Improved bounds on quantum learning algorithms

DOI10.1007/S11128-005-0001-2MaRDI QIDQ2491374zbMATH OpenOpenAlexFDO

Authors Alp Atıcı, Rocco A. Servedio

Publication date 29 May 2006

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0411140

zbMATH Keywords

computational learning theoryPAC learningquantum computationQuantum query algorithms

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Quantum computation (81P68)

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(fraclog|C|sqrt{hatgamma}^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(fraclog|C|loglog|C|sqrt{hatgamma}^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(fracdn)$ to $Omega(frac1epsilonlogfrac1delta+d+fracsqrtdepsilon)$. This new lower bound comes closer to matching known upper bounds for classical PAC learning.

Recommendations

• Equivalences and Separations Between Quantum and Classical Learnability
• Optimal quantum sample complexity of learning algorithms
• Optimal quantum sample complexity of learning algorithms
• How Many Query Superpositions Are Needed to Learn?
• scientific article; zbMATH DE number 2090015

Cites work

• A general lower bound on the number of examples needed for learning
• A theory of the learnable
• Equivalences and Separations Between Quantum and Classical Learnability
• How many queries are needed to learn?
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• On the Power of Quantum Computation
• Oracles and queries that are sufficient for exact learning
• Quantum Complexity Theory
• Rapid solution of problems by quantum computation
• STACS 2004
• Strengths and Weaknesses of Quantum Computing
• The geometry of quantum learning

Cited in

(27)

• An improved lower bound on query complexity for quantum PAC learning
• Quantum learning of concentrated Boolean functions
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Quantum algorithms for learning and testing juntas
• Quantum learning Boolean linear functions w.r.t. product distributions
• Quantum algorithms for the Goldreich-Levin learning problem
• Learning bounds for quantum circuits in the agnostic setting
• How Many Query Superpositions Are Needed to Learn?
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• scientific article; zbMATH DE number 1754656 (Why is no real title available?)
• Quantum machine learning: a classical perspective
• Optimal quantum sample complexity of learning algorithms
• Equivalences and Separations Between Quantum and Classical Learnability
• scientific article; zbMATH DE number 2090015 (Why is no real title available?)
• Quantum hardness of learning shallow classical circuits
• Quantum Algorithms for Classical Probability Distributions
• Two new results about quantum exact learning
• Optimal quantum sample complexity of learning algorithms
• Quantum algorithms and approximating polynomials for composed functions with shared inputs
• RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
• scientific article; zbMATH DE number 7651037 (Why is no real title available?)
• Solving the learning parity with noise problem using quantum algorithms
• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
• Fat shattering, joint measurability, and PAC learnability of POVM hypothesis classes
• Classical verification of quantum learning
• Improved algorithms for quantum identification of Boolean oracles
• The geometry of quantum learning

This page was built for publication: Improved bounds on quantum learning algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2491374)