dorsal/arxiv
View SchemaThoughts on Noise and Quantum Computation
| Authors | Gil Kalai |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0508095 |
| URL | https://arxiv.org/abs/quant-ph/0508095 |
Abstract
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quantum computation. We consider stochastic models of quantum computation on $n$ qubits subject to noise operators that are obtained as products of tiny noise operators acting on a small number of qubits. We conjecture that for realistic random noise operators of this kind there will be substantial dependencies between the noise on individual qubits and, in addition, we propose that the dependence structure of the noise acting on individual qubits will necessarily depend (systematically) on the dependence structure of the qubits themselves. We point out that the majority function can repair, in the classical case, some forms of stochastic noise of this kind and conjecture that this healing power of majority has no quantum analog. The main hypothesis of this paper is that these properties of noise are sufficient to reduce quantum computation to probabilistic classical computation. Some potentially relevant mathematical issues and problems will be described. Our line of thought appears to be related to that of physicists Alicki, Horodecki, Horodecki and Horodecki [AHHH].
{
"annotation_id": "10b545b6-e75c-44f3-9017-841a68ee3904",
"date_created": "2026-03-02T18:02:20.081000Z",
"date_modified": "2026-03-02T18:02:20.081000Z",
"file_hash": "ec1b8f99671510ed67bb34c44800b76b0f85c2a2d05efbd7e2168003cd99e86e",
"private": false,
"record": {
"abstract": "We will try to explore, primarily from the complexity-theoretic point of\nview, limitations of error-correction and fault-tolerant quantum computation.\nWe consider stochastic models of quantum computation on $n$ qubits subject to\nnoise operators that are obtained as products of tiny noise operators acting on\na small number of qubits. We conjecture that for realistic random noise\noperators of this kind there will be substantial dependencies between the noise\non individual qubits and, in addition, we propose that the dependence structure\nof the noise acting on individual qubits will necessarily depend\n(systematically) on the dependence structure of the qubits themselves. We point\nout that the majority function can repair, in the classical case, some forms of\nstochastic noise of this kind and conjecture that this healing power of\nmajority has no quantum analog. The main hypothesis of this paper is that these\nproperties of noise are sufficient to reduce quantum computation to\nprobabilistic classical computation. Some potentially relevant mathematical\nissues and problems will be described. Our line of thought appears to be\nrelated to that of physicists Alicki, Horodecki, Horodecki and Horodecki\n[AHHH].",
"arxiv_id": "quant-ph/0508095",
"authors": [
"Gil Kalai"
],
"categories": [
"quant-ph"
],
"title": "Thoughts on Noise and Quantum Computation",
"url": "https://arxiv.org/abs/quant-ph/0508095"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "72e9c335-09c5-4104-b632-9fe4f9b9b95f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}