Quantum Identification of Boolean Oracles
<|reference_start|>Quantum Identification of Boolean Oracles: 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$.<|reference_end|>
@article{ambainis2004quantum,
    title={Quantum Identification of Boolean Oracles},
    author={Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda,
  Raymond H. Putra and Shigeru Yamashita},
    journal={arXiv preprint arXiv:quant-ph/0403056},
    year={2004},
    archivePrefix={arXiv},
    eprint={quant-ph/0403056},
    primaryClass={quant-ph cs.CC}
}