Quantum discriminant analysis for dimensionality reduction and classification

DOI10.1088/1367-2630/18/7/073011MaRDI QIDQ5855064zbMATH OpenOpenAlexFDO

Authors Iris Cong, Lu-Ming Duan

Publication date 12 March 2021

Published in New Journal of Physics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://arxiv.org/abs/1510.00113

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum computation (81P68)

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 $NimesN$ 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(pextpolylog(MN)/epsilo{n}^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)/epsilo{n}^3)$.

Recommendations

• Quantum locality preserving projection algorithm
• Quantum speedup of Bayes’ classifiers
• Discriminant analysis based on the approaches of quantum computing
• Quantum data compression by principal component analysis
• Quantum K nearest neighbor algorithm

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Multiplying matrices faster than coppersmith-winograd
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithms revisited
• Quantum Computer Science
• Quantum Computing
• Quantum random access memory

Cited in

(39)

• Quantum-enhanced feature selection with forward selection and backward elimination
• An all-pair quantum SVM approach for big data multiclass classification
• Quantum mean centering for block-encoding-based quantum algorithm
• Quantum algorithm for Laplacian eigenmap via Rayleigh quotient iteration
• Quantum data compression by principal component analysis
• Quantum locality preserving projection algorithm
• Quantum algorithms for anomaly detection using amplitude estimation
• Quantum algorithms for similarity measurement based on Euclidean distance
• A survey on HHL algorithm: from theory to application in quantum machine learning
• Discriminant analysis based on the approaches of quantum computing
• An improved quantum principal component analysis algorithm based on the quantum singular threshold method
• Improved quantum algorithm for MMSE-based massive MIMO uplink detection
• Quantum algorithm for help-training semi-supervised support vector machine
• Quantum locally linear embedding for nonlinear dimensionality reduction
• Quantum \(k\)-fold cross-validation for nearest neighbor classification algorithm
• Quantum kernel logistic regression based Newton method
• Quantum dimensionality reduction by linear discriminant analysis
• An improved quantum algorithm for support matrix machines
• Quantum classifiers for domain adaptation
• Obtaining a linear combination of the principal components of a matrix on quantum computers
• Quantum-inspired minimum distance classification in a biomedical context
• Quantum speedup of Bayes’ classifiers
• Quantum discriminative canonical correlation analysis
• Quantum average neighborhood margin maximization for feature extraction
• Quantum machine learning for natural language processing application
• Quantum-inspired canonical correlation analysis for exponentially large dimensional data
• Module for arbitrary controlled rotation in gate-based quantum algorithms
• Learning quantum finite automata with queries
• Quantum attacks on beyond-birthday-bound MACs
• Quantum support vector machine based on regularized Newton method
• Quantum self-organizing feature mapping neural network algorithm based on Grover search algorithm
• A novel quantum algorithm for converting between one-hot and binary encodings
• Quantum metric learning with fuzzy-informed learning
• Quantum algorithm for classical multidimensional scaling
• An introduction to quantum computing for statisticians and data scientists
• A flexible quantum convolutional neural network
• Low-depth quantum approximate optimization algorithm for maximum likelihood detection in massive MIMO
• Rapidly trainable and shallow-compiled quantum approximate optimization algorithm for maximum likelihood detection
• Robust dequantization of the quantum singular value transformation and quantum machine learning algorithms

This page was built for publication: Quantum discriminant analysis for dimensionality reduction and classification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5855064)