Quantum algorithm and quantum circuit for A-Optimal Projection: dimensionality reduction

Abstract

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\left[{\log }_2\left(nk/\epsilon \right)\right]$ and $O[{\log }_2(nk)poly\left({\log }_2{\epsilon }^{-1}\right)]$ respectively, with fidelity at least $1-\epsilon$. Firstly, 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.

18 pages, 9 figures

References in corpus (12)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum machine learning in feature Hilbert spaces
• Quantum principal component analysis
• Quantum random access memory
• Quantum Networks for Elementary Arithmetic Operations
• Prediction by linear regression on a quantum computer
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• On the robustness of bucket brigade quantum RAM
• A Robust Quantum Random Access Memory
• Efficient quantum circuit for singular value thresholding

Cited by in corpus (16)

• Quantum K-nearest neighbor classification algorithm based on Hamming distance
• Automatic design of quantum feature maps
• Machine Learning Phase Transitions with a Quantum Processor
• Quantum Anomaly Detection with Density Estimation and Multivariate Gaussian Distribution
• Improved quantum algorithm for A-optimal projection
• Quantum Dimensionality Reduction by Linear Discriminant Analysis
• A brief introduction to quantum algorithms
• Quantum algorithm for Neighborhood Preserving Embedding
• Quantum-enhanced least-square support vector machine: simplified quantum algorithm and sparse solutions
• Quantum correlation alignment for unsupervised domain adaptation
• Experimental implementation of quantum algorithm for association rules mining
• An Investigation on Support Vector Clustering for Big Data in Quantum Paradigm
• Implementing perceptron models with qubits
• Quantum Approximate Optimization Algorithm for Maximum Likelihood Detection in Massive MIMO
• Quantum locally linear embedding for nonlinear dimensionality reduction
• Riemannian-geometric generalizations of quantum fidelities and Bures-Wasserstein distance