A Survey of Quantum Learning Theory
arXiv:1701.06806
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.
arXiv comment26 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
References in corpus (14)
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Quantum support vector machine for big data classification
- Strengths and Weaknesses of Quantum Computing
- Quantum principal component analysis
- Quantum algorithms for supervised and unsupervised machine learning
- Reversing quantum dynamics with near-optimal quantum and classical fidelity
- Sample-optimal tomography of quantum states
- Quantum Perceptron Models
- Quantum Recommendation Systems
- Classical computing, quantum computing, and Shor's factoring algorithm
- Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions
- Advances in quantum machine learning
- An optimal quantum algorithm for the oracle identification problem
Cited by in corpus (20)
- Quantum Machine Learning
- Noisy intermediate-scale quantum (NISQ) algorithms
- Quantum machine learning: a classical perspective
- The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
- Learning with Errors is easy with quantum samples
- Benchmarking neural networks for quantum computation
- Machine learning \& artificial intelligence in the quantum domain
- Inductive supervised quantum learning
- New Trends in Quantum Machine Learning
- Sublinear quantum algorithms for training linear and kernel-based classifiers
- Optimal Quantum Sample Complexity of Learning Algorithms
- Quantum statistical query learning
- Quantum exploration algorithms for multi-armed bandits
- Quantum Semi-Supervised Kernel Learning
- Two new results about quantum exact learning
- Variational quantum simulation of long-range interacting systems
- Generative Invertible Quantum Neural Networks
- Improved Quantum Boosting
- Quantum Spectral Clustering through a Biased Phase Estimation Algorithm
- Quantum Learning Algorithms and Post-Quantum Cryptography