Quantum Discriminant Analysis for Dimensionality Reduction and Classification

Abstract

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 [Phys. Rev. Lett. 103, 150502 (2009)] to efficiently implement a Hermitian chain product of $k$ trace-normalized $N\times N$ Hermitian positive-semidefinite matrices with time complexity of $O(\log (N))$. 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 $O(p\text{polylog}(MN)/{\epsilon }^3)$, where $\epsilon$ 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 $O(\log (MN)/{\epsilon }^3)$.

11 pages, published version

References in corpus (5)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum random access memory
• Creating superpositions that correspond to efficiently integrable probability distributions

Cited by in corpus (38)

• A rigorous and robust quantum speed-up in supervised machine learning
• Quantum Adversarial Machine Learning
• Variational Quantum algorithm for Poisson equation
• q-means: A quantum algorithm for unsupervised machine learning
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Quantum data compression by principal component analysis
• Hamiltonian Simulation with Optimal Sample Complexity
• Quantum algorithm for association rules mining
• Quantum algorithm for association rules mining
• Automatic design of quantum feature maps
• Quantum algorithm for visual tracking
• Quantum classification of the MNIST dataset with Slow Feature Analysis
• Quantum algorithm and quantum circuit for A-Optimal Projection: dimensionality reduction
• Quantum Anomaly Detection with Density Estimation and Multivariate Gaussian Distribution
• Variational Quantum Algorithms for Dimensionality Reduction and Classification
• Improved quantum algorithm for A-optimal projection
• Quantum algorithms for anomaly detection using amplitude estimation
• Universal Adversarial Examples and Perturbations for Quantum Classifiers
• Efficient quantum circuit for singular value thresholding
• Quantum Dimensionality Reduction by Linear Discriminant Analysis
• A brief introduction to quantum algorithms
• Quantum algorithm for Neighborhood Preserving Embedding
• Quantum algorithms for scientific computing
• Quantum correlation alignment for unsupervised domain adaptation
• Experimental implementation of quantum algorithm for association rules mining
• Quantum Continual Learning Overcoming Catastrophic Forgetting
• Quantum mean centering for block-encoding-based quantum algorithm
• Quantum diffusion map for nonlinear dimensionality reduction
• Quantum subspace alignment for domain adaptation
• Quantum Approximate Optimization Algorithm for Maximum Likelihood Detection in Massive MIMO
• Quantum algorithm for logistic regression
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• Quantum locally linear embedding for nonlinear dimensionality reduction
• Quantum approximated cloning-assisted density matrix exponentiation
• Quantum transfer component analysis for domain adaptation
• Quantum Algorithms for Prediction Based on Ridge Regression
• Quantum Laplacian Eigenmap
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks