El problema del viajante se considera un excelente ejemplo de problema de optimización combinatoria. Ahora, un equipo de Berlín dirigido por el físico teórico Prof. Dr. Jens Eisert de la Freie Universität Berlin y HZB ha demostrado que cierta clase de problemas de este tipo pueden resolverse mejor y mucho más rápido con ordenadores cuánticos que con métodos convencionales.
El trabajo del equipo se publica en la revista Science Advances. .
Los ordenadores cuánticos utilizan los llamados qubits, que no son cero ni uno como en los circuitos lógicos convencionales, sino que pueden adoptar cualquier valor intermedio. Estos qubits se obtienen mediante átomos, iones o circuitos superconductores altamente enfriados, y todavía es físicamente muy complejo construir una computadora cuántica con muchos qubits. Sin embargo, ya se pueden utilizar métodos matemáticos para explorar qué podrían lograr en el futuro los ordenadores cuánticos tolerantes a fallos.
"Hay muchos mitos al respecto y, a veces, cierta palabrería y exageración. Pero hemos abordado el tema con rigor, utilizando métodos matemáticos, y hemos obtenido resultados sólidos al respecto. Sobre todo, hemos aclarado en qué sentido puede haber ventajas", afirma el Prof. Dr. Eisert, que dirige un grupo de investigación conjunto en la Freie Universität Berlin y Helmholtz-Zentrum Berlin.
Un excelente ejemplo es el conocido problema del viajante de comercio:un viajero tiene que visitar varias ciudades y luego regresar a su ciudad natal. ¿Cuál es la ruta más corta? Aunque este problema es fácil de entender, se vuelve cada vez más complejo a medida que aumenta el número de ciudades y se dispara el tiempo de cálculo. El problema del viajante representa un grupo de problemas de optimización que tienen una enorme importancia económica, ya se trate de redes ferroviarias, logística u optimización de recursos. Se pueden encontrar soluciones suficientemente buenas utilizando métodos de aproximación.
El equipo dirigido por Eisert y su colega Jean-Pierre Seifert ha utilizado ahora métodos puramente analíticos para evaluar cómo una computadora cuántica con qubits podría resolver este tipo de problemas, un experimento mental clásico con lápiz, papel y mucha experiencia.
"Simplemente asumimos, independientemente de la realización física, que hay suficientes qubits y analizamos las posibilidades de realizar operaciones informáticas con ellos", explica Vincent Ulitzsch, Ph.D. estudiante de la Universidad Técnica de Berlín.
Al hacerlo, el equipo reveló similitudes con un problema bien conocido en criptografía, es decir, el cifrado de datos.
"Nos dimos cuenta de que podíamos utilizar el algoritmo de Shor para resolver una subclase de estos problemas de optimización", afirma Ulitzsch. Esto significa que el tiempo de cálculo ya no "explota" con el número de ciudades (exponencial, 2 N ), pero sólo aumenta polinomialmente, es decir, con N x , donde x es una constante. La solución obtenida de esta manera también es cualitativamente mucho mejor que la solución aproximada usando el algoritmo convencional.
"Hemos demostrado que para una clase específica pero muy importante y prácticamente relevante de problemas de optimización combinatoria, las computadoras cuánticas tienen una ventaja fundamental sobre las computadoras clásicas en ciertos casos del problema", dice Eisert.
Más información: Niklas Pirnay et al, Una ventaja cuántica superpolinomial en principio para aproximar problemas de optimización combinatoria mediante la teoría del aprendizaje computacional, Science Advances (2024). DOI:10.1126/sciadv.adj5170
Proporcionado por la Asociación Helmholtz de Centros de Investigación Alemanes