Improved algorithms for quantum identification of Boolean oracles

DOI10.1016/j.tcs.2006.12.013zbMath1118.68065OpenAlexW2082507052MaRDI QIDQ884445

Rudy Raymond, Andris Ambainis, Akinori Kawachi, Kazuo Iwama, Shigeru Yamashita

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

quantum computingquery complexityalgorithmic 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)

Related Items (5)

Quantum query complexity of almost all functions with fixed on-set size ⋮ Learning bounds for quantum circuits in the agnostic setting ⋮ Exact quantum search by parallel unitary discrimination schemes ⋮ Identifying Generalized Reed-Muller Codewords by Quantum Queries ⋮ RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC

Cites Work

• The geometry of quantum learning
• Improved bounds on quantum learning algorithms
• The quantum query complexity of approximating the median and related statistics
• Property testing and its connection to learning and approximation
• Sublinear geometric algorithms
• Computing with Noisy Information
• Quantum Complexity Theory
• STACS 2004
• Quantum Algorithms for Element Distinctness
• Automata, Languages and Programming
• STACS 2005
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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