La computación cuántica ofrece la esperanza de un aumento espectacular de las capacidades computacionales. Esa es la promesa de los ordenadores cuánticos, que pueden manejar cientos de miles o millones de bits cuánticos o cúbits.
Pero, por el momento, las máquinas de última generación apenas logran manejar unas pocas docenas de cúbits y aún no pueden superar a las computadoras clásicas de manera significativa. Parte del problema es que los algoritmos cuánticos generalmente requieren cientos o miles de cúbits, incluso para problemas simples. Por eso, los matemáticos y los científicos informáticos están buscando desesperadamente algoritmos más elegantes que dependan de menos cúbits.
Kapil Goswami y sus colegas de la Universidad de Hamburgo (Alemania) han descubierto una forma de resolver el problema del viajante de comercio utilizando un único cúbit. Afirman que el enfoque podría aplicarse a otros problemas y tiene el potencial de transformar la forma en que los científicos informáticos piensan sobre los algoritmos cuánticos.
El problema del viajante es un problema de optimización combinatoria y uno de los acertijos más estudiados en matemáticas. El desafío consiste en encontrar la ruta más corta que pase por todas las ciudades de una lista dada. Hasta donde saben los matemáticos, la única forma de hacerlo es calcular la longitud de todas las rutas y luego elegir la más corta.
Esto es sencillo cuando el número de ciudades es pequeño. Pero a medida que este número crece, las rutas posibles aumentan a un ritmo que depende de n!, el factorial del número de ciudades. Por lo tanto, 4! es 24, pero 10! es 3.628.800 y 100! es 9 x 10^157. Por lo tanto, esto se vuelve rápidamente imposible incluso para las computadoras convencionales más potentes.
Esfera elegante
Así que, en lugar de buscar soluciones exactas, los científicos informáticos han desarrollado algoritmos que calculan rutas óptimas, que pueden no ser las más cortas, pero que probablemente estén dentro de un pequeño porcentaje de esa distancia. Pero incluso estas requieren un gran esfuerzo computacional cuando el número de ciudades es grande.
La computación cuántica ha prometido desde hace tiempo acelerar estos algoritmos, pero Goswami y sus colegas afirman que incluso los mejores algoritmos cuánticos requieren una gran cantidad de cúbits. “El algoritmo cuántico para codificar problemas de 9 y 10 ciudades en una arquitectura cuántica de ondas D requiere 73 cúbits lógicos o 5436 cúbits físicos”, afirman.
Por lo tanto, reducirlo a tan solo 1 cúbit es un avance significativo. Goswami y sus colegas utilizan una forma de representar el espacio de estados de un sistema cuántico como un globo geométrico, conocido como esfera de Bloch. Luego representan la ubicación de las ciudades como estados cuánticos en una esfera de Bloch. De este modo, el proceso de viajar de una ciudad a otra se puede lograr mediante una serie de rotaciones de la esfera.
De hecho, es posible que la esfera represente las rutas desde cada ciudad hacia todas las demás mediante el proceso de superposición. “Usamos la superposición de estados para viajar por múltiples caminos a la vez”, dicen. Luego es posible seleccionar la ruta óptima mediante la medición adecuada del estado cuántico.
Este método funciona con cualquier ordenador cuántico que tenga la capacidad de rotar un cúbit de cualquier forma, lo que incluye máquinas superconductoras, máquinas de plataformas de iones atrapados, centros de nitrógeno vacante en diamantes, etc.
Los resultados son significativamente mejores que los obtenidos hasta ahora con dispositivos mucho más grandes. “Hemos demostrado que, para problemas de vendedores ambulantes en cuatro o seis ciudades, el algoritmo encuentra la solución exacta para la mayoría de las instancias del problema, lo que es mucho mejor que los esquemas cuánticos actuales”, afirman Goswami y compañía.
Para un mayor número de ciudades, los estados cuánticos deben estar más juntos en la superficie de la esfera y esto los hace más vulnerables al ruido y los errores. Sin embargo, el equipo ha tenido éxito con problemas de hasta 9 ciudades.
Búsqueda cuántica
Se trata de un trabajo fascinante con un potencial considerable. El equipo afirma que el proceso de visualización de problemas representados en una esfera geométrica es en sí mismo un avance importante porque abre inmediatamente el camino para representar otros problemas de la misma manera. “Nuestro esquema actuará como plantilla para seguir desarrollando algoritmos que utilicen el principio de superposición para la eficiencia de los recursos”, afirman los investigadores.
En particular, el equipo señala que la búsqueda a través de una superposición de estados en una esfera de Bloch es matemáticamente similar al algoritmo de búsqueda cuántica de Grover, uno de los algoritmos cuánticos más simples y poderosos y que es drásticamente más rápido que los algoritmos clásicos. Esto sugiere que, independientemente de cómo se aplique, este enfoque debería lograr una velocidad similar en comparación con los algoritmos clásicos.
Si bien las computadoras cuánticas continúan siendo máquinas ruidosas con un número limitado de qubits, esto convierte a las Esferas de Bloch en una nueva herramienta prometedora en el arsenal cuántico.
Ref.: Solución del problema del viajante de comercio utilizando un único qubit: arxiv.org/abs/2407.17207