title: Quantum support vector machine for big data classification.
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.
authors.affiliation: Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA.
authors.forename: Patrick
authors.initials: P
authors.lastname: Rebentrost
authors.affiliation: Google Research, Venice, California 90291, USA.
authors.forename: Masoud
authors.initials: M
authors.lastname: Mohseni
authors.affiliation: 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.
authors.forename: Seth
authors.initials: S
authors.lastname: Lloyd