Improved bounds on quantum learning algorithms

DOI10.1007/s11128-005-0001-2zbMath1130.81018arXivquant-ph/0411140MaRDI QIDQ2491374

Rocco A. Servedio, Alp Atıcı

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 theory; quantum computation; PAC learning; Quantum query algorithms

Mathematics Subject Classification ID

68Q32: Computational learning theory

68T05: Learning and adaptive systems in artificial intelligence

81P68: Quantum computation

Related Items

Improved algorithms for quantum identification of Boolean oracles, The geometry of quantum learning, An improved lower bound on query complexity for quantum PAC learning, Quantum algorithms for learning and testing juntas

Cites Work

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