Improved quantum algorithm for A-optimal projection

Abstract

Dimensionality reduction (DR) algorithms, which reduce the dimensionality of a given data set while preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan \emph{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 Duan \emph{et al}.'s algorithm to $O(\frac{{\kappa }^{4s}\sqrt{k^s}}{{\epsilon }^s}{\mathrm{polylog}}^s(\frac{mn}{\epsilon }))$, where $\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 $\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(\frac{s{\kappa }^6\sqrt{k}}{\epsilon }\mathrm{polylog}(\frac{nm}{\epsilon })+\frac{s^2{\kappa }^4}{\epsilon }\mathrm{polylog}(\frac{\kappa k}{\epsilon }))$ and space complexity $O({\log }_2(nk/\epsilon )+s)$. With space complexity slightly worse, our algorithm achieves at least a polynomial speedup compared to Duan \emph{et al}.'s algorithm. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when both $\kappa$, $k$ and $1/\epsilon$ are $O(\mathrm{polylog}(nm))$.

arXiv comment11 pages, 2 figures

References in corpus (19)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• Quantum Algorithms Revisited
• Hamiltonian Simulation by Qubitization
• Quantum Data Fitting
• Prediction by linear regression on a quantum computer
• Implementing a distance-based classifier with a quantum interference circuit
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum Algorithm for Linear Regression
• Quantum machine learning for quantum anomaly detection
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• Quantum data compression by principal component analysis
• Quantum algorithm for association rules mining
• Quantum algorithm for association rules mining
• Quantum algorithm for visual tracking
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• Quantum algorithm and quantum circuit for A-Optimal Projection: dimensionality reduction

Cited by in corpus (7)

• Variational Quantum algorithm for Poisson equation
• Quantum algorithms for anomaly detection using amplitude estimation
• Quantum Dimensionality Reduction by Linear Discriminant Analysis
• A brief introduction to quantum algorithms
• Quantum algorithm for Neighborhood Preserving Embedding
• Quantum Algorithm for Unsupervised Anomaly Detection
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem