Statistical Limits of Supervised Quantum Learning

Abstract

Within the framework of statistical learning theory it is possible to bound the minimum number of samples required by a learner to reach a target accuracy. We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning---for which statistical guarantees are available---cannot achieve polylogarithmic runtimes in the input dimension. We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most polynomial speedups over efficient classical algorithms, even in cases where quantum access to the data is naturally available.

arXiv commentv3: 6 pages, journal version, title changed (previous title "The Statistical Limits of Supervised Quantum Learning"), other minor improvements; v2: 6 pages, title changed (previous title "Fast quantum learning with statistical guarantees"), format changed to two-columns, typos corrected, remarks that better clarify the limitations of our analysis added

References in corpus (15)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum-enhanced measurements: beating the standard quantum limit
• Quantum metrology
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum Data Fitting
• Quantum machine learning: a classical perspective
• Prediction by linear regression on a quantum computer
• Quantum gradient descent for linear systems and least squares
• Quantum Algorithm for Linear Regression
• Hamiltonian Simulation with Optimal Sample Complexity
• Learning with Errors is easy with quantum samples
• Exploiting Faraday Rotation to Jam Quantum Key Distribution via Polarized Photons
• State-Independent Quantum Key Distribution with Two-Way Classical Communication

Cited by in corpus (5)

• The effect of data encoding on the expressive power of variational quantum machine learning models
• Biology and medicine in the landscape of quantum advantages
• On the Quantum versus Classical Learnability of Discrete Distributions
• Benchmarking Machine Learning Algorithms for Adaptive Quantum Phase Estimation with Noisy Intermediate-Scale Quantum Sensors
• The Inductive Bias of Quantum Kernels