dorsal/arxiv
View SchemaSharp Quantum vs. Classical Query Complexity Separations
| Authors | J. Niel de Beaudrap, Richard Cleve, John Watrous |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0011065 |
| URL | https://arxiv.org/abs/quant-ph/0011065 |
Abstract
We obtain the strongest separation between quantum and classical query complexity known to date -- specifically, we define a black-box problem that requires exponentially many queries in the classical bounded-error case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.
{
"annotation_id": "cf95b093-5685-4e5c-a34f-76247cad1af9",
"date_created": "2026-03-02T18:01:42.420000Z",
"date_modified": "2026-03-02T18:01:42.420000Z",
"file_hash": "582b47266b616a1c389137021a0eae0ef259b6725b42d7179ea08ec1c2360b9a",
"private": false,
"record": {
"abstract": "We obtain the strongest separation between quantum and classical query\ncomplexity known to date -- specifically, we define a black-box problem that\nrequires exponentially many queries in the classical bounded-error case, but\ncan be solved exactly in the quantum case with a single query (and a polynomial\nnumber of auxiliary operations). The problem is simple to define and the\nquantum algorithm solving it is also simple when described in terms of certain\nquantum Fourier transforms (QFTs) that have natural properties with respect to\nthe algebraic structures of finite fields. These QFTs may be of independent\ninterest, and we also investigate generalizations of them to noncommutative\nfinite rings.",
"arxiv_id": "quant-ph/0011065",
"authors": [
"J. Niel de Beaudrap",
"Richard Cleve",
"John Watrous"
],
"categories": [
"quant-ph"
],
"title": "Sharp Quantum vs. Classical Query Complexity Separations",
"url": "https://arxiv.org/abs/quant-ph/0011065"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "423059e6-0f68-49ea-913d-5a77a6b270be",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}