18
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\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
    Commented Mar 17, 2018 at 21:33
  • 1
    $\begingroup$ Is it not related to the spectral properties of $\mathcal{H}$? $\endgroup$
    – Mark Spinelli
    Commented Aug 15, 2018 at 2:14
  • $\begingroup$ related: quantumcomputing.stackexchange.com/q/126/55 $\endgroup$
    – glS ♦
    Commented Jul 11, 2022 at 11:26

2 Answers 2

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
0
1
$\begingroup$

There is a fully solvable model of quantum annealing with arbitrary target spin Hamiltonian: https://arxiv.org/pdf/2110.12354.pdf

It shows that generally the computation time depends on the number of qubits exponentially. However, it can be considerably smaller for specially structured spin Hamiltonians, for example, when the ground state is degenerate.

Improve this answer
$\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.