RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC

DOI10.1142/S0129054113400261MaRDI QIDQ5495415zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

quantum computingquery complexitystring recovery

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Quantum computation (81P68)

Recommendations

• Recovering strings in oracles: quantum and classic
• Reconstructing strings from substrings with quantum queries
• Near-optimal quantum algorithms for string problems
• ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• New binding-concealing trade-offs for quantum string commitment
• QUANTUM-CLASSICAL CORRESPONDENCE IN THE ORACLE MODEL OF COMPUTATION
• Classical vs quantum random oracles
• Quantum algorithms for string processing
• An optimal quantum algorithm for the oracle identification problem

Cites work

• Equivalences and Separations Between Quantum and Classical Learnability
• Improved algorithms for quantum identification of Boolean oracles
• Improved bounds on quantum learning algorithms
• On the power of Ambainis lower bounds
• Quantum Complexity Theory
• Quantum counterfeit coin problems
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum Query Complexity of Boolean Functions with Small On-Sets
• Randomized group testing for mutually obscuring defectives
• Reconstructing strings from substrings with quantum queries
• Strengths and Weaknesses of Quantum Computing

Cited in

(2)

• Reconstructing strings from substrings with quantum queries
• Recovering strings in oracles: quantum and classic

This page was built for publication: RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC

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