Ma compréhension est qu'il semble y avoir une certaine confiance que le recuit quantique fournira une accélération pour des problèmes comme le vendeur itinérant, en raison de l'efficacité fournie par, par exemple, le tunneling quantique. Savons-nous, cependant, quelle quantité d'accélération est fournie?
Tout d'abord, permettez-moi de noter que le recuit quantique, ou plus précisément le modèle de calcul quantique adiabatique est polynomialement équivalent au modèle de calcul quantique basé sur la porte conventionnel . Deuxièmement, le problème général des vendeurs ambulants est NP complet . Troisièmement, on pense généralement qu'avec le calcul quantique basé sur une porte, on ne peut pas résoudre en temps polinomial des problèmes NP complets . Tout cela signifie qu'il est hautement improbable qu'avec le recuit quantique, on puisse résoudre en temps polynomial le problème général des vendeurs ambulants.
Malgré cela, on pense que le problème général ne peut être résolu qu'en temps exponentiel également avec le recuit quantique, il pourrait encore y avoir une certaine accélération, par exemple, une accélération polynomiale. On ne sait pas grand-chose à ce sujet pour le cas général. Cependant, il y a un très bon travail récent qui montre qu'il existe des algorithmes quantiques à erreur bornée qui fournissent une accélération quantique quadratique lorsque le degré de chaque sommet (dans le problème du vendeur en travail) est au plus de 3.