Statistical Limits of Supervised Quantum Learning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningLearning TheoryQuantum Machine LearningSimilar Papers 제목 키워드 기반
Ultimate Limits of Thermal Pattern Recognition
Quantum Channel Discrimination (QCD) presents a fundamental task in quantum information theory, with critical applications in quantum reading, illumination, data-readout and more. The extension to multiple quantum channe…
image-classificationImage ClassificationLearnability of the output distributions of local quantum circuits
There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approxima…
Statistical Complexity of Quantum Learning
Recent years have seen significant activity on the problem of using data for the purpose of learning properties of quantum systems or of processing classical or quantum data via quantum computing. As in classical learnin…
Learning TheoryAdversarial Limits of Quantum Certification: When Eve Defeats Detection
Security of quantum key distribution (QKD) relies on certifying that observed correlations arise from genuine quantum entanglement rather than eavesdropper manipulation. Theoretical security proofs assume idealized condi…
Quantum Computing Methods for Supervised Learning
The last two decades have seen an explosive growth in the theory and practice of both quantum computing and machine learning. Modern machine learning systems process huge volumes of data and demand massive computational …
BIG-bench Machine Learning