A Caltech Library Service

Information-Theoretic Bounds on Quantum Advantage in Machine Learning

Huang, Hsin-Yuan and Kueng, Richard and Preskill, John (2021) Information-Theoretic Bounds on Quantum Advantage in Machine Learning. Physical Review Letters, 126 (19). Art. No. 190505. ISSN 0031-9007. doi:10.1103/PhysRevLett.126.190505.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
Creative Commons Attribution.

[img] PDF (complete proofs for the main theorems, a discussion of related works, and the details of numerical experiments) - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter x and involve execution of a (possibly unknown) quantum process E. Our figure of merit is the number of runs of E required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of E, and quantum ML models that can access E coherently to acquire quantum data; the classical or quantum data are then used to predict the outcomes of future experiments. We prove that for any input distribution D(x), a classical ML model can provide accurate predictions on average by accessing E a number of times comparable to the optimal quantum ML model. In contrast, for achieving an accurate prediction on all inputs, we prove that the exponential quantum advantage is possible. For example, to predict the expectations of all Pauli observables in an n-qubit system ρ, classical ML models require 2^(Ω(n)) copies of ρ, but we present a quantum ML model using only O(n) copies. Our results clarify where the quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Huang, Hsin-Yuan0000-0001-5317-2613
Kueng, Richard0000-0002-8291-648X
Preskill, John0000-0002-2421-4762
Additional Information:© 2021 American Physical Society. Received 12 January 2021; revised 17 March 2021; accepted 2 April 2021; published 14 May 2021. The authors thank Victor Albert, Sitan Chen, Jerry Li, Seth Lloyd, Jarrod McClean, Spiros Michalakis, Yuan Su, and Thomas Vidick for valuable input and inspiring discussions. We would also like to thank anonymous reviewers for in-depth comments and suggestions. H. H. is supported by the J. Yang & Family Foundation. J. P. acknowledges funding from the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, (Grants No. DE-NA0003525 and No. DE-SC0020290), and the National Science Foundation (Grant No. PHY-1733907). The Institute for Quantum Information and Matter is a NSF Physics Frontiers Center.
Group:Institute for Quantum Information and Matter, Walter Burke Institute for Theoretical Physics, AWS Center for Quantum Computing
Funding AgencyGrant Number
J. Yang Family and FoundationUNSPECIFIED
Department of Energy (DOE)DE-NA0003525
Department of Energy (DOE)DE-SC0020290
Issue or Number:19
Record Number:CaltechAUTHORS:20210512-104048123
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109099
Deposited By: George Porter
Deposited On:12 May 2021 19:23
Last Modified:14 May 2021 20:53

Repository Staff Only: item control page