Quantum annealing can be considered either in the perfectly adiabatic "slow" limit (in which case it's usually referred as "adiabatic quantum computing" (AQC) instead of "quantum annealing"), or in the diabatic regime of diabatic quantum annealing (DQA).

If you ignore all experimental practicalities and consider a theoretical perfect quantum annealer that can operate at any speed without decohering, then my intuition is that the perfectly adiabatic version would be the most theoretically powerful, in the sense that it can solve any problem faster than the diabatic version.

On the other hand, I could also imaging telling a heuristic story in which in some cases the diabatic effects can help, by either (a) simply allowing you to tune your transverse field qualitatively faster than possible if you need to maintain adiabaticity, or (b) taking advantage of quantum fluctuations out of the ground state to tunnel through some intermediate excited states that end up taking you to the final ground state faster than if you stayed in the ground state the whole time.

Are either of these two intuitions known to be correct? That is, is it known or suspected which of these three claims is correct from the perspective of theoretical computational complexity?

  1. For all problems, AQC is at least as powerful as DQA.
  2. For all problems, DQA is at least as powerful as AQC.
  3. For some problems, AQC gives a qualitative speedup over DQA, and for other problems, DQA gives a qualitative speedup over AQC.
  • $\begingroup$ I don't think anyone has done any proofs of the power of DQA. $\endgroup$ – user1271772 Jun 20 '20 at 23:02
  • $\begingroup$ @user1271772 What about conjectures? People can rarely prove anything in computational complexity theory. $\endgroup$ – tparker Jun 21 '20 at 0:54
  • $\begingroup$ What is the earliest reference you know for DQA? $\endgroup$ – user1271772 Jun 21 '20 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.