Quantum Support Vector Machine for Big Data Classification
Top Cited Papers
- 25 September 2014
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 113 (13), 130503
- https://doi.org/10.1103/physrevlett.113.130503
Abstract
Supervised machine learning is the classification of new data based on already classified training examples. In this work, we show that the support vector machine, an optimized binary classifier, can be implemented on a quantum computer, with complexity logarithmic in the size of the vectors and the number of training examples. In cases where classical sampling algorithms require polynomial time, an exponential speedup is obtained. At the core of this quantum big data algorithm is a nonsparse matrix exponentiation technique for efficiently performing a matrix inversion of the training data inner-product (kernel) matrix.Keywords
Other Versions
Funding Information
- Defense Advanced Research Projects Agency (DARPA)
- National Science Foundation (NSF)
- Eni
- Air Force Office of Scientific Research (AFOSR)
This publication has 19 references indexed in Scilit:
- Quantum principal component analysisNature Physics, 2014
- Quantum adiabatic machine learningQuantum Information Processing, 2012
- Quantum Algorithm for Data FittingPhysical Review Letters, 2012
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Convex OptimizationPublished by Cambridge University Press (CUP) ,2004
- Equivalences and Separations Between Quantum and Classical LearnabilitySIAM Journal on Computing, 2004
- Quantum optimization for training support vector machinesNeural Networks, 2003
- Quantum learning and universal quantum matching machinePhysical Review A, 2002
- Least Squares Support Vector Machine ClassifiersNeural Processing Letters, 1999
- Support-vector networksMachine Learning, 1995