Tengo entendido que parece haber cierta confianza en que el recocido cuántico proporcionará una aceleración para problemas como el vendedor ambulante, debido a la eficiencia proporcionada por, por ejemplo, el túnel cuántico. ¿Sabemos, sin embargo, en qué medida se proporciona una aceleración?
Primero, permítanme señalar que el recocido cuántico, o más precisamente, el modelo de cálculo cuántico adiabático es polinomialmente equivalente al modelo de cálculo cuántico basado en puerta convencional . En segundo lugar, el problema general del vendedor ambulante es NP completo . En tercer lugar, generalmente se cree que con el cálculo cuántico basado en la puerta no se pueden resolver en tiempo polinomial los problemas completos de NP . Todo esto significa que se considera altamente improbable que con el recocido cuántico se pueda resolver en tiempo polinómico el problema general del vendedor ambulante.
A pesar de que se cree que el problema general solo puede resolverse en tiempo exponencial también con recocido cuántico, todavía podría haber cierta aceleración, por ejemplo, una aceleración polinómica. No se sabe demasiado sobre esto para el caso general. Sin embargo, hay un trabajo reciente muy bueno que muestra que hay algoritmos cuánticos de error limitado que proporcionan una aceleración cuántica cuadrática cuando el grado de cada vértice (en el problema del vendedor) es como máximo 3.