Improved algorithms for quantum identification of Boolean oracles

DOI10.1016/J.TCS.2006.12.013zbMATH Open1118.68065OpenAlexW2082507052MaRDI QIDQ884445FDOQ884445

Authors Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, S. Yamasita

Publication date 6 June 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.12.013

zbMATH Keywords

query complexityquantum computingalgorithmic learning theory

Mathematics Subject Classification ID

Computational learning theory (68Q32) Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Recommendations

• Improved Algorithms for Quantum Identification of Boolean Oracles
• STACS 2004
• Quantum identification of Boolean oracles
• An optimal quantum algorithm for the oracle identification problem
• Boolean functions identification via quantum computing methods

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 2038718 (Why is no real title available?)
• scientific article; zbMATH DE number 2079317 (Why is no real title available?)
• scientific article; zbMATH DE number 2086396 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 1406119 (Why is no real title available?)
• scientific article; zbMATH DE number 1406120 (Why is no real title available?)
• Automata, Languages and Programming
• Computing with Noisy Information
• Improved bounds on quantum learning algorithms
• Property testing and its connection to learning and approximation
• Quantum Algorithms for Element Distinctness
• Quantum Complexity Theory
• Quantum algorithms for the triangle problem
• Quantum search of spatial regions
• STACS 2004
• STACS 2005
• Sublinear geometric algorithms
• The geometry of quantum learning
• The quantum query complexity of approximating the median and related statistics

Cited in

(12)

• Oracles with costs
• Query complexity of quantum biased oracles
• Quantum identification of Boolean oracles
• Recovering strings in oracles: quantum and classic
• Learning bounds for quantum circuits in the agnostic setting
• Quantum query complexity of almost all functions with fixed on-set size
• Improved Algorithms for Quantum Identification of Boolean Oracles
• STACS 2004
• An optimal quantum algorithm for the oracle identification problem
• RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
• Identifying generalized Reed-Muller codewords by quantum queries
• Exact quantum search by parallel unitary discrimination schemes

This page was built for publication: Improved algorithms for quantum identification of Boolean oracles

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