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
    Answers to this question should consider taking noise into account, as it is a critical part of what determines the speed of quantum tunneling. – DanielSank Mar 17 at 21:33
  • Is it not related to the spectral properties of $\mathcal{H}$? – Mark S Aug 15 at 2:14
up vote 14 down vote accepted

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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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