6533b853fe1ef96bd12ac098

RESEARCH PRODUCT

Quantum Identification of Boolean Oracles

subject

description

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 bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is \(O(\sqrt{N {\rm log} M {\rm log} N}{\rm log log} M)\) for anyS 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 anyS 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 \(O(\sqrt{N/K})\), where K is a simple parameter determined by S.