Quantum Computers -How Can They Fail?

Abstract We propose and discuss two postulates on the nature of errors in highly correlated noisy physical stochastic systems. The first postulate asserts that errors for a pair of substantially correlated elements are themselves substantially correlated. The second postulate asserts that in a noisy system with many highly correlated elements there will be a strong effect of error synchronization. These postulates appear to be damaging for quantum computers. Quantum computers and the threshold theorem Quantum computers are hypothetical devices based on quantum physics. A formal definition of quantum computers was pioneered by Deutsch [1], who also realized that they can outperform classical computation. The idea of a quantum computer can be traced back to works by Feynman, Manin, and others, and this development is also related to reversible computation and connections between computation and physics were studied by Bennett in the 1970s. Perhaps the most important result in this field and certainly a major turning point was Shor's discovery [2] of a polynomial quantum algorithm for factorization. The notion of a quantum computer along wit