La versión original de esta historia apareció en Revista cuanta.
Para los científicos informáticos, resolver problemas es un poco como el montañismo. Primero deben elegir un problema para resolver, para identificar un pico para escalar, y luego deben desarrollar una estrategia para resolverlo. Los investigadores clásicos y cuánticos compiten utilizando diferentes estrategias, con una rivalidad saludable entre los dos. Los investigadores cuánticos informan una forma rápida de resolver un problema, a menudo escalando un pico que nadie pensó que valía la pena subir, luego los equipos clásicos corren para ver si pueden encontrar una mejor manera.
Este concurso casi siempre termina como un vínculo virtual: cuando los investigadores piensan que han ideado un algoritmo cuántico que funciona más rápido o mejor que cualquier otra cosa, los investigadores clásicos generalmente se les ocurre uno que lo iguala. La semana pasada, una supuesta acelera cuántica, publicada en la revista Cienciafue recibido con escepticismo inmediato de dos grupos separados que mostraron cómo realizar similar cálculos en máquinas clásicas.
Pero en un artículo publicado en el sitio científico de preimpresión arxiv.org el año pasado, los investigadores describieron lo que parece una aceleración cuántica que es convincente y útil. Los investigadores describieron un nuevo algoritmo cuántico que funciona más rápido que todos los clásicos conocidos para encontrar buenas soluciones para una amplia clase de problemas de optimización (que buscan la mejor solución posible entre una enorme cantidad de opciones).
Hasta ahora, ningún algoritmo clásico ha destronado el nuevo algoritmo, conocido como interferometría cuántica decodificada (DQI). Es “un avance en los algoritmos cuánticos”, dijo Gil Kalaiun matemático en la Universidad de Reichman y un escéptico prominente de computación cuántica. Los informes de algoritmos cuánticos entusiasman a los investigadores, en parte porque pueden iluminar nuevas ideas sobre problemas difíciles, y en parte porque, a pesar de todo el zumbido en torno a las máquinas cuánticas, no está claro qué problemas se beneficiarán realmente de ellos. Un algoritmo cuántico que supera a todos los clásicos conocidos en las tareas de optimización representaría un paso importante para aprovechar el potencial de las computadoras cuánticas.
“Estoy entusiasmado con eso”, dijo Ronald de Wolfun científico informático teórico de CWI, el Instituto Nacional de Investigación de Matemáticas e Informática en los Países Bajos, que no participó en el nuevo algoritmo. Pero al mismo tiempo, advirtió que todavía es muy posible que los investigadores eventualmente encuentren un algoritmo clásico que funcione igual de bien. Y debido a la falta de hardware cuántico, seguirá siendo un tiempo antes de que puedan probar el nuevo algoritmo empíricamente.
El algoritmo podría inspirar un nuevo trabajo en el lado clásico, según Ewin Tangun científico informático de la Universidad de California, Berkeley, que llegó a la fama cuando era adolescente Creación de algoritmos clásicos que coincidan con los cuánticos. Las nuevas afirmaciones “son lo suficientemente interesantes como para decirle a la gente de los algoritmos clásicos:” Oye, deberías mirar este documento y trabajar en este problema “, dijo.
El mejor camino a seguir?
Cuando los algoritmos clásicos y cuánticos compiten, a menudo lo hacen en el campo de batalla de la optimización, un campo se centró en encontrar las mejores opciones para resolver un problema espinoso. Los investigadores generalmente se centran en problemas en los que el número de posibles soluciones explota a medida que el problema se hace más grande. ¿Cuál es la mejor manera para que un camión de reparto visite 10 ciudades en tres días? ¿Cómo debes empacar los parcelas en la parte posterior? Los métodos clásicos para resolver estos problemas, que a menudo implican agitarse a través de posibles soluciones de manera inteligente, se vuelven rápidamente insostenibles.
El problema de optimización específico que DQI aborda es aproximadamente esto: se le da una colección de puntos en una hoja de papel. Debe crear una función matemática que pase a través de estos puntos. Específicamente, su función tiene que ser un polinomio: una combinación de variables elevadas a exponentes de número completo y multiplicada por coeficientes. Pero no puede ser demasiado complicado, lo que significa que los poderes no pueden ponerse demasiado altos. Esto le da una línea curva que se mueve hacia arriba y hacia abajo a medida que se mueve a través de la página. Su trabajo es encontrar la línea Wiggly que toque la mayor cantidad de puntos.
Las variaciones de este problema aparecen en diversas formas en la informática, especialmente en la codificación de errores y la criptografía, los campos centrados en la codificación de forma segura y precisa de los datos a medida que se transmite. Los investigadores de DQI reconocieron, básicamente, que trazar una mejor línea es similar a cambiar un mensaje codificado ruidoso más cerca de su significado preciso.