Information-Theoretic Bounds on Quantum Advantage in Machine Learning

作     者：Hsin-Yuan Huang Richard Kueng John Preskill 

作者机构：Institute for Quantum Information and Matter Caltech Pasadena California 91125 USA Department of Computing and Mathematical Sciences Caltech Pasadena California 91125 USA Institute for Integrated Circuits Johannes Kepler University Linz Linz 4040 Austria Walter Burke Institute for Theoretical Physics Caltech Pasadena California 91125 USA AWS Center for Quantum Computing Pasadena California 91125 USA 

出 版 物：《Physical Review Letters》 (物理评论快报)

年 卷 期：2021年第126卷第19期

页      面：190505-190505页

核心收录：

学科分类：07[理学] 0702[理学-物理学] 

基　　金：U.S. Department of Energy, USDOE J. Yang & Family Foundation Office of Science, SC National Science Foundation, NSF, (PHY-1733907, PHY-1733907) Advanced Scientific Computing Research, ASCR, (DE-NA0003525, DE-SC0020290) 

主　　题：Machine learning Quantum information processing 

摘      要：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.