From what I understood, there seems to be a difference between quantum annealing and adiabatic quantum computation models but the only thing I found on this subject implies some strange results (see below).

My question is the following: what is exactly the difference/relation between quantum annealing and adiabatic quantum computation?

The observations that leads to a "strange" result:

  • On Wikipedia, adiabatic quantum computation is depicted as "a subclass of quantum annealing".
  • On the other hand we know that:
    1. Adiabatic quantum computation is equivalent to quantum circuit model (arXiv:quant-ph/0405098v2)
    2. DWave computers use quantum annealing.

So by using the 3 facts above, DWave quantum computers should be universal quantum computers. But from what I know, DWave computers are restricted to a very specific kind of problem so they cannot be universal (DWave's engineers confirm this in this video).

As a side question, what is the problem with the reasoning above?


Vinci and Lidar have a nice explanation in their introduction of non-stoquastic Hamiltonians in quantum annealing (which is necessary to a quantum annealing device to simulate gate model computation).


It is well known that the solution of computational problems can be encoded into the ground state of a time-dependent quantum Hamiltonian. This approach is known as adiabatic quantum computation (AQC), and is universal for quantum computing (for a review of AQC see arXiv:1611.04471). Quantum annealing (QA) is a framework that incorporates algorithms and hardware designed to solve computational problems via quantum evolution towards the ground states of final Hamiltonians that encode classical optimization problems, without necessarily insisting on universality or adiabaticity.

QA thus inhabits a regime that is intermediate between the idealized assumptions of universal AQC and unavoidable experimental compromises. Perhaps the most significant of these compromises has been the design of stoquastic quantum annealers. A Hamiltonian $H$ is stoquastic with respect to a given basis if $H$ has only real nonpositive offdiagonal matrix elements in that basis, which means that its ground state can be expressed as a classical probability distribution. Typically, one chooses the computational basis, i.e., the basis in which the final Hamiltonian is diagonal. The computational power of stoquastic Hamiltonians has been carefully scrutinized, and is suspected to be limited in the ground-state AQC setting. E.g., it is unlikely that ground-state stoquastic AQC is universal. Moreover, under various assumptions ground-state stoquastic AQC can be efficiently simulated by classical algorithms such as quantum Monte Carlo, though certain exceptions are known.

  • $\begingroup$ This answer coupled with your comment on an other question answered my question. Thanks! $\endgroup$ – Nelimee Apr 5 '18 at 6:02
  • $\begingroup$ Does a stochastic Hamiltonian imply that its a stoquastic Hamiltonian too? $\endgroup$ – user3483902 Apr 21 '18 at 19:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.