Name
Abstract | ||
|---|---|---|
The oracle identification problem (OIP) is, given a set S of M Boolean oracles out of 2(N) ones, to determine which oracle in S is the current black-box oracle. We can exploit the information that candidates of the current oracle is restricted to S. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. Our interest is in the quantum query complexity, for which we present several upper bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is O(rootN log M log N log log M) for any S such that M = \S\ > N, which is better than the obvious bound N if M < 2(N/log3) (N). (ii) It is O(rootN) for any S if \S\ = N, which includes the upper bound for the Grover search as a special case. (iii) For a wide range of oracles (\S\ = N) such as random oracles and balanced oracles, the query complexity is O(rootN/K), where K is a simple parameter determined by S. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/3-540-33133-6_1 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
quantum physics,random oracle,upper and lower bounds,computational complexity,upper bound | Boolean function,Log-log plot,Discrete mathematics,Combinatorics,Upper and lower bounds,Oracle,Quantum computer,Random oracle,Quantum walk,Quantum algorithm,Mathematics | Conference |
Volume | ISSN | Citations |
2996 | 0302-9743 | 18 |
PageRank | References | Authors |
0.99 | 27 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andris Ambainis | 1 | 2000 | 183.24 |
| Kazuo Iwama | 2 | 1400 | 153.38 |
| Akinori Kawachi | 3 | 185 | 20.66 |
| Hiroyuki Masuda | 4 | 18 | 0.99 |
| Raymond Putra | 5 | 24 | 1.80 |
| shigeru yamashita | 6 | 174 | 31.87 |