Quantum Support Vector Machine for Big Data Classification
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90391 https://orcid.org/0000-0002-6728-8163 |
| _version_ | 1826209081319227392 |
|---|---|
| author | Mohseni, Masoud Lloyd, Seth Rebentrost, Frank Patrick |
| author2 | Massachusetts Institute of Technology. Department of Mechanical Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Mechanical Engineering Mohseni, Masoud Lloyd, Seth Rebentrost, Frank Patrick |
| author_sort | Mohseni, Masoud |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T14:17:16Z |
| format | Article |
| id | mit-1721.1/90391 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:17:16Z |
| publishDate | 2014 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/903912022-09-28T19:44:35Z Quantum Support Vector Machine for Big Data Classification Mohseni, Masoud Lloyd, Seth Rebentrost, Frank Patrick Massachusetts Institute of Technology. Department of Mechanical Engineering Massachusetts Institute of Technology. Research Laboratory of Electronics Rebentrost, Frank Patrick Lloyd, Seth 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. United States. Defense Advanced Research Projects Agency National Science Foundation (U.S.) United States. Air Force Office of Scientific Research Google-NASA Quantum Artificial Intelligence Laboratory 2014-09-26T14:53:32Z 2014-09-26T14:53:32Z 2014-09 2014-02 2014-09-25T22:00:02Z Article http://purl.org/eprint/type/JournalArticle 0031-9007 1079-7114 http://hdl.handle.net/1721.1/90391 Rebentrost, Patrick, Masoud Mohseni, and Seth Lloyd. "Quantum Support Vector Machine for Big Data Classification." Phys. Rev. Lett. 113, 130503 (September 2014). © 2014 American Physical Society https://orcid.org/0000-0002-6728-8163 en http://dx.doi.org/10.1103/PhysRevLett.113.130503 Physical Review Letters Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. American Physical Society application/pdf American Physical Society American Physical Society |
| spellingShingle | Mohseni, Masoud Lloyd, Seth Rebentrost, Frank Patrick Quantum Support Vector Machine for Big Data Classification |
| title | Quantum Support Vector Machine for Big Data Classification |
| title_full | Quantum Support Vector Machine for Big Data Classification |
| title_fullStr | Quantum Support Vector Machine for Big Data Classification |
| title_full_unstemmed | Quantum Support Vector Machine for Big Data Classification |
| title_short | Quantum Support Vector Machine for Big Data Classification |
| title_sort | quantum support vector machine for big data classification |
| url | http://hdl.handle.net/1721.1/90391 https://orcid.org/0000-0002-6728-8163 |
| work_keys_str_mv | AT mohsenimasoud quantumsupportvectormachineforbigdataclassification AT lloydseth quantumsupportvectormachineforbigdataclassification AT rebentrostfrankpatrick quantumsupportvectormachineforbigdataclassification |