Format

Send to

Choose Destination
Phys Rev Lett. 2014 Sep 26;113(13):130503. Epub 2014 Sep 25.

Quantum support vector machine for big data classification.

Author information

1
Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.
2
Google Research, Venice, California 90291, USA.
3
Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA and Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.

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.

Supplemental Content

Full text links

Icon for American Physical Society
Loading ...
Support Center