Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2006.05745 · Physical Review A

Improved quantum algorithm for A-optimal projection

Shi‐Jie Pan, Lin‐Chun Wan, Hailing Liu, Qing-Le Wang, Su‐Juan Qin, Qiaoyan Wen, Fei Gao

Published Nov 4, 2020• 41 citations
arXivHTMLPDF

Abstract

Dimensionality reduction algorithms, which reduce the dimensionality of a given data set whereas preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan et al. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space $n$ and the dimensionality of the reduced feature space $k$ over the classical algorithm. In this paper, we correct the time complexity of the algorithm of Duan et al. to $O\left[\frac{{\ensuremath{\kappa}}^{4s}\sqrt{{k}^{s}}}{{\ensuremath{\epsilon}}^{s}}{\mathrm{polylog}}^{s}\left(\frac{mn}{\ensuremath{\epsilon}}\right)\right]$, where $\ensuremath{\kappa}$ is the condition number of a matrix that related to the original data set, $s$ is the number of iterations, $m$ is the number of data points, and $\ensuremath{\epsilon}$ is the desired precision of the output state. Since the time complexity has an exponential dependence on $s$, the quantum algorithm can only be beneficial for high-dimensional problems with a small number of iterations $s$. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity $O\left[\frac{s{\ensuremath{\kappa}}^{6}\sqrt{k}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{nm}{\ensuremath{\epsilon}}\right)+\frac{{s}^{2}{\ensuremath{\kappa}}^{4}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{\ensuremath{\kappa}k}{\ensuremath{\epsilon}}\right)\right]$ and space complexity $O[{log}_{2}(nk/\ensuremath{\epsilon})+s]$. With space complexity slightly worse, our algorithm achieves, at least, a polynomial speedup compared to the algorithm of Duan et al.. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when $\ensuremath{\kappa},\phantom{\rule{0.28em}{0ex}}k$, and $1/\ensuremath{\epsilon}$ are $O[\mathrm{polylog}(nm)]$.

DOI
10.1103/physreva.102.052402

Related papers

Quantum algorithm and quantum circuit for A-optimal projection: Dimensionality reduction

Bojia Duan, Jiabin Yuan, Juan Xu +1 more

Learning low-dimensional representation is a crucial issue for many machine-learning tasks, such as pattern recognition and image retrieval. In this article, we present a quantum algorithm and a quantum circuit to efficiently perform A-optimal projection for dimensionality reduction. Compared with the best-know classical algorithms, the quantum A-optimal projection (QAOP) algorithm shows an exponential speedup in both the original feature space dimension $n$ and the reduced feature space dimension $k$. We show that the space and time complexity of the QAOP circuit are $O[{log}_{2}(nk/\ensuremath{\epsilon})]$ and $O[{log}_{2}(nk)\text{poly}({log}_{2}{\ensuremath{\epsilon}}^{\ensuremath{-}1})],$ respectively, with fidelity at least $1\ensuremath{-}\ensuremath{\epsilon}$. First, a reformation of the original QAOP algorithm is proposed to help omit the quantum-classical interactions during the QAOP algorithm. Then the quantum algorithm and quantum circuit with performance guarantees are proposed. Specifically, the quantum circuit modules for preparing the initial quantum state and implementing the controlled rotation can be also used for other quantum machine-learning algorithms.

arXiv:1812.09782•Physical Review A•Mar 11, 2019•54 citations

Quantum discriminant analysis for dimensionality reduction and classification

Iris Cong, Luming Duan

We present quantum algorithms to efficiently perform discriminant analysis for dimensionality reduction and classification over an exponentially large input data set. Compared with the best-known classical algorithms, the quantum algorithms show an exponential speedup in both the number of training vectors M and the feature space dimension N . We generalize the previous quantum algorithm for solving systems of linear equations (2009 Phys. Rev. Lett. 103 150502 ) to efficiently implement a Hermitian chain product of k trace-normalized N × N Hermitian positive-semidefinite matrices with time complexity of . Using this result, we perform linear as well as nonlinear Fisher discriminant analysis for dimensionality reduction over M vectors, each in an N -dimensional feature space, in time , where denotes the tolerance error, and p is the number of principal projection directions desired. We also present a quantum discriminant analysis algorithm for data classification with time complexity .

arXiv:1510.00113•New Journal of Physics•Jul 6, 2016•133 citations

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The $q$-means algorithm has convergence and precision guarantees similar to $k$-means, and it outputs with high probability a good approximation of the $k$ cluster centroids like the classical algorithm. Given a dataset of $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)$ per iteration, where $κ(V)$ is the condition number, $μ(V)$ is a parameter that appears in quantum linear algebra procedures and $η= \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)$ per iteration, which is linear in the number of features $d$, and polynomial in the rank $k$, the maximum square norm $η$ and the error parameter $δ$. Both running times are only polylogarithmic in the number of datapoints $N$. Our algorithm provides substantial savings compared to the classical $k$-means algorithm that runs in time $O(kdN)$ per iteration, particularly for the case of large datasets.

arXiv:1812.03584•Dec 10, 2018•119 citations

Near-optimal quantum kernel principal component analysis

Youle Wang

Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ⁡ ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.

Quantum Science and Technology•Nov 12, 2024•6 citations

q-means: A quantum algorithm for unsupervised machine learning

Iordanis Kerenidis, Jonas Landman, Alessandro Luongo +1 more

Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The $q$-means algorithm has convergence and precision guarantees similar to $k$-means, and it outputs with high probability a good approximation of the $k$ cluster centroids like the classical algorithm. Given a dataset of $N$ $d$-dimensional vectors $v_i$ (seen as a matrix $V \in \mathbb{R}^{N \times d})$ stored in QRAM, the running time of q-means is $\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)$ per iteration, where $\kappa(V)$ is the condition number, $\mu(V)$ is a parameter that appears in quantum linear algebra procedures and $\eta = \max_{i} ||v_{i}||^{2}$. For a natural notion of well-clusterable datasets, the running time becomes $\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)$ per iteration, which is linear in the number of features $d$, and polynomial in the rank $k$, the maximum square norm $\eta$ and the error parameter $\delta$. Both running times are only polylogarithmic in the number of datapoints $N$. Our algorithm provides substantial savings compared to the classical $k$-means algorithm that runs in time $O(kdN)$ per iteration, particularly for the case of large datasets.

•Jan 1, 2019•15 citations

Quantum algorithm for linear regression

Guoming Wang

We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where $N$ is the size of the data set, $d$ is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on $d$ and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.

arXiv:1402.0660•Physical Review A•Jul 31, 2017•144 citations
Dimensionality reduction algorithms, which reduce the dimensionality of a given data set whereas preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan et al. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space nnn and the dimensionality of the reduced feature space kkk over the classical algorithm. In this paper, we correct the time complexity of the algorithm of Duan et al. to O[\ensuremathκ4sks\ensuremathϵspolylogs(mn\ensuremathϵ)]O\left[\frac{{\ensuremath{\kappa}}^{4s}\sqrt{{k}^{s}}}{{\ensuremath{\epsilon}}^{s}}{\mathrm{polylog}}^{s}\left(\frac{mn}{\ensuremath{\epsilon}}\right)\right]O[\ensuremathϵs\ensuremathκ4sks​​polylogs(\ensuremathϵmn​)], where \ensuremathκ\ensuremath{\kappa}\ensuremathκ is the condition number of a matrix that related to the original data set, sss is the number of iterations, mmm is the number of data points, and \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ is the desired precision of the output state. Since the time complexity has an exponential dependence on sss, the quantum algorithm can only be beneficial for high-dimensional problems with a small number of iterations sss. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity O[s\ensuremathκ6k\ensuremathϵpolylog(nm\ensuremathϵ)+s2\ensuremathκ4\ensuremathϵpolylog(\ensuremathκk\ensuremathϵ)]O\left[\frac{s{\ensuremath{\kappa}}^{6}\sqrt{k}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{nm}{\ensuremath{\epsilon}}\right)+\frac{{s}^{2}{\ensuremath{\kappa}}^{4}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{\ensuremath{\kappa}k}{\ensuremath{\epsilon}}\right)\right]O[\ensuremathϵs\ensuremathκ6k​​polylog(\ensuremathϵnm​)+\ensuremathϵs2\ensuremathκ4​polylog(\ensuremathϵ\ensuremathκk​)] and space complexity O[log2(nk/\ensuremathϵ)+s]O[{log}_{2}(nk/\ensuremath{\epsilon})+s]O[log2​(nk/\ensuremathϵ)+s]. With space complexity slightly worse, our algorithm achieves, at least, a polynomial speedup compared to the algorithm of Duan et al.. Also, our algorithm shows exponential speedups in nnn and mmm compared with the classical algorithm when \ensuremathκ,k\ensuremath{\kappa},\phantom{\rule{0.28em}{0ex}}k\ensuremathκ,k, and 1/\ensuremathϵ1/\ensuremath{\epsilon}1/\ensuremathϵ are O[polylog(nm)]O[\mathrm{polylog}(nm)]O[polylog(nm)].
Learning low-dimensional representation is a crucial issue for many machine-learning tasks, such as pattern recognition and image retrieval. In this article, we present a quantum algorithm and a quantum circuit to efficiently perform A-optimal projection for dimensionality reduction. Compared with the best-know classical algorithms, the quantum A-optimal projection (QAOP) algorithm shows an exponential speedup in both the original feature space dimension nnn and the reduced feature space dimension kkk. We show that the space and time complexity of the QAOP circuit are $O[{log}_{2}(nk/\ensuremath{\epsilon})]$ and $O[{log}_{2}(nk)\text{poly}({log}_{2}{\ensuremath{\epsilon}}^{\ensuremath{-}1})],$ respectively, with fidelity at least $1\ensuremath{-}\ensuremath{\epsilon}$. First, a reformation of the original QAOP algorithm is proposed to help omit the quantum-classical interactions during the QAOP algorithm. Then the quantum algorithm and quantum circuit with performance guarantees are proposed. Specifically, the quantum circuit modules for preparing the initial quantum state and implementing the controlled rotation can be also used for other quantum machine-learning algorithms.
We present quantum algorithms to efficiently perform discriminant analysis for dimensionality reduction and classification over an exponentially large input data set. Compared with the best-known classical algorithms, the quantum algorithms show an exponential speedup in both the number of training vectors M and the feature space dimension N . We generalize the previous quantum algorithm for solving systems of linear equations (2009 Phys. Rev. Lett. 103 150502 ) to efficiently implement a Hermitian chain product of k trace-normalized N × N Hermitian positive-semidefinite matrices with time complexity of . Using this result, we perform linear as well as nonlinear Fisher discriminant analysis for dimensionality reduction over M vectors, each in an N -dimensional feature space, in time , where denotes the tolerance error, and p is the number of principal projection directions desired. We also present a quantum discriminant analysis algorithm for data classification with time complexity .
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\widetilde{O}\left( k d \fracη{δ^2}κ(V)(μ(V) + k \fracηδ) + k^2 \frac{η^{1.5}}{δ^2} κ(V)μ(V) \right)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)κ(V)κ(V) is the condition number, μ(V)μ(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2η= \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{η^{2.5}}{δ^3} + k^{2.5} \frac{η^2}{δ^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm ηηη and the error parameter δδδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)O(kdN) per iteration, particularly for the case of large datasets.
Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ⁡ ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.
Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The qqq-means algorithm has convergence and precision guarantees similar to kkk-means, and it outputs with high probability a good approximation of the kkk cluster centroids like the classical algorithm. Given a dataset of NNN ddd-dimensional vectors viv_ivi​ (seen as a matrix V∈RN×d)V \in \mathbb{R}^{N \times d})V∈RN×d) stored in QRAM, the running time of q-means is O~(kdηδ2κ(V)(μ(V)+kηδ)+k2η1.5δ2κ(V)μ(V))\widetilde{O}\left( k d \frac{\eta}{\delta^2}\kappa(V)(\mu(V) + k \frac{\eta}{\delta}) + k^2 \frac{\eta^{1.5}}{\delta^2} \kappa(V)\mu(V) \right)O(kdδ2η​κ(V)(μ(V)+kδη​)+k2δ2η1.5​κ(V)μ(V)) per iteration, where κ(V)\kappa(V)κ(V) is the condition number, μ(V)\mu(V)μ(V) is a parameter that appears in quantum linear algebra procedures and η=max⁡i∣∣vi∣∣2\eta = \max_{i} ||v_{i}||^{2}η=maxi​∣∣vi​∣∣2. For a natural notion of well-clusterable datasets, the running time becomes O~(k2dη2.5δ3+k2.5η2δ3)\widetilde{O}\left( k^2 d \frac{\eta^{2.5}}{\delta^3} + k^{2.5} \frac{\eta^2}{\delta^3} \right)O(k2dδ3η2.5​+k2.5δ3η2​) per iteration, which is linear in the number of features ddd, and polynomial in the rank kkk, the maximum square norm η\etaη and the error parameter δ\deltaδ. Both running times are only polylogarithmic in the number of datapoints NNN. Our algorithm provides substantial savings compared to the classical kkk-means algorithm that runs in time O(kdN)O(kdN)O(kdN) per iteration, particularly for the case of large datasets.
We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where NNN is the size of the data set, ddd is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on ddd and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.