28
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

13
$\begingroup$

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).

https://arxiv.org/abs/1701.07494

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.

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

All three of the bulleted or numbered claims in your OP are correct. But the flaw in your logic in combining them together is that D-Wave is not a "universal" quantum annealer, in the sense that it can't operate perfectly at all "temperatures"/levels of adiabaticity. In other words, it can (allegedly) perform some types of quantum annealing, but not all of them.

In particular, it can't perform the most useful form of quantum annealing of all - the perfectly adiabatic case ("zero temperature"/no quantum fluctuations out of the ground state). If it could, then it would indeed be (equivalent to) a universal quantum computer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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