A Survey of Quantum Learning Theory

2017/01/24 by Srinivasan Arunachalam, Arunachalam, Srinivasan, Ronald de Wolf +1 · 9 citations
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #cs.LG #quant-ph

paper · pdf · doi:10.48550/arxiv.1701.06806

26 pages LaTeX. v2: many small changes to improve the presentation. This version will appear as Complexity Theory Column in SIGACT News in June 2017. v3: fixed a small ambiguity in the definition of gamma(C) and updated a reference

openalex publication_date 2017/01/24 · arxiv created 2017/07/28 · arxiv updated 2017/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper surveys quantum learning theory: the theoretical aspects of machine learning using quantum computers. We describe the main results known for three models of learning: exact learning from membership queries, and Probably Approximately Correct (PAC) and agnostic learning from classical or quantum examples.

Citations

• Quantum algorithms for supervised and unsupervised machine learning
• Strengths and Weaknesses of Quantum Computing
• Quantum mechanical computers
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Quantum support vector machine for big data classification
• On the Power of Quantum Computation
• Simulating physics with computers
• Quantum Perceptron Models
• Quantum Recommendation Systems
• Quantum Machine Learning

Cited by

• Hybrid Quantum-Classical Selective State Space Artificial Intelligence
• Enhancing the reachability of variational quantum algorithms via input-state design
• Data Complexity: a threshold between Classical and Quantum Machine Learning -- Part I
• Quantum statistical query learning
• Pushing the Limits of LLMs in Quantum Operations
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum Spectral Clustering through a Biased Phase Estimation Algorithm
• Improved Quantum Boosting
• Optimal entanglement witness of multipartite systems using support vector machine approach

Related

• An introduction to quantum machine learning
• A Quick Introduction to Quantum Machine Learning for Non-Practitioners
• Quantum machine learning for data scientists
• Quantum Machine Learning
• Quantum Computing Methods for Supervised Learning