Dwave has published a paper which claims that the effect of strong decoherence on AQC is to (generically) square the time it takes an optimal algorithm to operate. This wipes out quadratic speed-ups (like adiabatic Grover search), but implies that exponential gains remain exponential for AQC even with total loss of phase coherence.
The paper is Decoherence in adiabatic quantum computation M. H. S. Amin1 and Dmitri V. Averin2
1 D-Wave Systems Inc., 100-4401 Still Creek Drive, Burnaby, B.C., V5C 6G9, Canada
2 Department of Physics and Astronomy, Stony Brook University, SUNY, Stony Brook, NY 11794-3800
We have studied the decoherence properties of adiabatic quantum computation in the presence of in general non-Markovian (e.g., low-frequency) noise. We show that the global scheme of adiabatic quantum computation maintains its performance even for strong decoherence. The more efficient local adiabatic computation, however, does not improve scaling of the computation time with the number of qubits n as in the decoherence-free case, although it does provide some prefactor” improvement. The scaling improvement requires phase coherence throughout the computation, limiting the computation time and the problem size n.
Why is this important?
This is advancing answers to the questions around the Dwave quantum computer (16 qubit demo feb/2007).
Dwave Systems indicates that they will have a 1024 qubit commercial quantum computer in 2008. If this paper is correct then that machine will have vastly superior performance for solving problems where there is exponential improvement for quantum computer algorithms. Also, where they can maintain freedom from decoherence they will have large improvements for several other very useful problems. Among the problems that should see improvement is quantum chemistry simulations which would accelerate the development of molecular nanotechnology. Initial more limited but significant commercial success should provide dwave with the funds to refine their qubits and increase the size of their quantum computers. 2009-2010 should be when their systems start to make significant impact on the development of quantum chemistry and molecular nanotechnology.
From the Comments:
Q: “this implies that exponential gains remain exponential for AQC even with total loss of phase coherence.” from Dave Bacon
Must say I don’t get that statement at all. Why is the error model considered here the one which is relevant to universal AQC?
Answer from one of the authors: Mohammad Amin
To answer Dave’s question, in this work we considered a wide range of classical and quantum noise models which include bosonic environment (phonons or electromagnetic noise) and also spin environment. We also considered the most important type of error in AQC, which is excitation at the energy anticrossing between the lowest two energy levels. Every other type of error in AQC is suppressed by a much larger gap. What we found is that decoherence broadens the resonance region. Since for the global AQC only the integral of the transition rate matters, the broadening doesn’t affect the probability of excitation. On the other hand, for local AQC the width of the broadening plays an important role making it very sensitive to decoherence. Indeed, the computation time in local AQC is limited by the decoherence time the same way as it is in gate model QC. The fact that Landau-Zener transition (i.e., global AQC) is insensitive to phase coherence has also been discussed before us by others, see e.g., Saito et al. arXiv:cond-mat/0703596, in which they also consider a completely general noise model.