dorsal/arxiv
View SchemaLimitations of Quantum Advice and One-Way Communication
| Authors | Scott Aaronson |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0402095 |
| URL | https://arxiv.org/abs/quant-ph/0402095 |
| DOI | 10.4086/toc.2005.v001a001 |
| Journal | Theory of Computing 1(1):1-28, 2005 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that $\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}$, where $\mathsf{BQP/qpoly}$ is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state" that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which $\mathsf{NP}\not \subset \mathsf{BQP/qpoly}$. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).
{
"annotation_id": "70207981-46bf-42b9-a179-a6ff944484db",
"date_created": "2026-03-02T18:02:06.221000Z",
"date_modified": "2026-03-02T18:02:06.221000Z",
"file_hash": "27c47c91d4147ca0fee1c2dd7058851c278e185e0c723f7247614135eb993d20",
"private": false,
"record": {
"abstract": "Although a quantum state requires exponentially many classical bits to\ndescribe, the laws of quantum mechanics impose severe restrictions on how that\nstate can be accessed. This paper shows in three settings that quantum messages\nhave only limited advantages over classical ones.\n First, we show that $\\mathsf{BQP/qpoly}\\subseteq\\mathsf{PP/poly}$, where\n$\\mathsf{BQP/qpoly}$ is the class of problems solvable in quantum polynomial\ntime, given a polynomial-size \"quantum advice state\" that depends only on the\ninput length. This resolves a question of Buhrman, and means that we should not\nhope for an unrelativized separation between quantum and classical advice.\nUnderlying our complexity result is a general new relation between\ndeterministic and quantum one-way communication complexities, which applies to\npartial as well as total functions.\n Second, we construct an oracle relative to which $\\mathsf{NP}\\not \\subset\n\\mathsf{BQP/qpoly}$. To do so, we use the polynomial method to give the first\ncorrect proof of a direct product theorem for quantum search. This theorem has\nother applications; for example, it can be used to fix a result of Klauck about\nquantum time-space tradeoffs for sorting.\n Third, we introduce a new trace distance method for proving lower bounds on\nquantum one-way communication complexity. Using this method, we obtain optimal\nquantum lower bounds for two problems of Ambainis, for which no nontrivial\nlower bounds were previously known even for classical randomized protocols.\n A preliminary version of this paper appeared in the 2004 Conference on\nComputational Complexity (CCC).",
"arxiv_id": "quant-ph/0402095",
"authors": [
"Scott Aaronson"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.4086/toc.2005.v001a001",
"journal_ref": "Theory of Computing 1(1):1-28, 2005",
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Limitations of Quantum Advice and One-Way Communication",
"url": "https://arxiv.org/abs/quant-ph/0402095"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "11abeb6c-c8c9-4797-b91e-df68414a17db",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}