dorsal/arxiv
View SchemaA Comparison of Quantum Oracles
| Authors | Elham Kashefi, Adrian Kent, Vlatko Vedral, Konrad Banaszek |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0109104 |
| URL | https://arxiv.org/abs/quant-ph/0109104 |
| DOI | 10.1103/PhysRevA.65.050304 |
| Journal | Phys. Rev. A 65 050304 (2002). |
Abstract
A standard quantum oracle $S_f$ for a general function $f: Z_N \to Z_N $ is defined to act on two input states and return two outputs, with inputs $\ket{i}$ and $\ket{j}$ ($i,j \in Z_N $) returning outputs $\ket{i}$ and $\ket{j \oplus f(i)}$. However, if $f$ is known to be a one-to-one function, a simpler oracle, $M_f$, which returns $\ket{f(i)}$ given $\ket{i}$, can also be defined. We consider the relative strengths of these oracles. We define a simple promise problem which minimal quantum oracles can solve exponentially faster than classical oracles, via an algorithm which cannot be naively adapted to standard quantum oracles. We show that $S_f$ can be constructed by invoking $M_f$ and $(M_f)^{-1}$ once each, while $\Theta(\sqrt{N})$ invocations of $S_f$ and/or $(S_f)^{-1}$ are required to construct $M_f$.
{
"annotation_id": "efc09641-17e9-4ca6-b04a-38db2fbd6468",
"date_created": "2026-03-02T18:01:45.790000Z",
"date_modified": "2026-03-02T18:01:45.790000Z",
"file_hash": "dacf1f718d27ac9558ed9846168e19bbe0a46c493bf86a0c641983ecdf2fc340",
"private": false,
"record": {
"abstract": "A standard quantum oracle $S_f$ for a general function $f: Z_N \\to Z_N $ is\ndefined to act on two input states and return two outputs, with inputs\n$\\ket{i}$ and $\\ket{j}$ ($i,j \\in Z_N $) returning outputs $\\ket{i}$ and\n$\\ket{j \\oplus f(i)}$. However, if $f$ is known to be a one-to-one function, a\nsimpler oracle, $M_f$, which returns $\\ket{f(i)}$ given $\\ket{i}$, can also be\ndefined. We consider the relative strengths of these oracles. We define a\nsimple promise problem which minimal quantum oracles can solve exponentially\nfaster than classical oracles, via an algorithm which cannot be naively adapted\nto standard quantum oracles. We show that $S_f$ can be constructed by invoking\n$M_f$ and $(M_f)^{-1}$ once each, while $\\Theta(\\sqrt{N})$ invocations of $S_f$\nand/or $(S_f)^{-1}$ are required to construct $M_f$.",
"arxiv_id": "quant-ph/0109104",
"authors": [
"Elham Kashefi",
"Adrian Kent",
"Vlatko Vedral",
"Konrad Banaszek"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.65.050304",
"journal_ref": "Phys. Rev. A 65 050304 (2002).",
"title": "A Comparison of Quantum Oracles",
"url": "https://arxiv.org/abs/quant-ph/0109104"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b8959bde-095a-4eb5-bf14-9bb45b94ed66",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}