dorsal/arxiv
View SchemaQuantum Identification of Boolean Oracles
| Authors | Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0403056 |
| URL | https://arxiv.org/abs/quant-ph/0403056 |
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 and lower bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is $O(\sqrt{N\log M \log N}\log\log M)$ for {\it any} $S$ such that $M = |S| > N$, which is better than the obvious bound $N$ if $M < 2^{N/\log^{3}N}$. (ii) It is $O(\sqrt{N})$ for {\it 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 $\Theta(\sqrt{N/K})$, where $K$ is a simple parameter determined by $S$.
{
"annotation_id": "a354ff29-c7e6-493f-bc6f-8bd1d6b5ef88",
"date_created": "2026-03-02T18:02:06.511000Z",
"date_modified": "2026-03-02T18:02:06.511000Z",
"file_hash": "303f32a2fac63b9bc4c3133d377073102c17141d796e0304090d286237664008",
"private": false,
"record": {
"abstract": "The oracle identification problem (OIP) is, given a set $S$ of $M$ Boolean\noracles out of $2^{N}$ ones, to determine which oracle in $S$ is the current\nblack-box oracle. We can exploit the information that candidates of the current\noracle is restricted to $S$. The OIP contains several concrete problems such as\nthe original Grover search and the Bernstein-Vazirani problem. Our interest is\nin the quantum query complexity, for which we present several upper and lower\nbounds. They are quite general and mostly optimal: (i) The query complexity of\nOIP is $O(\\sqrt{N\\log M \\log N}\\log\\log M)$ for {\\it any} $S$ such that $M =\n|S| \u003e N$, which is better than the obvious bound $N$ if $M \u003c 2^{N/\\log^{3}N}$.\n(ii) It is $O(\\sqrt{N})$ for {\\it any} $S$ if $|S| = N$, which includes the\nupper bound for the Grover search as a special case. (iii) For a wide range of\noracles ($|S| = N$) such as random oracles and balanced oracles, the query\ncomplexity is $\\Theta(\\sqrt{N/K})$, where $K$ is a simple parameter determined\nby $S$.",
"arxiv_id": "quant-ph/0403056",
"authors": [
"Andris Ambainis",
"Kazuo Iwama",
"Akinori Kawachi",
"Hiroyuki Masuda",
"Raymond H. Putra",
"Shigeru Yamashita"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Quantum Identification of Boolean Oracles",
"url": "https://arxiv.org/abs/quant-ph/0403056"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cb7f341c-1a13-4bef-8793-40bb52ed54ff",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}