An improved lower bound on query complexity for quantum PAC learning

DOI10.1016/J.IPL.2010.10.007MaRDI QIDQ1944033zbMATH OpenOpenAlexFDO

Authors 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 complexitylower boundprobably approximately correct learningquantum algorithmVC dimension

Mathematics Subject Classification ID

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

Recommendations

• Improved bounds on quantum learning algorithms
• Optimal quantum sample complexity of learning algorithms
• scientific article; zbMATH DE number 2090015
• Optimal quantum sample complexity of learning algorithms
• Quantum learning of concentrated Boolean functions

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
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 53945 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• scientific article; zbMATH DE number 799789 (Why is no real title available?)
• Improved bounds on quantum learning algorithms
• Introduction to algorithms
• Learnability and the Vapnik-Chervonenkis dimension
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Matrix Analysis
• Quantum Complexity Theory
• Quantum lower bounds by polynomials
• Rapid solution of problems by quantum computation

Cited in

(11)

• Sample size lower bounds in PAC learning by Algorithmic Complexity Theory
• Quantum learning of concentrated Boolean functions
• Learning bounds for quantum circuits in the agnostic setting
• Quantum machine learning: a classical perspective
• Optimal quantum sample complexity of learning algorithms
• Efficient and effective quantum compiling for entanglement-based machine learning on IBM Q devices
• scientific article; zbMATH DE number 2090015 (Why is no real title available?)
• Optimal quantum sample complexity of learning algorithms
• Learning quantum finite automata with queries
• scientific article; zbMATH DE number 7701523 (Why is no real title available?)
• Classical verification of quantum learning

This page was built for publication: An improved lower bound on query complexity for quantum PAC learning

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