Quantum Identification of Boolean Oracles

Abstract

The 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 $\Theta (\sqrt{N/K})$, where $K$ is a simple parameter determined by $S$.

11 pages, 4 figures, to appear in Proceedings of STACS 2004