Improved Bounds on Quantum Learning Algorithms

Abstract

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples. Hunziker et al. conjectured that for any class C of Boolean functions, the number of quantum black-box queries which are required to exactly identify an unknown function from C is $O(\frac{\log |C|}{\sqrt{{\hat{\gamma }}^C}})$, where ${\hat{\gamma }}^C$ is a combinatorial parameter of the class C. We essentially resolve this conjecture in the affirmative by giving a quantum algorithm that, for any class C, identifies any unknown function from C using $O(\frac{\log |C|\log \log |C|}{\sqrt{{\hat{\gamma }}^C}})$ quantum black-box queries. We consider a range of natural problems intermediate between the exact learning problem (in which the learner must obtain all bits of information about the black-box function) and the usual problem of computing a predicate (in which the learner must obtain only one bit of information about the black-box function). We give positive and negative results on when the quantum and classical query complexities of these intermediate problems are polynomially related to each other. Finally, we improve the known lower bounds on the number of quantum examples (as opposed to quantum black-box queries) required for $(\epsilon ,\delta )$-PAC learning any concept class of Vapnik-Chervonenkis dimension d over the domain $\{0,1{\}}^n$ from $\Omega (\frac{d}{n})$ to $\Omega (\frac{1}{\epsilon }\log \frac{1}{\delta }+d+\frac{\sqrt{d}}{\epsilon })$. This new lower bound comes closer to matching known upper bounds for classical PAC learning.

Minor corrections. 18 pages. To appear in Quantum Information Processing. Requires: algorithm.sty, algorithmic.sty to build

References in corpus (5)

• Strengths and Weaknesses of Quantum Computing
• Tight bounds on quantum searching
• A Limit on the Speed of Quantum Computation in Determining Parity
• Quantum Lower Bounds by Polynomials
• Robust Quantum Algorithms for Oracle Identification

Cited by in corpus (22)

• Quantum machine learning: a classical perspective
• Quantum learning robust to noise
• Learning with Errors is easy with quantum samples
• Quantum Algorithms for Learning and Testing Juntas
• Quantum learning by measurement and feedback
• Certainty and Uncertainty in Quantum Information Processing
• Optimal Quantum Sample Complexity of Learning Algorithms
• Efficient and Effective Quantum Compiling for Entanglement-based Machine Learning on IBM Q Devices
• Quantum statistical query learning
• The speed of quantum and classical learning for performing the k-th root of NOT
• Robust Quantum Algorithms for Oracle Identification
• Quantum Coupon Collector
• Optimal lower bounds for Quantum Learning via Information Theory
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• Learning Quantum Processes with Quantum Statistical Queries
• Quantum circuit-like learning: A fast and scalable classical machine-learning algorithm with similar performance to quantum circuit learning
• Quantum Communication-Query Tradeoffs
• The Learnability of Unknown Quantum Measurements
• Quantum algorithms for learning a hidden graph and beyond
• Quantum search of partially ordered sets
• Quantum Learning Theory Beyond Batch Binary Classification