Quantum annealing is an optimization protocol that, thanks to quantum tunneling, allows in given circumstances to maximize/minimize a given function more efficiently than classical optimization algorithms.

A crucial point of quantum annealing is the adiabaticity of the algorithm, which is required for the state to stay in the ground state of the time-dependent Hamiltonian. This is however also a problem, as it means that find a solution can require very long times.

How long do these times have to be for a given Hamiltonian? More precisely, given a problem Hamiltonian $\mathcal H$ of which we want to find the ground state, are there results saying how long would it take a quantum annealer to reach the solution?

  • 2
    $\begingroup$ Answers to this question should consider taking noise into account, as it is a critical part of what determines the speed of quantum tunneling. $\endgroup$ – DanielSank Mar 17 '18 at 21:33
  • $\begingroup$ Is it not related to the spectral properties of $\mathcal{H}$? $\endgroup$ – Mark S Aug 15 '18 at 2:14

The time to solution (tts) is highly dependent on the Hamiltonian of the problem one would like to solve. The D-Wave uses a spin-glass-like Hamiltonian which can be in the NP-Complete complexity class.

Due to having to run the annealing process multiple times, tts measures are typically quantified by how long it takes to find the ground state some percent of the time.

Here's a paper by some colleagues that explains tts (see especially equation 3).


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.