I wrote a short paper entitled “when noise accumulates” that contains the main conceptual points (described rather formally) of my work regarding noisy quantum computers. Here is the paper. (Update: Here is a new version, Dec 2010.) The new exciting innovation in computer science conference in Beijing seemed tailor made for this kind of work, but the paper did not make it that far. Let me quote the first few paragraphs. As always, remarks are welcome!
From the introduction: Quantum computers were offered by Feynman and others and formally described by Deutsch, who also suggested that they can outperform classical computers. The idea was that since computations in quantum physics require an exponential number of steps on digital computers, computers based on quantum physics may outperform classical computers. A spectacular support for this idea came with Shor’s theorem that asserts that factoring is in BQP (the complexity class described by quantum computers).
The feasibility of computationally superior quantum computers is one of the most fascinating and clear-cut scientific problems of our time. The main concern regarding quantum-computer feasibility is that quantum systems are inherently noisy. (This concern was put forward in the mid-90s by Landauer, Unruh, and others.)
The theory of quantum error correction and fault-tolerant quantum computation (FTQC) and, in particular, the threshold theorem which asserts that under certain conditions FTQC is possible, provides strong support for the possibility of building quantum computers.
However, as far as we know, quantum error correction and quantum fault tolerance (and the highly entangled quantum states that enable them) are not experienced in natural quantum processes. It is therefore not clear if computationally superior quantum computation is necessary to describe natural quantum processes.
We will try to address two closely related questions. The first is, what are the properties of quantum processes that do not exhibit quantum fault tolerance and how to formally model such processes. The second is, what kind of noise models cause quantum error correction and FTQC to fail.
A main point we would like to make is that it is possible that there is a systematic relation between the noise and the intended state of a quantum computer. Such a systematic relation does not violate linearity of quantum mechanics, and it is expected to occur in processes that do not exhibit fault tolerance.
Let me give an example: suppose that we want to simulate on a noisy quantum computer a certain bosonic state. The standard view of noisy quantum computers asserts that under certain conditions this can be done up to some error that is described by the computational basis. In contrast, the type of noise we expect amounts to having a mixed state between the intended bosonic state and other bosonic states (that represent the noise).
Criticism: A criticism expressed by several readers of an early version of this paper is that no attempt is made to motivate the conjectures from a physical point of view and that the suggestions seem “unphysical.” What can justify the assumption that a given error lasts for a constant fraction of the entire length of the process? If a noisy quantum computer at a highly entangled state has correlated noise between faraway qubits as we suggest, wouldn’t it allow signaling faster than the speed of light?
I had sort of a mixed reaction toward this criticism. On the one hand I think that it is important and may be fruitful to examine various models of noise while putting the physics aside. Nevertheless, I added a brief discussion of some physical aspects. Here it is:
Let us go back to the example of simulating bosonic states with a noisy quantum computer. When errors accumulate I expect that a large (even dominant) part of the noise will not consist of local noise based on the computational bases but rather it will be a mix of the intended bosonic state with other unintended bosonic states.
We do not yet have quantum computers that simulate bosonic states but we do have several natural and experimental processes that come close to this description, like phonons, which can be regarded as a bosonic state (on a macroscopic scale) “simulated” on microscopic “qudits”. (There are several other examples as well.) These examples can serve as a good place to examine noise.
Another place to examine some suggestions of this paper is current implementations of ion-trap computers. In these implementations we need to move qubits together in order to gate them, and this suggests that, in each computer cycle, errors will be correlated for all pairs of qubits. At present, the rate of noise is still the major concern of experimentalists, but it is not clear how a large pairwise correlation between all pairs of qubits can be avoided in current architecture. Specific alternative suggestions (based on teleportation) of performing gates for ion-trap computers without moving the qubits may not solve this problem since we cannot assume for these suggested implementations that measuring qubits will not induce noise on other qubits.
If our suggested properties of noise for some (hypothetical) quantum computer architecture at some quantum state ρ allow instantaneous signaling, then the conclusion is that this quantum computer architecture simply does not accommodate the quantum state ρ
Given a proposed architecture for a quantum computer it is possible that for some hypothetical states that cannot be achieved the proposed properties of noise are “unphysical”. The place to examine the conjectures are for attainable states.
Finally, another comment was that FTQC via topological quantum computing does not rely on the threshold theorem and Conjectures A and B (from my paper) are not relevant for this model. However, the underlying mathematics behind the threshold theorem and behind FTQC via topological quantum computers is quite similar. The extreme stability to noise expected for non-Abelian anyons (and Abelian anyons) relies on similar assumptions to those enabling quantum error correction. When we create Abelian anyons in the laboratory, or try to create non-Abelian anyons, there is no reason to believe that the process for creating them will involve suppression of propagated noise and therefore, just as when we simulate fermions or bosons, we expect a mixture of the intended state with other states of the same type. When noise accumulates there is no reason to expect the strong stability of certain anyons that is predicted by current models.