Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing Quantum machine learning
Open accessThe DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Abstract
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang’s breakthrough quantum-inspired algorithm for recommendation systems [STOC’19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén et al. [STOC’19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffices to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: ℓ2-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691 · cited 1×
“[LMR14], cluster assignment and nding [LMR13], support vector machines [RML14], recommendation systems [KP17]), their quantum speedups are not as \strong" as, say, Shor’s algorithm for factoring [Sho97], because it is unclear how to load the input into a quantum computer eciently or conclude useful information fr…”
BackgroundQuantum 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 · cited 1×
“component regression The low-rank matrix inversion algorithm given by Gilyen et al. and Chia et al. [GLT18, CLW18] dequantizes Harrow, Hassidim, and Lloyd’s quantum matrix inversion algorithm (HHL) [HHL09] in the regime where the input matrix is low-rank instead of sparse { the corresponding quantum algorithm is prese…”
MethodLloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088
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
Quantum principal component analysis
Lloyd, S., Mohseni, M., & Rebentrost, P. (2014) · Nature Physics · doi:10.1038/nphys3029 · Cited by 1,385 · cited 1×
“Our framework improves on Tang’s dequantization [44] of the quantum principal component analysis (qPCA) algorithm [33].”
MethodGiovannetti, V., Lloyd, S., & Maccone, L. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.160501 · Cited by 935
Simulating Hamiltonian Dynamics with a Truncated Taylor Series
Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.090502 · Cited by 742
Aaronson, S. (2015) · Nature Physics · doi:10.1038/nphys3272 · Cited by 567
Quantum algorithms for supervised and unsupervised machine learning
Lloyd, S., Mohseni, M., & Rebentrost, P. (2013) · arXiv · doi:10.48550/arxiv.1307.0411 · Cited by 542
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
Berry, D. W., Childs, A. M., & Kothari, R. (2015) · 2015 IEEE 56th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.54 · Cited by 372
A quantum-inspired classical algorithm for recommendation systems
Tang, E. (2019) · Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing · doi:10.1145/3313276.3316310 · Cited by 360
Self-citationExponential improvement in precision for simulating sparse Hamiltonians
Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D. (2014) · Proceedings of the forty-sixth annual ACM symposium on Theory of computing · doi:10.1145/2591796.2591854 · Cited by 324
Adiabatic quantum state generation and statistical zero knowledge
Aharonov, D., & Ta-Shma, A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780546 · Cited by 322
Quantum Recommendation Systems
Kerenidis, I., & Prakash, A. (2016) · arXiv · doi:10.48550/arxiv.1603.08675 · Cited by 270
Quantum algorithms for topological and geometric analysis of data
Lloyd, S., Garnerone, S., & Zanardi, P. (2016) · Nature Communications · doi:10.1038/ncomms10138 · Cited by 241
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
Tang, E. (2018) · arXiv · doi:10.48550/arxiv.1811.00414 · Cited by 141
Self-citationTang, E. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.060503 · Cited by 140
Self-citationChakraborty, S., Gilyén, A., & Jeffery, S. (2019) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.icalp.2019.33 · Cited by 127
Self-citationQuantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
Gilyén, A., Lloyd, S., & Tang, E. (2018) · arXiv · doi:10.48550/arxiv.1811.04909 · Cited by 63
Self-citation
Cited by
Challenges and opportunities in quantum machine learning
Cerezo, M., Verdon, G., Huang, H.-Y., Cincio, L., & Coles, P. J. (2022) · Nature Computational Science · doi:10.1038/s43588-022-00311-3 · Cited by 689
A rigorous and robust quantum speed-up in supervised machine learning
Liu, Y., Arunachalam, S., & Temme, K. (2021) · Nature Physics · doi:10.1038/s41567-021-01287-z · Cited by 649
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
Herman, D., Googin, C., Liu, X., Sun, Y., Galda, A., Safro, I., Pistoia, M., & Alexeev, Y. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00603-1 · Cited by 284
Tang, E. (2018) · arXiv · doi:10.48550/arxiv.1811.00414 · Cited by 141
Self-citation
Metadata
- Authors
- Chia, N.-H., Gilyén, A., Li, T., Lin, H.-H., Tang, E., & Wang, C.
- Venue
- Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
- Publisher
- ACM
- Published
- 2020-06-22
- Pages
- 387-400
- OpenAlex
- W3034336799
- Cited by
- 99
- References
- 23
- FWCI
- 6.25
- Type
- conference paper
- Language
- en
- Open access
- bronze
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.