dorsal/arxiv
View SchemaQuantum and Classical Tradeoffs
| Authors | Yaoyun Shi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0312213 |
| URL | https://arxiv.org/abs/quant-ph/0312213 |
| DOI | 10.1016/j.tcs.2005.03.053 |
Abstract
We propose an approach for quantifying a quantum circuit's quantumness as a means to understand the nature of quantum algorithmic speedups. Since quantum gates that do not preserve the computational basis are necessary for achieving quantum speedups, it appears natural to define the quantumness of a quantum circuit using the number of such gates. Intuitively, a reduction in the quantumness requires an increase in the amount of classical computation, hence giving a ``quantum and classical tradeoff''. In this paper we present two results on this direction. The first gives an asymptotic answer to the question: ``what is the minimum number of non-basis-preserving gates required to generate a good approximation to a given state''. This question is the quantum analogy of the following classical question, ``how many fair coins are needed to generate a given probability distribution'', which was studied and resolved by Knuth and Yao in 1976. Our second result shows that any quantum algorithm that solves Grover's Problem of size n using k queries and l levels of non-basis-preserving gates must have k*l=\Omega(n).
{
"annotation_id": "c3df2975-65b9-4a18-b546-c29fea6d8cfb",
"date_created": "2026-03-02T18:02:03.591000Z",
"date_modified": "2026-03-02T18:02:03.591000Z",
"file_hash": "173418f736e491a4dfea0335b2faf95fd9018f4516c13cf89d48482af86c78c5",
"private": false,
"record": {
"abstract": "We propose an approach for quantifying a quantum circuit\u0027s quantumness as a\nmeans to understand the nature of quantum algorithmic speedups. Since quantum\ngates that do not preserve the computational basis are necessary for achieving\nquantum speedups, it appears natural to define the quantumness of a quantum\ncircuit using the number of such gates. Intuitively, a reduction in the\nquantumness requires an increase in the amount of classical computation, hence\ngiving a ``quantum and classical tradeoff\u0027\u0027.\n In this paper we present two results on this direction. The first gives an\nasymptotic answer to the question: ``what is the minimum number of\nnon-basis-preserving gates required to generate a good approximation to a given\nstate\u0027\u0027. This question is the quantum analogy of the following classical\nquestion, ``how many fair coins are needed to generate a given probability\ndistribution\u0027\u0027, which was studied and resolved by Knuth and Yao in 1976. Our\nsecond result shows that any quantum algorithm that solves Grover\u0027s Problem of\nsize n using k queries and l levels of non-basis-preserving gates must have\nk*l=\\Omega(n).",
"arxiv_id": "quant-ph/0312213",
"authors": [
"Yaoyun Shi"
],
"categories": [
"quant-ph"
],
"doi": "10.1016/j.tcs.2005.03.053",
"title": "Quantum and Classical Tradeoffs",
"url": "https://arxiv.org/abs/quant-ph/0312213"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7f5ed686-0cf4-4f89-b94f-0025429bcc6a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}