About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theoretical Computer Science
Paper
Improved algorithms for quantum identification of Boolean oracles
Abstract
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.