The oracle identification problem (OIP) was introduced by Ambainis et al.. 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 black-box 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 [3] by providing a mostly optimal upper bound of query complexity for this problem: (ⅰ) For any oracle set S such that ∣S∣ ≤ 2~(N~d) (d < 1), we design an algorithm whose query complexity is O((N log M/log N)~(1/2)), matching the lower bound proved in [3]. (ⅱ) 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. (ⅲ) 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 for special cases of OIP.
展开▼
