Jak długo trwa wyżarzanie kwantowe, aby znaleźć rozwiązanie danego problemu?

Wyżarzanie kwantowe jest protokołem optymalizacji, który dzięki tunelowaniu kwantowemu pozwala w danych okolicznościach zmaksymalizować / zminimalizować daną funkcję bardziej skutecznie niż klasyczne algorytmy optymalizacji.

Kluczowym punktem wyżarzania kwantowego jest adiabatyczność algorytmu, która jest wymagana, aby stan pozostawał w stanie podstawowym zależnego od czasu hamiltonianu. Jest to jednak również problem, ponieważ oznacza, że ​​znalezienie rozwiązania może wymagać bardzo długiego czasu.

Jak długie muszą być te czasy dla danego Hamiltonianina? Mówiąc dokładniej, biorąc pod uwagę problem Hamiltonian w którym chcemy znaleźć stan podstawowy, czy istnieją wyniki, które mówią, jak długo zajmie kwantowe wygrzewanie do rozwiązania?$\mathcal H$

Czas do rozwiązania (tts) jest wysoce zależny od hamiltonianu problemu, który chciałby rozwiązać. D-Wave wykorzystuje hamiltonian typu spin-glass, który może należeć do klasy złożoności NP-Complete.

Z uwagi na konieczność wielokrotnego uruchamiania procesu wyżarzania miary tts są zazwyczaj określane ilościowo na podstawie tego, ile czasu zajmuje znalezienie stanu podstawowego przez pewien procent czasu.

Oto praca niektórych kolegów, która wyjaśnia tts (patrz zwłaszcza równanie 3).