@inproceedings{457adf9ee3304404ac9bcffe33cb16e8,
title = "Improved algorithms for quantum identification of boolean oracles",
abstract = "The oracle identification problem (OIP) was introduced by Ambainis et al. [3]. 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: (i) For any oracle set S such that |S| ≤ 2Nd (d < 1), we design an algorithm whose query complexity is O(√N log M/log N), matching the lower bound proved in [3]. (ii) Our algorithm also works for the range between 2Nd and 2 N/logN (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 [2, 11, 18] for special cases of OIP.",
author = "Andris Ambainis and Kazuo Iwama and Akinori Kawachi and Rudy Raymond and Shigeru Yamashita",
year = "2006",
doi = "10.1007/11785293\_27",
language = "English",
isbn = "354035753X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "280--291",
booktitle = "Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings",
address = "Germany",
note = "10th Scandinavian Workshop on Algorithm Theory, SWAT 2006 ; Conference date: 06-07-2006 Through 08-07-2006",
}