Here is a paper we’re posting to the arxiv shortly. The abstract:
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.
What it claims is 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.