Improved bounds on quantum learning algorithms

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

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 theoryquantum computationPAC learningQuantum query algorithms

Mathematics Subject Classification ID

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

Related Items (11)

Quantum machine learning: a classical perspective ⋮ Improved algorithms for quantum identification of Boolean oracles ⋮ Learning bounds for quantum circuits in the agnostic setting ⋮ An improved lower bound on query complexity for quantum PAC learning ⋮ Quantum algorithms for learning and testing juntas ⋮ The geometry of quantum learning ⋮ Quantum Algorithms for Classical Probability Distributions ⋮ Unnamed Item ⋮ RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC ⋮ Quantum learning of concentrated Boolean functions ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound

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

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