2026-07-22T03:56:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4481 2024-03-06T10:35:06Z ddc:004 open_access

An optimal quantum algorithm for the oracle identification problem Kothari, Robin quantum algorithms quantum query complexity oracle identification In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al. The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robin Kothari 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.482 urn:nbn:de:0030-drops-44813 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.482 eng https://creativecommons.org/licenses/by/3.0/legalcode