The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Quantum Support Vector Machine for Big Data Classification
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“Exponential speedup has, for instance, shown to be possible for quantum support vector machines [110]”
From Neutral atom quantum computing hardware: performance and end-user perspective (2023) · cites this paper as [110]
In the citing paper
“First, by more sophisticated Trotter-Suzuki decompositions 261 , the approximation error can be made to depend on progressively-higher orders in τ 196,260,261 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [261]
In the citing paper
“If |χ is some other vector, then the method provides a method for supervised learning and cluster assignment 9,10,21,28 :”
From Quantum principal component analysis (2014) · cites this paper as [28]
In the citing paper
“Note that this expressivity boost is not limited to neural networks and has been observed, for instance, for support vector machines.[222,228,229]”
From Quantum Computing for Molecular Biology** (2023) · cites this paper as [222]
In the citing paper
“The first advantage has been leveraged in deriving the quantum realization of the principal components analysis algorithm [221] and of a support vector machine.[222]”
From Quantum Computing for Molecular Biology** (2023) · cites this paper as [222]
In the citing paper
“Rebentrost et al. [75] presented a quantum algorithm that can train a SVM with a polynomial kernel in O log N ð Þ, and this was later extended to the radial basis function (RBF) kernel [76].”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [75]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Cortes, C., & Vapnik, V. (1995) · Machine Learning · doi:10.1007/bf00994018 · Cited by 59,421
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
An Introduction to the Bootstrap
Efron, B., & Tibshirani, R. J. (1994) · doi:10.1201/9780429246593 · Cited by 40,500
Book Review: Pattern Recognition and Machine Learning
Nasrabadi, N. M. (2007) · Journal of Electronic Imaging · doi:10.1117/1.2819119 · Cited by 22,066
Least Squares Support Vector Machine Classifiers
Suykens, J., & Vandewalle, J. (1999) · Neural Processing Letters · doi:10.1023/a:1018628609742 · Cited by 9,481
(2012) · Cited by 9,062
Information theory, inference, and learning algorithms
(2004) · Choice Reviews Online · doi:10.5860/choice.41-5949 · Cited by 6,536
Proceedings of the 25th international conference on Machine learning
Cohen, W. W., McCallum, A., & Roweis, S. T. (2008) · Cited by 5,691
ASH, R. B. (1966) · Cited by 3,990
An introduction to kernel-based learning algorithms
Müller, K. R., Mika, S., Rätsch, G., Tsuda, K., & Schölkopf, B. (2001) · IEEE Transactions on Neural Networks · doi:10.1109/72.914517 · Cited by 3,521
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325
Self-citationPattern recognition and machine learning
(2007) · Choice Reviews Online · doi:10.5860/choice.44-5091 · Cited by 2,783
Kernel methods in machine learning
Hofmann, T., Schölkopf, B., & Smola, A. J. (2008) · The Annals of Statistics · doi:10.1214/009053607000000677 · Cited by 2,292
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1990) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(08)80013-2 · Cited by 2,248
Quantum principal component analysis
Lloyd, S., Mohseni, M., & Rebentrost, P. (2014) · Nature Physics · doi:10.1038/nphys3029 · Cited by 1,385
Self-citationProceedings Of The International Joint Conference On Neural Networks 2003
(2003) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2003.1223944 · Cited by 953
Giovannetti, V., Lloyd, S., & Maccone, L. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.160501 · Cited by 935
Self-citationInformation Theory, Inference, and Learning Algorithms
(2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834752 · Cited by 866
Efficient Quantum Algorithms for Simulating Sparse Hamiltonians
Berry, D. W., Ahokas, G., Cleve, R., & Sanders, B. C. (2007) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0150-x · Cited by 692
Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
Drineas, P., Kannan, R., & Mahoney, M. W. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704442696 · Cited by 569
Randomized algorithms for the low-rank approximation of matrices
Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., & Tygert, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0709640104 · Cited by 559
Quantum Algorithm for Data Fitting
Wiebe, N., Braun, D., & Lloyd, S. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.050505 · Cited by 528
Self-citationOn the Relationship Between Continuous- and Discrete-Time Quantum Walk
Childs, A. M. (2010) · Communications in Mathematical Physics · doi:10.1007/s00220-009-0930-1 · Cited by 411
Introduction to Machine Learning (Adaptive Computation and Machine Learning)
Alpaydın, E. (2004) · The MIT Press eBooks · Cited by 291
Quantum Speedup for Active Learning Agents
Paparo, G. D., Dunjko, V., Makmal, A., Martin-Delgado, M. A., & Briegel, H. J. (2014) · Physical Review X · doi:10.1103/physrevx.4.031002 · Cited by 192
Quantum adiabatic machine learning
Pudenz, K. L., & Lidar, D. A. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0506-4 · Cited by 139
Equivalences and Separations Between Quantum and Classical Learnability
Servedio, R. A., & Gortler, S. J. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539704412910 · Cited by 126
Quantum optimization for training support vector machines
Anguita, D., Ridella, S., Rivieccio, F., & Zunino, R. (2003) · Neural Networks · doi:10.1016/s0893-6080(03)00087-x · Cited by 119
Quantum learning and universal quantum matching machine
Sasaki, M., & Carlini, A. (2002) · Physical Review A · doi:10.1103/physreva.66.022303 · Cited by 103
Proceedings of the 29 th International Conference on Machine Learning, Edinburgh, Scotland, UK, 2012
Zhong, M., & Girolami, M. (2012) · Cited by 23
Flagged first, then by citations
Research works printed but not linked: 3
- S. Aaronson, 2010, Proceedings of the 42nd ACM Symposium on Theory of Computing, Cambridge, MA, 2010
- C. Ding, 2004, Proceedings of the 21st International Conference on Machine Learning, Banff, AB, Canada, 2004
- Z. Bar-Yossef, 2003, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, 2003
Cited by
Sorted by citations
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
Self-citationSupervised learning with quantum-enhanced feature spaces
Havlíček, V., Córcoles, A. D., Temme, K., Harrow, A. W., Kandala, A., Chow, J. M., & Gambetta, J. M. (2019) · Nature · doi:10.1038/s41586-019-0980-2 · Cited by 2,572
A quantum engineer's guide to superconducting qubits
Krantz, P., Kjærgaard, M., Yan, F., Orlando, T. P., Gustavsson, S., & Oliver, W. D. (2019) · Applied Physics Reviews · doi:10.1063/1.5089550 · Cited by 2,321
Quantum Machine Learning in Feature Hilbert Spaces
Schuld, M., & Killoran, N. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.040504 · Cited by 1,840
Big data in healthcare: management, analysis and future prospects
Dash, S., Shakyawar, S. K., Sharma, M., & Kaushik, S. (2019) · Journal of Big Data · doi:10.1186/s40537-019-0217-0 · Cited by 1,747
Metadata
- Authors
- Rebentrost, P., Mohseni, M., & Lloyd, S.
- Affiliations
- Massachusetts Institute of Technology (US)
- Google (United States) (US)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2014-09-25
- Volume
- 113
- Issue
- 13
- Pages
- 130503-130503
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2103956991
- Cited by
- 1,951
- References
- 30
- Citations by year
- 2026: 229 · 2025: 306 · 2024: 274 · 2023: 277 · 2022: 205 · 2021: 208 · 2020: 151 · 2019: 105 · 2018: 77 · 2017: 54 · 2016: 45 · 2015: 13 · 2014: 7
- FWCI
- 39.50
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
- arXiv (Cornell University)
- Funders
- Defense Advanced Research Projects Agency (DARPA)
- National Science Foundation (NSF)
- Eni
- Air Force Office of Scientific Research (AFOSR)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum support vector machine, quantum machine learning, big data classification, binary classification, quantum advantage, matrix inversion, kernel matrix, quantum computing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
