An improved lower bound on query complexity for quantum PAC learning

DOI10.1016/j.ipl.2010.10.007zbMath1260.68192OpenAlexW2009381781MaRDI QIDQ1944033

Chi Zhang

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.10.007

zbMATH Keywords

computational complexityVC dimensionlower boundquantum algorithmprobably approximately correct learning

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Quantum machine learning: a classical perspective, Learning bounds for quantum circuits in the agnostic setting, Learning quantum finite automata with queries, Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices, Unnamed Item, Quantum learning of concentrated Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A general lower bound on the number of examples needed for learning
• Improved bounds on quantum learning algorithms
• Learnability and the Vapnik-Chervonenkis dimension
• Matrix Analysis
• A theory of the learnable
• Rapid solution of problems by quantum computation
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Quantum Complexity Theory
• Equivalences and Separations Between Quantum and Classical Learnability
• Quantum lower bounds by polynomials