dorsal/arxiv
View SchemaRobust Quantum Algorithms for Oracle Identification
| Authors | Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, Shigeru Yamashita |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0411204 |
| URL | https://arxiv.org/abs/quant-ph/0411204 |
Abstract
The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. 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 \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: ($i$) For any oracle set $S$ such that $|S| \le 2^{N^d}$ ($d < 1$), we design an algorithm whose query complexity is $O(\sqrt{N\log{M}/\log{N}})$, matching the lower bound proved in \cite{AIKMRY04}. ($ii$) Our algorithm also works for the range between $2^{N^d}$ and $2^{N/\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 the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.
{
"annotation_id": "a6defda2-7787-4d50-803a-ec3088f40458",
"date_created": "2026-03-02T18:02:13.630000Z",
"date_modified": "2026-03-02T18:02:13.630000Z",
"file_hash": "5e01e4565c2cb5318e1e9b50b04639303e696180abc01bf0ea8069a2a2a96adf",
"private": false,
"record": {
"abstract": "The oracle identification problem (OIP) was introduced by Ambainis et al.\n\\cite{AIKMRY04}. It is given as a set $S$ of $M$ oracles and a blackbox oracle\n$f$. Our task is to figure out which oracle in $S$ is equal to the blackbox $f$\nby making queries to $f$. OIP includes several problems such as the Grover\nSearch as special cases. In this paper, we improve the algorithms in\n\\cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity\nfor this problem: ($i$) For any oracle set $S$ such that $|S| \\le 2^{N^d}$ ($d\n\u003c 1$), we design an algorithm whose query complexity is\n$O(\\sqrt{N\\log{M}/\\log{N}})$, matching the lower bound proved in\n\\cite{AIKMRY04}. ($ii$) Our algorithm also works for the range between\n$2^{N^d}$ and $2^{N/\\log{N}}$ (where the bound becomes O(N)), but the gap\nbetween the upper and lower bounds worsens gradually. ($iii$) Our algorithm is\nrobust, namely, it exhibits the same performance (up to a constant factor)\nagainst the noisy oracles as also shown in the literatures\n\\cite{AC02,BNRW03,HMW03} for special cases of OIP.",
"arxiv_id": "quant-ph/0411204",
"authors": [
"Andris Ambainis",
"Kazuo Iwama",
"Akinori Kawachi",
"Rudy Raymond",
"Shigeru Yamashita"
],
"categories": [
"quant-ph"
],
"title": "Robust Quantum Algorithms for Oracle Identification",
"url": "https://arxiv.org/abs/quant-ph/0411204"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d8fc4164-6238-40c9-a42d-25c5d5c633c2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}