En la práctica, muchos programas diseñados para computadoras clásicas no pueden ejecutarse en computadoras cuánticas porque no pueden olvidar selectivamente la información. El nuevo algoritmo de multiplicación muestra cómo solucionar este problema.
Los bits clásicos son en blanco y negro, y los bits cuánticos son un poco más complicados.Cuando tenía 9 años, mis padres compraron una computadora nueva. En casi todos los aspectos, era mejor que el anterior, excepto uno: mis carreras favoritas no comenzaron en él. Recuerdo cómo pensé: ¿por qué necesito una computadora nueva si no inicia mi programa favorito?
Las computadoras cuánticas tienen el mismo problema. En teoría, son capaces de todo lo que el clásico es capaz de hacer. En la práctica, su naturaleza cuántica hace que sea casi imposible ejecutar algunos de los algoritmos clásicos más importantes.
Es por eso que el
trabajo , publicado el 15 de abril, contiene buenas noticias.
Craig Gidney , un científico informático de Google AI Quantum, con sede en Santa Bárbara, California, describe una versión cuántica del algoritmo clásico para multiplicar rápidamente números muy grandes. En las computadoras clásicas, este algoritmo ha estado funcionando durante bastante tiempo. Pero antes del trabajo de Gidney, no estaba claro si sería posible adaptarlo para máquinas cuánticas.
Más importante aún, el algoritmo de multiplicación pertenece a la clase de algoritmos ubicuos de informática. Gidney cree que su nueva técnica permitirá que las computadoras cuánticas implementen toda la clase de estos algoritmos, que hasta ahora se han considerado demasiado engorrosos para usar en una máquina cuántica.
Este algoritmo de multiplicación aprovecha el descubrimiento, que fue el primer avance en la multiplicación realizada durante varios miles de años. El método tradicional de multiplicación de la escuela requiere n
2 pasos, donde n es el número de caracteres en los números multiplicados. Durante varios miles de años, los matemáticos creyeron que no existía un enfoque más eficiente.
Pero, como aclaramos recientemente en el artículo "Los
matemáticos descubrieron la forma ideal de multiplicar números "
, en 1960, el matemático soviético Anatoly Karatsuba descubrió una forma más rápida. Su método era dividir números largos en números más cortos. Para multiplicar dos números de ocho dígitos, por ejemplo, primero debe dividirlos en dos números de cuatro dígitos, luego dividirlos en dos números de dos dígitos. Luego debe realizar varias operaciones con números de dos dígitos y restaurar el resultado de la multiplicación final. Para multiplicar números muy grandes, el método Karatsuba toma muchos menos pasos que el método escolar.
Cuando una computadora clásica se ejecuta en el algoritmo Karatsuba, elimina información en el proceso. Por ejemplo, restaurando los números de dos dígitos a los de cuatro dígitos, olvida los números de dos dígitos. Ahora solo le interesan los números de cuatro dígitos. La versión clásica del algoritmo es similar a un escalador que tira su equipo mientras sube: puede moverse más rápido si no lleva toda la basura con él.
Pero las computadoras cuánticas no pueden descartar información.
Las computadoras cuánticas realizan cálculos a través de manipulaciones con bits cuánticos o "qubits". Están entrelazados entre sí o confundidos. Esta confusión brinda a las computadoras cuánticas enormes oportunidades: en lugar de almacenar información en bits separados, las computadoras cuánticas utilizan interacciones complejas de todos los qubits. Como resultado, para ciertas tareas, las computadoras cuánticas pueden demostrar una potencia de cómputo exponencialmente mayor en comparación con las clásicas.
Sin embargo, la misma propiedad que hace que las computadoras cuánticas sean tan potentes también las hace frágiles. Como los qubits están enredados, es imposible cambiar algunos de ellos sin afectar a los demás. Esto hace que sea imposible eliminar selectivamente la información disponible para las computadoras clásicas. Hacer retroceder qubits es como cortar partes de una red: incluso un solo corte puede destruir toda la red.
Este requisito para la preservación de la información complica la creación de versiones cuánticas de algoritmos recursivos, es decir, recurrir a ellos mismos. En informática, los algoritmos recursivos se usan ampliamente, sin embargo, para funcionar de la mejor manera, necesitan que la computadora descarte información en cada paso. Sin esto, la informática se volverá poco práctica rápidamente. "Si guarda información cada vez que realiza una operación, el espacio que ocupa crecerá con la cantidad de operaciones", dijo
Ashley Montanaro , especialista en información cuántica de la Universidad de Bristol. Cualquier máquina práctica se quedará sin memoria rápidamente.
En un nuevo trabajo, Gidney describe un método cuántico para implementar la multiplicación de Karatsuba, que no requiere un gran consumo de memoria. En lugar de generar valores intermedios para obtener el resultado final, utiliza el método de "
optimización de recursión de cola " para convertir directamente la entrada en salida. Esto permite que el algoritmo evite crear información intermedia que una computadora cuántica no puede descartar. "Se deshace del problema de los qubits adicionales sin generar qubits adicionales", dijo
Thomas Vaughn , un especialista en información cuántica de la Universidad de Creiton.
Gidney cree que su método funcionará para adaptar muchos algoritmos recursivos clásicos para computadoras cuánticas. Hasta ahora, las computadoras cuánticas están en una etapa tan temprana que apenas pueden hacer frente a la multiplicación de un solo dígito. Sin embargo, el algoritmo está listo, y cuando se mejoren sus esquemas, serán capaces de mucho más.