  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].
