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:
Physics
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.
Combinatorics and more 
Quantum computing at the mass produced level depends on the nano/picoscale research progress achieved by advanced physics. Exploration of the picoscale, where atoms are ~300 picometers across, holds the key. Valid research is coming forth by data density from SEM/AFM imaging with computer modeling of electrons and energy fields. The essential data does not come through SEM/AFM, though, because those optical images give none of the vital information on the topology of electrons, energy fields, and force field-matrix. Real advancement lies in the resolution of femtoscale energy structures, by the atomic topological function commonly called the Schrodinger equation.
Recent advancements in quantum science have produced the picoyoctometric, 3D, interactive video atomic model imaging function, in terms of chronons and spacons for exact, quantized, relativistic animation. This format returns clear numerical data for a full spectrum of variables. The atom’s RQT (relative quantum topological) data point imaging function is built by combination of the relativistic Einstein-Lorenz transform functions for time, mass, and energy with the workon quantized electromagnetic wave equations for frequency and wavelength.
The atom labeled psi (Z) pulsates at the frequency {Nhu=e/h} by cycles of {e=m(c^2)} transformation of nuclear surface mass to forcons with joule values, followed by nuclear force absorption. This radiation process is limited only by spacetime boundaries of {Gravity-Time}, where gravity is the force binding space to psi, forming the GT integral atomic wavefunction. The expression is defined as the series expansion differential of nuclear output rates with quantum symmetry numbers assigned along the progression to give topology to the solutions.
Next, the correlation function for the manifold of internal heat capacity energy particle 3D functions is extracted by rearranging the total internal momentum function to the photon gain rule and integrating it for GT limits. This produces a series of 26 topological waveparticle functions of the five classes; {+Positron, Workon, Thermon, -Electromagneton, Magnemedon}, each the 3D data image of a type of energy intermedon of the 5/2 kT J internal energy cloud, accounting for all of them.
Those 26 energy data values intersect the sizes of the fundamental physical constants: h, h-bar, delta, nuclear magneton, beta magneton, k (series). They quantize atomic dynamics by acting as fulcrum particles. The result is the exact picoyoctometric, 3D, interactive video atomic model data point imaging function, responsive to keyboard input of virtual photon gain events by relativistic, quantized shifts of electron, force, and energy field states and positions.
Images of the h-bar magnetic energy waveparticle of ~175 picoyoctometers are available online at http://www.symmecon.com with the complete RQT atomic modeling manual titled The Crystalon Door, copyright TXu1-266-788. TCD conforms to the unopposed motion of disclosure in U.S. District (NM) Court of 04/02/2001 titled The Solution to the Equation of Schrodinger.
When you say that you can have correlated noise without non-linearity, what exactly do you mean by non-linearity (or rather, linearity). It’s never actually defined in your paper, and I suspect that what you mean by it is somewhat different from what I mean by it.
Dear Peter,
There was the following criticism on my conjectures:
“Is a message of the detrimental noise model that it depends on the state of the system? I don’t see how that is compatible with linearity. A linear map should be independent of the state it is applied to.”
(So the problem is not with correlated noise per se.)
The answer is that indeed my conjectures amount to a systematic relation between the noise and the intended state of the computer, and that I do not see why such a systematic relation between the state and the noise violates linearity of quantum mechanics. (In the sense that it requires more general form of operations which quantum mechanics does not accomodate.)
Hi Gil,
I am probably missing something completely obvious, but I’m confused. I’m used to thinking of noise as uncertainty. Shouldn’t a linear system be deterministic and thus not have any noise? Of course, real-life quantum computers will indeed have noise, but this noise doesn’t arise from quantum mechanics itself, but from uncertainty in the exact length of time that forces are applied, and from unexpected interactions with the environment, etc. If you augment standard quantum mechanics with some unexplained uncertainty that isn’t arising from any of these sources, don’t you have to prove that what you get can really be linear?
Don’t get me wrong; I’m not saying that it can’t be linear. What I’m claiming is that you haven’t demonstrated that it can be, and that there is something that really needs to be proven here.
Dear Peter, what I am saying is that systematic dependence between the state of the computer and the noise (which is indeed a non linear phenomenon), does not violate by itself linearity of quantum mechanics.
It is very reasonable to regard noise as expressing uncertainty. Let’s consider a real-life-quantum-computer that can simulate bosonic and fermionic states. (I am quite confident that such devices can be built.) I tend to think that when the intended state is bosonic then a dominant part of the noise will be a mixture with undesirable bosonic states, and when the intended state is fermionic, then a dominant part of the noise will be a mixture with undesirable fermionic state.
I guess that such a behavior will follow from the “smoothing-in-time” formula for noise that I propose in the third section. (And this formula is essentially linear in the sense that the noisy evolution can be described as a unitary evolution on a larger Hilbert space). I also guess that this property of the noise will show up in any noisy device we will build, at least for a while.
(In any case, if there is something specific I need to demonstrate, I will be happy to think about it, and try to prove it or even disprove it. )
Hi Gil,
Well, the hope is that if you put in fault tolerance, then, no matter what you’re simulating, nearly all of the noise will be a mixture of states that are not codewords in the error correcting code, but which are correctable to states in the code.
I’ll think about whether I have something specific to ask about non-linearity, and get back to you.
Peter
GK: Thanks, Peter!
Peter wrote: “Well, the hope is that if you put in fault tolerance, then, no matter what you’re simulating, nearly all of the noise will be a mixture of states that are not codewords in the error correcting code, but which are correctable to states in the code.”
When we try to create a state that represents a quantum error correcting code, the alternative presented in my paper amounts to noise which is a mixture of the desired codeword with undesired codewords. The concern is that this type of noise, coming from the process leading to the desired state, cannot be avoided.
Gil,
If this works, it would seem to go some way to getting around your concerns regarding noise. What do you think?
http://www.nature.com/news/2011/110601/full/474024a.html
Dear Mike, thanks for the interesting link. My preliminary thoughts are: First, yes, sure if this works it might be in conflict with my concerns. And second, since White’s approach is based on “shortcutting” the traditional qubits/gates/quantum-error-correction architecture his suggestion may actually be vulnerable to my concerns.
I will have to look more carefully at the technical papers (your link is to a popular article).