Can small quantum systems learn
Open accessAbstract
We examine the question of whether quantum mechanics places limitations on the ability of small quantum devices to learn. We specifically examine the question in the context of Bayesian inference, wherein the prior and posterior distributions are encoded in the quantum state vector. We conclude based on lower bounds from Grover’s search that an efficient blackbox method for updating the distribution is impossible. We then address this by providing a new adaptive form of approximate quantum Bayesian inference that is polynomially faster than its classical anolog and tractable if the quantum system is augmented with classical memory or if the low–order moments of the distribution are protected through redundant preparation. This work suggests that there may be a connection between fault tolerance and the capacity of a quantum system to learn from its surroundings.
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
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?
Sufficiently powerful quantum computers can in principle provide computational speedups for key machine learning algorithms and subroutines such as data fitting, principal component analysis, Bayesian inference, Monte Carlo methods, support vector machines, Boltzmann machines, and recommendation systems.
“Sufficiently powerful quantum computers can in principle provide computational speedups for key machine learning algorithms and subroutines such as data fitting [4], principal component analysis [5], Bayesian inference [6,7], Monte Carlo methods [8], support vector machines [9,10], Boltzmann machines [11,12], and recommendation systems [13].”
From Continuous-variable quantum neural networks (2019) · cites this paper as [7]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
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 principal component analysis
Lloyd, S., Mohseni, M., & Rebentrost, P. (2014) · Nature Physics · doi:10.1038/nphys3029 · Cited by 1,385 · see citing works
Flagged first, then by citations
Research works printed but not linked: 26
- P. W. Shor, in Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on (IEEE, 1994) pp. 124-134.
- S. Lloyd et al., Science 273, 1073 (1996). · DOI · Paper page
- A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (ACM, 2003) pp. 59-68.
- S. Aaronson, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 463, 3089 (2007). · DOI
- C. E. Granade, C. Ferrie, N. Wiebe, and D. G. Cory, New Journal of Physics 14, 103013 (2012). · DOI
- C. Ferrie and C. E. Granade, Physical Review Letters 112, 130402 (2014). · DOI
- E. Aïmeur, G. Brassard, and S. Gambs, in Advances in Artificial Intelligence (Springer, 2006) pp. 431-442.
- N. Wiebe, A. Kapoor, and K. M. Svore, arXiv preprint arXiv:1412.3489 (2014). · arXiv
- N. Wiebe, A. Kapoor, and K. Svore, arXiv preprint arXiv:1401.2142 (2014). · arXiv
- S. Lloyd, M. Mohseni, and P. Rebentrost, arXiv preprint arXiv:1307.0411 (2013). · arXiv
- S. Boixo, G. Ortiz, and R. Somma, The European Physical Journal Special Topics 224, 35 (2015).
- G. H. Low, T. J. Yoder, and I. L. Chuang, Physical Review A 89, 062315 (2014). · DOI · Paper page
- M. Ozols, M. Roetteler, and J. Roland, ACM Transactions on Computation Theory (TOCT) 5, 11 (2013).
- G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Contemporary Mathematics 305, 53 (2002).
- L. K. Grover, in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (ACM, 1996) pp. 212-219.
- M. Boyer, G. Brassard, P. Høyer, and A. Tapp, arXiv preprint quant-ph/9605034 (1996). · arXiv
- P. Dagum and M. Luby, Artificial Intelligence 60, 141 (1993). · DOI
- J. Liu and M. West, in Sequential Monte Carlo Methods in Practice, edited by D. Freitas and N. Gordon (Springer-Verlag, New York, 2001).
- T. P. Minka, in Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence (Morgan Kaufmann Publishers Inc., 2001) pp. 362-369.
- R. Van Der Merwe, A. Doucet, N. De Freitas, and E. Wan, in NIPS (2000) pp. 584-590.
- L. Grover and T. Rudolph, arXiv preprint quant-ph/0208112 (2002). · arXiv
- N. Wiebe, C. Granade, A. Kapoor, and K. M. Svore, arXiv preprint arXiv:1511.06458 (2015). · arXiv
- D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer, arXiv preprint arXiv:1506.05135 (2015). · arXiv
- G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, arXiv preprint quant-ph/0005055 (2000). · arXiv
- N. Wiebe, C. Granade, C. Ferrie, and D. Cory, Physical Review Letters 112, 190501 (2014). · DOI
- M. Isard and A. Blake, International Journal of Computer Vision 29, 5 (1998). · DOI · Paper page
Cited by
Sorted by citations
Continuous-variable quantum neural networks
Killoran, N., Bromley, T. R., Arrazola, J. M., Schuld, M., Quesada, N., & Lloyd, S. (2019) · Physical Review Research · doi:10.1103/physrevresearch.1.033063 · Cited by 418 · see citing works
- Authors
- Wiebe, N., & Grandade, C.
- ORCID
- Wiebe, Nathan
- Venue
- Quantum Information and Computation
- Publisher
- Rinton Press
- Published
- 2017-05
- Volume
- 17
- Issue
- 7&8
- Pages
- 568-594
- ISSN
- 1533-7146 (ISSN-L)
- OpenAlex
- W2191638898
- Cited by
- 26
- References
- 2
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 1 · 2023: 2 · 2022: 3 · 2021: 3 · 2020: 4 · 2019: 3 · 2018: 4 · 2017: 3 · 2016: 1
- FWCI
- 2.25
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Quantum Information and Computation (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- 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 Mechanics and Applications
- Keywords
- quantum machine learning, Bayesian inference, Grover's algorithm, lower bounds, black-box learning, adaptive learning, fault tolerance, small quantum systems
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
