Reena Elangovan, Shubham Jain, et al.
ACM TODAES
The oracle identification problem (OIP) was introduced by Ambainis et al. [A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R.H. Putra, S. Yamashita, Quantum identification of boolean oracles, in: Proc. of STACS'04, in: LNCS, vol. 2996, 2004, pp. 105-116]. 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 [A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R.H. Putra, S. Yamashita, Quantum identification of boolean oracles, in: Proc. of STACS'04, in: LNCS, vol. 2996, 2004, pp. 105-116] by providing a mostly optimal upper bound of query complexity for this problem: (i) For any oracle set S such that | S | ≤ 2Nd (d < 1), we design an algorithm whose query complexity is O (sqrt(N log M / log N)), matching the lower bound proved in [A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R.H. Putra, S. Yamashita, Quantum identification of boolean oracles, in: Proc. of STACS'04, in: LNCS, vol. 2996, 2004, pp. 105-116]. (ii) Our algorithm also works for the range between 2Nd and 2N / 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 noisy oracles as also shown in the literature [M. Adcock, R. Cleve, A quantum Goldreich-Levin theorem with cryptographic applications, in: Proc. of STACS'02, in: LNCS, vol. 2285, 2002, pp. 323-334; H. Buhrman, I. Newman, H. Röhrig, R. deWolf, Robust quantum algorithms and polynomials, in: Proc. of STACS'05, in: LNCS, vol. 3404, 2005, pp. 593-604; P. Høyer, M. Mosca, R. de Wolf, Quantum search on bounded-error inputs, in: Proc. of ICALP'03, in: LNCS, vol. 2719, 2003, pp. 291-299] for special cases of OIP. © 2006 Elsevier Ltd. All rights reserved.
Reena Elangovan, Shubham Jain, et al.
ACM TODAES
Zohar Feldman, Avishai Mandelbaum
WSC 2010
Rajeev Gupta, Shourya Roy, et al.
ICAC 2006
Elliot Linzer, M. Vetterli
Computing