Po pierwsze, pragnę zauważyć, że wyżarzanie kwantowe, a ściślej adiabatyczny model obliczeń kwantowych, jest wielomianowo równoważny z konwencjonalnym modelem obliczeń kwantowych opartych na bramce . Po drugie, ogólny problem sprzedawców w podróży jest NP kompletny . Po trzecie, ogólnie uważa się, że przy obliczaniu kwantowym opartym na bramce nie można rozwiązać problemów całkowitych NP w czasie wielomianowym . Wszystko to oznacza, że uważa się za bardzo mało prawdopodobne, aby przy wyżarzaniu kwantowym można było rozwiązać w czasie wielomianowym ogólny problem sprzedawcy w podróży.
Pomimo tego uważa się, że ogólny problem można rozwiązać tylko w czasie wykładniczym, także przy wyżarzaniu kwantowym, nadal może być pewne przyspieszenie, na przykład przyspieszenie wielomianowe. Niewiele wiadomo na ten temat w ogólnym przypadku. Jest jednak bardzo ładna ostatnia praca, która pokazuje, że istnieją algorytmy kwantowe z błędem ograniczonym, które zapewniają kwadratowe przyspieszenie kwantowe, gdy stopień każdego wierzchołka (w problemie kupieckiego handlu) wynosi co najwyżej 3.