Robust Quantum Algorithms for Oracle Identification

Details Robust Quantum Algorithms for Oracle Identification Robust Quantum Algorithms for Oracle Identification

2004-11-30

arxiv.org/abs/quant-ph/0411204v5

Physics

Quantum Physics

Presentation is improved

Scientific paper

The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set $S$ of $M$ oracles and a blackbox oracle $f$. Our task is to figure out which oracle in $S$ is equal to the blackbox $f$ by making queries to $f$. OIP includes several problems such as the Grover Search as special cases. In this paper, we improve the algorithms in \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: ($i$) For any oracle set $S$ such that $|S| \le 2^{N^d}$ ($d < 1$), we design an algorithm whose query complexity is $O(\sqrt{N\log{M}/\log{N}})$, matching the lower bound proved in \cite{AIKMRY04}. ($ii$) Our algorithm also works for the range between $2^{N^d}$ and $2^{N/\log{N}}$ (where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. ($iii$) Our algorithm is robust, namely, it exhibits the same performance (up to a constant factor) against the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.

Affiliated with

Also associated with

No associations

Rating

Robust Quantum Algorithms for Oracle Identification 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 Robust Quantum Algorithms for Oracle Identification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust Quantum Algorithms for Oracle Identification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-14353