← Back to papers
Fast quantum learning with statistical guarantees
C. Ciliberto, Andrea Rocchetto, Alessandro Rudi, Leonard Wossnig·January 28, 2020
PhysicsComputer ScienceMathematics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
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 which statistical guarantees are available -- cannot achieve polylogarithmic runtimes in the input dimension. This calls for a careful revaluation of quantum speedups for learning problems, even in cases where quantum access to the data is naturally available.