Thoughts on Noise and Quantum Computation

Gil Kalai

Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem

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, the dependence structure of the noise acting on individual qubits will necessarily depend (systematically) on the dependence structure of the qubits themselves. 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].

Pages: 43 pages
Date: 2005-08
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://ratio.huji.ac.il/sites/default/files/publications/dp400.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp400.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp400.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:huj:dispap:dp400

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin ().