Physics – Quantum Physics
Scientific paper
2004-03-07
Physics
Quantum Physics
11 pages, 4 figures, to appear in Proceedings of STACS 2004
Scientific paper
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$.
Ambainis Andris
Iwama Kazuo
Kawachi Akinori
Masuda Hiroyuki
Putra Raymond H.
No associations
LandOfFree
Quantum Identification of Boolean Oracles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Identification of Boolean Oracles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Identification of Boolean Oracles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-236046