Un nuevo algoritmo cuántico acelera la resolución de una enorme clase de problemas

La versión original de esta historia apareció en Quanta Magazine .

Para los informáticos, resolver problemas es como escalar montañas. Primero deben elegir un problema —similar a identificar una cima que escalar— y luego desarrollar una estrategia para resolverlo. Los investigadores clásicos y cuánticos compiten con estrategias diferentes, con una sana rivalidad entre ambos. Los investigadores cuánticos informan de una forma rápida de resolver un problema —a menudo escalando una cima que nadie creía que valiera la pena escalar—; luego, los equipos clásicos compiten para ver si pueden encontrar una mejor manera.

Esta competencia casi siempre termina en un empate: cuando los investigadores creen haber ideado un algoritmo cuántico que funciona más rápido o mejor que cualquier otro, los investigadores clásicos suelen idear uno que lo iguala. Justo la semana pasada, una supuesta aceleración cuántica, publicada en la revista Science , fue recibida con escepticismo inmediato por dos grupos distintos que demostraron cómo realizar cálculos similares en máquinas clásicas.

Pero en un artículo publicado el año pasado en el sitio web de prepublicaciones científicas arxiv.org, investigadores describieron lo que parece una aceleración cuántica convincente y útil . Los investigadores describieron un nuevo algoritmo cuántico que funciona más rápido que todos los algoritmos clásicos conocidos para encontrar buenas soluciones a una amplia gama de problemas de optimización (que buscan la mejor solución posible entre un gran número de opciones).

Hasta ahora, ningún algoritmo clásico ha destronado al nuevo algoritmo, conocido como interferometría cuántica decodificada (DQI). Es "un gran avance en algoritmos cuánticos", dijo Gil Kalai , matemático de la Universidad Reichman y un destacado escéptico de la computación cuántica . Los informes de algoritmos cuánticos entusiasman a los investigadores, en parte porque pueden arrojar luz sobre nuevas ideas sobre problemas difíciles y en parte porque, a pesar de todo el revuelo en torno a las máquinas cuánticas, no está claro qué problemas se beneficiarán realmente de ellas. Un algoritmo cuántico que supere a todos los clásicos conocidos en tareas de optimización representaría un gran paso adelante en el aprovechamiento del potencial de las computadoras cuánticas.

"Estoy entusiasmado", afirmó Ronald de Wolf , informático teórico del CWI, el instituto nacional de investigación en matemáticas e informática de los Países Bajos, quien no participó en el nuevo algoritmo. Sin embargo, advirtió que aún es muy posible que los investigadores encuentren un algoritmo clásico con el mismo rendimiento. Y debido a la falta de hardware cuántico, aún pasará un tiempo antes de que puedan probar el nuevo algoritmo empíricamente.

El algoritmo podría inspirar nuevos trabajos en el ámbito clásico, según Ewin Tang , científica informática de la Universidad de California, Berkeley, quien se hizo famosa en su adolescencia al crear algoritmos clásicos que se asemejan a los cuánticos . Las nuevas afirmaciones «son tan interesantes que les diría a quienes se dedican a los algoritmos clásicos: 'Deberían consultar este artículo y trabajar en este problema'», afirmó.

Cuando los algoritmos clásicos y cuánticos compiten, a menudo lo hacen en el campo de batalla de la optimización, un campo centrado en encontrar las mejores opciones para resolver un problema complejo. Los investigadores suelen centrarse en problemas en los que el número de posibles soluciones se dispara a medida que el problema se hace más grande. ¿Cuál es la mejor manera de que un camión de reparto visite 10 ciudades en tres días? ¿Cómo se deben empacar los paquetes en la parte trasera? Los métodos clásicos para resolver estos problemas, que a menudo implican analizar las posibles soluciones de forma ingeniosa, se vuelven rápidamente insostenibles.

El problema de optimización específico que aborda DQI es, en líneas generales, el siguiente: Se te proporciona un conjunto de puntos en una hoja de papel. Debes crear una función matemática que pase por estos puntos. En concreto, la función debe ser un polinomio: una combinación de variables elevadas a exponentes enteros y multiplicadas por coeficientes. Sin embargo, no puede ser demasiado compleja, es decir, las potencias no pueden ser demasiado altas. Esto te da una línea curva que se mueve hacia arriba y hacia abajo a medida que se desplaza por la página. Tu tarea es encontrar la línea ondulada que toque la mayor cantidad de puntos.

Este problema se presenta en diversas formas en la informática, especialmente en la codificación de errores y la criptografía, campos centrados en la codificación segura y precisa de datos durante su transmisión. Los investigadores del DQI reconocieron, básicamente, que trazar una línea más precisa es similar a acercar un mensaje codificado con ruido a su significado preciso.

Pero todo eso vino después. Cuando los investigadores de DQI empezaron a trabajar en su algoritmo, ni siquiera tenían este problema en mente.

“Habría sido perfectamente plausible para un investigador con objetivos definidos comenzar planteando el problema y luego investigar si los algoritmos cuánticos podrían resolverlo más rápido que los algoritmos clásicos”, afirmó Stephen Jordan , físico de Google Quantum AI y uno de los principales arquitectos de DQI. “Claro que en nuestro caso no fue así. Lo encontramos por un camino tortuoso y retrógrado”.

Jordan emprendió ese camino en 2023, cuando se incorporó a Google y descubrió que trabajaría con Eddie Farhi , físico de Google cuyo trabajo se ha centrado durante mucho tiempo en algoritmos cuánticos que superan a los clásicos. (Farhi fue asesor doctoral de Jordan en el Instituto Tecnológico de Massachusetts). Jordan sabía que, en 2014, Farhi había realizado un análisis cuántico de un problema de optimización al considerar la energía, donde las energías más bajas corresponden a mejores soluciones. Para Farhi, la energía conectaba la optimización con la física cuántica.

Pero Jordan quería hacer algo diferente. Recurrió a otro concepto inherente a la física cuántica: reconocer todo como ondas. Mediante una herramienta matemática llamada transformada cuántica de Fourier, Jordan encontró la manera de traducir todas las posibles respuestas a un conocido tipo de problemas de optimización en ondas cuánticas. De este modo, pudo manipular el sistema cuántico para que ondas más grandes (en forma de amplitudes cuánticas más altas) correspondieran a mejores soluciones.

Pero aún quedaba un gran desafío por superar. En un sistema cuántico, preguntar "¿Cuál es la mayor amplitud?" no es tan sencillo como reconocer la ola más grande en la playa. El panorama cuántico es increíblemente complejo, y no estaba claro cómo identificar las amplitudes cuánticas que corresponderían a las mejores soluciones.

Tras muchos intentos fallidos, Jordan logró un gran avance: el proceso de selección de las mejores soluciones resultó ser similar al de decodificación, un proceso que elimina errores en los mensajes codificados. Esta es un área muy estudiada de la informática, repleta de técnicas que Jordan pudo explorar. Al traducir un problema de optimización a uno cuántico y aplicarle la perspectiva de la decodificación, Jordan descubrió una nueva forma de desarrollar algoritmos cuánticos.

Junto con Noah Shutty , también de Google, Jordan comenzó a probar esquemas de decodificación, observando su rendimiento frente a los algoritmos clásicos en diversos problemas de optimización. Necesitaban el enfoque adecuado y un problema donde funcionara. «Resulta que los algoritmos clásicos son difíciles de superar», dijo Jordan. «Después de varios meses intentándolo, aún no habíamos conseguido ninguna victoria para la cuántica».

Pero finalmente, la pareja dio con un algoritmo de decodificación introducido por primera vez en la década de 1960 para encontrar y corregir errores individuales en un mensaje codificado. Encontrar ese problema fue la clave. "Cuando investigamos, tuvimos éxito casi de inmediato", dijo Jordan. Finalmente, encontraron un problema y un enfoque que, en conjunto, parecían una aceleración cuántica.

Por supuesto, eso no significaba que fuera infalible. «Quizás exista algún método clásico que pueda replicar eficientemente todo el enfoque», dijo Jordan. «Estas descuantificaciones no siempre son obvias».

Para disipar esos temores, consultaron con Mary Wootters , experta en teoría de la codificación (y exasesora de doctorado de Shutty en la Universidad de Stanford). Ella buscó cuidadosamente cualquier algoritmo clásico conocido que pudiera igualar su aceleración cuántica. La ventaja se mantuvo. Las comprobaciones del equipo también sugieren que se mantendrá. "Hicieron la debida diligencia", dijo Tang.

Con este análisis como base, analizaron con mayor detenimiento el problema de optimización que estaban resolviendo. A Jordan le preocupaba que fuera demasiado específico, sin aplicaciones más amplias, pero Shutty reconoció que este problema de decodificación era una variante de problemas bien conocidos y útiles en el cifrado y otros campos.

Jordan reconoce que, sin una máquina cuántica lo suficientemente grande, la DQI seguirá siendo un avance teórico. «La DQI no puede ejecutarse en las computadoras cuánticas actuales», afirmó. Pero siguen avanzando. Desde que el grupo publicó su trabajo el pasado agosto, han extendido la aplicación de la DQI más allá del problema original a una clase más amplia de problemas de optimización, que incluye más casos de estos problemas de «mejor camino».

Hasta ahora, dijo Jordan, espera que DQI pueda superar a los algoritmos clásicos también en esos problemas.

Por el momento, la comunidad cuántica sigue entusiasmada. «Encontrar algoritmos cuánticos que muestren una ventaja sobre los algoritmos clásicos es un proyecto muy emocionante de las últimas tres décadas, y el número de algoritmos concretos que muestran dicha ventaja no es elevado», afirmó Kalai. «Por lo tanto, cada nuevo algoritmo es motivo de celebración».

Historia original reimpresa con permiso de Quanta Magazine , una publicación editorialmente independiente de la Fundación Simons cuya misión es mejorar la comprensión pública de la ciencia cubriendo los desarrollos de investigación y las tendencias en matemáticas y ciencias físicas y de la vida.