Quantum Identification of Boolean Oracles

Simple item page
dc.creatorAmbainis, Andris
dc.creatorIwama, Kazuo
dc.creatorKawachi, Akinori
dc.creatorMasuda, Hiroyuki
dc.creatorPutra, Raymond H.
dc.creatorYamashita, Shigeru
dc.date2004-03-07
dc.date.accessioned2026-07-07T06:09:15Z
dc.date.available2026-07-07T06:09:15Z
dc.descriptionThe oracle identification problem (OIP) is, given a set $S$ of $M$ Boolean oracles out of $2^{N}$ ones, to determine which oracle in $S$ is the current black-box oracle. We can exploit the information that candidates of the current oracle is restricted to $S$. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. Our interest is in the quantum query complexity, for which we present several upper and lower bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is $O(\sqrt{N\log M \log N}\log\log M)$ for {\it any} $S$ such that $M = |S| > N$, which is better than the obvious bound $N$ if $M < 2^{N/\log^{3}N}$. (ii) It is $O(\sqrt{N})$ for {\it any} $S$ if $|S| = N$, which includes the upper bound for the Grover search as a special case. (iii) For a wide range of oracles ($|S| = N$) such as random oracles and balanced oracles, the query complexity is $Θ(\sqrt{N/K})$, where $K$ is a simple parameter determined by $S$.
dc.description11 pages, 4 figures, to appear in Proceedings of STACS 2004
dc.identifierhttps://arxiv.org/abs/quant-ph/0403056
dc.identifierhttp://arxiv.org/abs/quant-ph/0403056
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/91897
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleQuantum Identification of Boolean Oracles
dc.typetext

Files

Collections

arXiv