Performance measurement and data base design
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
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.
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003
David S. Kung
DAC 1998
Khaled A.S. Abdel-Ghaffar
IEEE Trans. Inf. Theory