The DOI matches its DataCite record.
Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
Open accessAbstract
A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC'19], we introduce such a model, where we assume we can efficiently perform $\ell^2$-norm samples of input data, a natural analogue to quantum algorithms that assume efficient state preparation of classical data. Though this model produces less practical algorithms than the (stronger) standard model of classical computation, it captures versions of many of the features and nuances of quantum linear algebra algorithms. With this model, we describe classical analogues to Lloyd, Mohseni, and Rebentrost's quantum algorithms for principal component analysis [Nat. Phys. 10, 631 (2014)] and nearest-centroid clustering [arXiv:1307.0411]. Since they are only polynomially slower, these algorithms suggest that the exponential speedups of their quantum counterparts are simply an artifact of state preparation assumptions.
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
“So far, dequantized machine learning algorithms have been developed for recommendation systems (Tang, 2019), principal component analysis and supervised clustering (Tang, 2018), stochastic regression (Gilyén et al. , 2018) and low-rank linear systems (Arrazola et al. , 2019; Chia et al. , 2018).”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Tang, 2018
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
No references could be resolved yet.
Research works printed but not linked: 11
- [1]V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Physical review letters 100 , 160501 (2008).
- [3]A. Prakash, Quantum algorithms for linear algebra and machine learning. , Ph.D. thesis, UC Berkeley (2014).
- [6]E. Tang, A quantum-inspired classical algorithm for recommendation systems, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing STOC 2019 (ACM Press, 2019) arXiv:1807.04271 [cs.IR]. · arXiv
- [5]I. Kerenidis and A. Prakash, Quantum recommendation systems, in 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , LIPIcs, Vol. 67 (Schloss Dagstuhl, 2017) pp. 49:1-49:21.
- [7]L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions, arXiv (2002), arXiv:0208112 [quant-ph].
- [10]R. Orús, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics 349 , 117 (2014).
- [12]U. Schollwöck, The density-matrix renormalization group in the age of matrix product states, Annals of Physics 326 , 96 (2011).
- [16]J. C. Bridgeman and C. T. Chubb, Hand-waving and interpretive dance: an introductory course on tensor networks, Journal of Physics A: Mathematical and Theoretical 50 , 223001 (2017).
- [19]W. Hoeffding, Probability inequalities for sums of bounded random variables, in The Collected Works of Wassily Hoeffding , edited by N. I. Fisher and P. K. Sen (Springer New York, New York, NY, 1994) pp. 409-426.
- [20]C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM Journal on Computing 26 , 1510 (1997).
- [22]A. Frieze, R. Kannan, and S. Vempala, Fast Monte-Carlo algorithms for finding low-rank approximations, Journal of the ACM (JACM) 51 , 1025 (2004).
Cited by
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
Variational quantum state diagonalization
LaRose, R., Tikku, A., O’Neel-Judy, É., Cincio, L., & Coles, P. J. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0167-6 · Cited by 199
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
Metadata
- Authors
- Tang, E.
- Affiliations
- University of Washington (US)
- Corresponding author
- Tang, Ewin
- ORCID
- Tang, Ewin
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2018
- Volume
- 127
- Issue
- 6
- Pages
- 060503-060503
- ISSN
- 0031-9007 (ISSN-L)
- arXiv
- 1811.00414
- OpenAlex
- W3192002582
- Cited by
- 141
- References
- 0
- Citations by year
- 2026: 17 · 2025: 23 · 2024: 26 · 2023: 25 · 2022: 25 · 2021: 12 · 2020: 7 · 2019: 4 · 2018: 2
- FWCI
- 7.75
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1762114)
- 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 principal component analysis, quantum linear algebra, quantum state preparation, exponential speedup, quantum machine learning
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
