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 2019.], we introduce such a model, where we assume we can efficiently perform ℓ^{2}-norm samples of input data, a natural analog 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 analogs to Lloyd, Mohseni, and Rebentrost's quantum algorithms for principal component analysis [S. Lloyd, M. Mohseni, and P. Rebentrost, Nat. Phys. 10, 631 (2014).NPAHAX1745-247310.1038/nphys3029] and nearest-centroid clustering [S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning]. 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.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
These quantum machine learning approaches need careful consideration of subtle issues that do not appear in classical algorithms and are strongly intertwined with the underlying hardware.
“Regardless of the conditions of their advantages, these approaches need careful consideration of subtle issues (see, e.g., Refs.[112-115]) that do not appear in classical algorithms and are, in particular, strongly intertwined with the underlying hardware.”
From Neutral atom quantum computing hardware: performance and end-user perspective (2023) · cites this paper as [112]
Cites
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830 · see citing works
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 · see citing works
Quantum Support Vector Machine for Big Data Classification
Rebentrost, P., Mohseni, M., & Lloyd, S. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.130503 · Cited by 1,951 · see citing works
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · see citing works
Quantum principal component analysis
Lloyd, S., Mohseni, M., & Rebentrost, P. (2014) · Nature Physics · doi:10.1038/nphys3029 · Cited by 1,385 · see citing works
Aaronson, S. (2015) · Nature Physics · doi:10.1038/nphys3272 · Cited by 567 · see citing works
Quantum Algorithm for Data Fitting
Wiebe, N., Braun, D., & Lloyd, S. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.050505 · Cited by 528 · see citing works
Quantum Speed-Ups for Solving Semidefinite Programs
Brandao, F. G. S. L., & Svore, K. M. (2017) · 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) · doi:10.1109/focs.2017.45 · Cited by 142 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
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 1,726 · see citing works
Quantum advantage in learning from experiments
Huang, H.-Y., Broughton, M., Cotler, J., Chen, S., Li, J., Mohseni, M., Neven, H., Babbush, R., Kueng, R., Preskill, J., et al. (2022) · Science · doi:10.1126/science.abn7293 · Cited by 519 · see citing works
The Born supremacy: quantum advantage and training of an Ising Born machine
Coyle, B., Mills, D., Danos, V., & Kashefi, E. (2020) · npj Quantum Information · doi:10.1038/s41534-020-00288-9 · Cited by 155 · see citing works
Neutral atom quantum computing hardware: performance and end-user perspective
Wintersperger, K., Dommert, F., Ehmer, T., Hoursanov, A., Klepsch, J., Mauerer, W., Reuber, G., Strohm, T., Yin, M., & Luber, S. (2023) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-023-00190-1 · Cited by 117 · see citing works
Quantum Algorithms for Deep Convolutional Neural Networks
Kerenidis, I., Landman, J., & Prakash, A. (2019) · arXiv · doi:10.48550/arxiv.1911.01117 · Cited by 102 · see citing works
- Authors
- Tang, E.
- Affiliations
- University of Washington (US)
- Corresponding author
- Tang, Ewin
- ORCID
- Tang, Ewin
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2021-08-04
- Volume
- 127
- Issue
- 6
- Pages
- 060503-060503
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W3192002582
- Cited by
- 140
- References
- 8
- Citations by year
- 2026: 16 · 2025: 23 · 2024: 26 · 2023: 25 · 2022: 25 · 2021: 12 · 2020: 7 · 2019: 4 · 2018: 2
- FWCI
- 7.78
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (DGE-1762114)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › 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
