Poziom korzyści zapewnianych przez wyżarzanie dla podróżujących sprzedawców

Rozumiem, że wydaje się, iż istnieje pewna pewność, że wyżarzanie kwantowe przyspieszy problemy takie jak podróżujący sprzedawca, ze względu na wydajność zapewnianą np. Przez tunelowanie kwantowe. Czy wiemy jednak, ile przyspieszenia?

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.