RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
From MaRDI portal
Publication:5495415
DOI10.1142/S0129054113400261zbMath1293.68170OpenAlexW2025667057MaRDI QIDQ5495415
Harumichi Nishimura, Kazuo Iwama
Publication date: 4 August 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054113400261
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)
Cites Work
- Randomized group testing for mutually obscuring defectives
- On the power of Ambainis lower bounds
- Quantum counterfeit coin problems
- Improved algorithms for quantum identification of Boolean oracles
- Improved bounds on quantum learning algorithms
- Reconstructing Strings from Substrings with Quantum Queries
- Quantum Query Complexity of Boolean Functions with Small On-Sets
- Quantum Complexity Theory
- Strengths and Weaknesses of Quantum Computing
- Equivalences and Separations Between Quantum and Classical Learnability
- Quantum lower bounds by polynomials
- Quantum lower bounds by quantum arguments