El estado cuántico de un cúbit ideal está descrito por un punto en la superficie de la esfera de Bloch (un estado cuántico puro). Pero el estado de un cúbit real está descrito por una distribución de probabilidad localizada alrededor de un punto en el interior de la esfera de Bloch (un estado cuántico de tipo mezcla descrito por una matriz densidad). En los algoritmos para ordenadores cuánticos se asume que todos los cúbits son ideales, aunque ninguno lo sea. Se publica en arXiv que usando un único cúbit ideal se puede un implementar un algoritmo para resolver el problema del viajante (TSP), determinar el camino más corto entre n ciudades, que es un problema NP-duro. Se mapea el TSP en un problema discreto de tipo braquistócrona (curva de recorrido más rápido) donde las ciudades son estados en la esfera de Bloch y el camino entre ellas viene dado por rotaciones (transformaciones unitarias) en superposición cuántica. Para n ciudades hay que aplicar 2 (n−1) (2 + (n−2)²) = O(n³) rotaciones unitarias (36 para n = 4, y 532 para n = 8); el problema es que tienen que estar ajustadas de forma casi perfecta. No se sabe si el algoritmo ofrece ventaja cuántica, pues aún no se ha podido estimar cuántas medidas cuánticas son necesarias en el paso final (así que no se sabe si el algoritmo está en la clase BQP). Los resultados se han obtenido usando simulaciones clásicas de un cúbit ideal para entre 4 y 9 ciudades (problemas triviales de resolver en tu ordenador).

En principio, la implementación física del algoritmo solo requiere cúbits de alta calidad en los que se puedan aplicar operadores unitarios que simulen con alta fidelidad rotaciones arbitrarias en la esfera de Bloch. Por desgracia, los cúbits reales de hoy en día (NISQ) están muy alejados de un cúbit ideal como para permitir tal implementación para n > 10. Por cierto, quizás conviene aclarar la diferencia entre el problema TSP de optimización (TSP-OPT), que es NP-duro, y el de decisión (TSP-DEC), que es NP-completo. Como ya he comentado, el TSP-OPT consiste en encontrar el camino entre las ciudades que minimiza la distancia (o cualquier otra función de coste); mientras que el TSP-DEC consiste en determinar, dado cierto coste, si existe o no existe una solución al problema con menor coste. ^(∗)Como es obvio una solución a TSP-OPT en tiempo polinómico implica una solución a TSP-DEC en tiempo polinómico y, por tanto, que P = NP. Si en los próximos años se demuestra que el nuevo algoritmo está en BQP, resultará que BQP = NP y será fácil demostrar que P = NP. Por desgracia, hay una conjetura firme en complejidad computacional cuántica que afirma que BQP ≠ NP. Si dicha conjetura es cierta, el nuevo algoritmo para TSP-OPT no puede estar en BQP.

La utilidad práctica del nuevo algoritmo es nula. Sin embargo, se están dando grandes avances tecnológicos hacia un cúbit ideal (con una eficiencia superior al 99 % durante 24 horas). Cabe prever que dichos avances harán posible la implementación del nuevo algoritmo. Lo que no resta interés a este nuevo logro. El artículo es Kapil Goswami, Gagan Anekonda Veereshi, …, Rick Mukherjee, «Solving The Travelling Salesman Problem Using A Single Qubit,» arXiv:2407.17207 [quant-ph] (24 Jul 2024), doi: https://doi.org/10.48550/arXiv.2407.17207.

^(∗) [PS 31 Jul 2024] Agradezco el comentario de Josejuan que me ha hecho ver que mi afirmación original era (obviamente) incorrecta. [/PS]

Hoy en día se puede resolver un problema TSP-OPT con cientos de ciudades en un PC (la solución será cuasi-óptima, pues se basará en heurísticos); en un supercomputador se podrá resolver para decenas de miles de ciudades (en algunos casos hasta cerca de cien mil). En un ordenador cuántico actual solo se puede resolver un problema con una decena de ciudades (en los ordenadores de recocido cuántico de D-Wave Systems con 5436 cúbits físicos, equivalentes a 73 cúbits lógicos, el récord ha sido un problema con 10 ciudades); un problema irrisorio para tu PC (recuerda que los ordenadores cuánticos actuales son solo una promesa de futuro).

El problema TSP-OPT consiste en encontrar el ciclo hamiltoniano más corto que recorre todas las ciudades (es decir, que pasa por todas ellas, una sola vez por cada una, desde la primera hasta retornar a la primera). Este problema se puede implementar como un problema discreto de tipo braquistócrona, cuando la función coste entre dos ciudades mide el tiempo que cuesta recorrer la distancia que las separa. En un ordenador clásico, dicho problema requiere recorrer el árbol de todos los posibles ciclos hamiltonianos (como muestra la figura de la izquierda) y elegir el ciclo que requiere un tiempo mínimo (figura de la derecha). El grafo de la izquierda ilustra que este algoritmo muestra mucho paralelismo, con lo que parece natural intentar aprovechar el paralelismo cuántico asociado a las superposiciones coherentes.

El problema TSP-OPT como problema discreto de tipo braquistócrona se puede implementar en la esfera de Bloch asociada a un cúbit. Un estado del cúbit es un punto de la esfera y una operación unitaria sobre el cúbit corresponde a un rotación de dicho punto a otro punto de la esfera. Las ciudades se codifican como puntos en la esfera, sea P_ii la ciudad i-ésima. El coste del camino entre las ciudades i y j se codifica con el tiempo asociado a la transición entre dichos estados, τ_ii–jj, tal que cos(ω τ_ii–jj) = 〈P_ii|P_jj〉. El problema TSP es simétrico cuando el coste entre dos ciudades no depende del sentido, τ_ii–jj = τ_jj–ii, y es asimétrico en caso contrario, τ_ii–jj ≠ τ_jj–ii.

Para poder asignar un coste arbitrario entre dos ciudades se introduce un punto intermedio P_ij, de tal forma que el coste sea la suma de los costes, τ_ii–jj = τ_ii–ij + τ_ij–jj, determinados por 〈P_ii|P_ij〉 y 〈P_ij|P_jj〉. El camino entre dos estados viene dado por una rotación en la esfera de Bloch, descrita por una transformación unitaria; la transición entre P_ii y P_jj requiere dos transformaciones unitarias, una entre P_ii y P_ij, sea P_ij = U^u_ii–ij P_ii, y otra entre P_ij y P_jj, sea P_jj = U^d_ij–jj P_ij. Así una solución al problema para cuatro ciudades (ilustrado en la figura), sea c₁ → c₂ → c₃ → c₄ → c₁, corresponderá a la secuencia de transformaciones unitarias (indicadas por flechas) entre los siguientes estados P₁₁ → P₁₂ → P₂₂ → P₂₃ → P₃₃ → P₃₄ → P₄₄ → P₄₁ → P₁₁. Para n ciudades hay que aplicar 2 (n−1) transformaciones unitarias.

El principio de superposición de la física cuántica permite aplicar una transformación unitaria que sea combinación lineal de varias transformaciones unitarias (lo que se suele llamar paralelismo cuántico). Así podemos aplicar a P₁₁ una transformación unitaria de tipo U^u P₁₁ = (α_11–12 U^u_11–12 + α_11–13 U^u_11–13 + α_11–14 U^u_11–14) P₁₁, que dará lugar a una combinación lineal de estados α_11–12 |P₁₂ 〉+ α_11–13 |P₁₃〉+ α_11–14 |P₁₄〉. De esta forma se aplica una única operación cuántica que corresponde a nivel clásico a (n−1) operaciones. Una vez aplicadas dichas transformaciones (que en una simulación clásica son triviales de implementar, pero que en una realización física requieren una fidelidad exquisita) hay que realizar una serie de medidas cuánticas del estado en la penúltima etapa del algoritmo con objeto de estimar los coeficientes que multiplican la superposición de estados 〈P_i1|P_j1〉.

Las medidas cuánticas finales son el paso más incierto de todo el algoritmo. En el artículo no se presenta ninguna estimación de cuántas medidas cuánticas hay que realizar para obtener una estimación de dichos coeficientes con una fidelidad suficiente en función del número de ciudades. Para pocas ciudades representadas por estados bien separados en la esfera de Bloch (como en todos los ejemplos que se presentan en el artículo) no se necesitan muchas medidas cuánticas. Pero cuando el número de ciudades crece y hay acumulación de estados en la esfera de Bloch (el peor caso para el algoritmo), podría ocurrir que el número de medidas creciera de forma exponencial. En dicho caso, el algoritmo no presentaría ninguna ventaja cuántica (no sería eficiente en su peor caso).

Usando los valores de dichas medidas cuánticas de 〈P_i1|P_j1〉 se obtiene una matriz de coeficientes para un sistema lineal de ecuaciones. Su solución permite determinar el ciclo hamiltoniano óptimo que resuelve el problema TSP. Quizás no comprendas todos los detalles, pero lo que me gustaría que entendieras es que (1) hay que usar estados cuánticos en la esfera de Bloch de altísima fidelidad, (2) hay que aplicar transformaciones unitarias arbitrarias con altísima precisión, y (3) hay que realizar un gran número de medias cuánticas que estimen los solapes entre estados con altísima exactitud. Todo ello requiere un cúbit ideal, muy alejado de los cúbits reales actuales. Los resultados de la simulaciones para entre 4 y 9 ciudades (bien separadas en la esfera de Bloch) son prometedores; aunque no siempre se obtiene la solución óptima y el error crece con el número de ciudades. Como ilustra esta figura, los resultados para entre 4 y 6 ciudades son aceptables para problemas TSP simétricos, pero para problemas asimétricos, sobre todo entre 7 y 9 ciudades, dejan bastante que desear.

En resumen, un artículo más interesante como idea de concepto que por sus resultados. Con lo rápido que avance al campo de la computación cuántica estoy seguro de que habrá grandes mejoras en este algoritmo en los próximos años (y quizás alguna permita su implementación física con tecnología de cúbits NISQ). Además, habrá avances a nivel teórico, que aclararán si el nuevo algoritmo es eficiente o no lo es (debo confesar que tengo serias dudas de que sea eficiente para un gran número de ciudades). Habrá que estar al tanto de los progresos sobre este tema.