Treinta años después, un impulso para la factorización cuántica | Revista Quanta

Pedro Shor no se propuso romper Internet. Pero un algoritmo que desarrolló a mediados de los años 1990 amenazaba con hacer justamente eso. en un papel de referencia, Shor mostró cómo una computadora hipotética que explotara las peculiaridades de la física cuántica podría descomponer grandes números en sus factores primos mucho más rápido que cualquier máquina clásica ordinaria.

El resultado tuvo implicaciones mucho más allá de las matemáticas. En ese momento, un componente vital de la seguridad de Internet llamado criptografía de clave pública Se basó en el supuesto de que factorizar números grandes es tan difícil desde el punto de vista computacional que resulta efectivamente imposible. Esa suposición todavía sustenta algunos protocolos críticos en la actualidad. El algoritmo de Shor demostró que fallaría espectacularmente en un mundo con potentes computadoras cuánticas.

En los últimos 30 años, los científicos informáticos han optimizado el algoritmo de Shor en preparación para el día en que la tecnología cuántica madure lo suficiente como para ejecutarlo. Pero una nueva variante, del informático de la Universidad de Nueva York Oded Regev, es más rápido en un sentido fundamentalmente nuevo. Es el primero en mejorar la relación entre el tamaño del número que se factoriza y el número de operaciones cuánticas necesarias para factorizarlo.

"Es realmente sorprendente que alguien aparentemente haya podido mejorar la complejidad de este resultado muchos, muchos años después", dijo Ashley Montanaro, investigador de computación cuántica de la Universidad de Bristol. "Esto es realmente emocionante".

Martín Ekerå, un criptógrafo de la Autoridad Nacional de Seguridad de las Comunicaciones de Suecia, estuvo de acuerdo en que el artículo de Regev es interesante, pero advirtió que superar los últimos avances en la práctica requerirá una mayor optimización. "Los algoritmos originales de Shor ya son sorprendentemente eficientes, por lo que no es trivial realizar mejoras importantes", escribió en un correo electrónico.

Regev desarrolló su nuevo algoritmo aumentando el algoritmo de Shor con técnicas de una rama de la criptografía que se ocupa de la geometría de alta dimensión.

"Habría pensado que cualquier algoritmo que funcionara con este esquema básico estaría condenado al fracaso", dijo Shor, un matemático aplicado que ahora trabaja en el Instituto de Tecnología de Massachusetts. "Pero estaba equivocado."

Encontrar factores

Las computadoras cuánticas obtienen su poder de la forma peculiar en que procesan la información. Las computadoras clásicas usan bits, cada uno de los cuales siempre debe estar en uno de dos estados, denominados 0 y 1. Los bits cuánticos, o “qubits”, también pueden estar en combinaciones de sus estados 0 y 1, un fenómeno llamado superposición. También es posible lograr que varios qubits entren en un estado de superposición colectiva: una superposición de dos qubits tiene cuatro componentes que pueden realizar diferentes cálculos simultáneamente, y el número de dichos componentes crece exponencialmente a medida que aumenta el número de qubits. Eso permite a las computadoras cuánticas realizar de manera efectiva exponencialmente muchos cálculos diferentes en paralelo.

Pero hay una trampa: Leer el resultado de un cálculo realizado en superposición solo revela la respuesta a la parte calculada por un componente aleatorio. Para aprovechar los beneficios de la computación en superposición, de alguna manera debe asignar el resultado final a un estado más simple donde sea seguro leer el resultado. Eso no es posible en la mayoría de los casos y al principio nadie sabía cómo solucionar ningún problema. "Había muy pocas personas que tuvieran el coraje de pensar en cálculos cuánticos", dijo Regev.

Luego, en 1994, Shor leyó un papel del informático Daniel Simon que mostró cómo explotar la superposición cuántica para resolver un problema artificial. Shor descubrió cómo extender el resultado de Simon a un problema más general y práctico llamado búsqueda de períodos. Se dice que una función matemática es periódica cuando su salida pasa repetidamente por los mismos valores a medida que aumenta la entrada; la duración de un solo ciclo se conoce como período de la función.

Para encontrar el período de una función determinada usando una computadora cuántica, comience configurando una superposición muy grande en la que cada componente calcula la salida de la función para una entrada diferente. Luego use el método de Shor para convertir esa gran superposición en un estado más simple y lea el resultado. En ese momento, una computadora clásica puede hacerse cargo y finalizar el cálculo rápidamente. En general, el algoritmo de búsqueda de períodos de Shor se ejecuta exponencialmente más rápido que cualquier alternativa clásica porque calcula diferentes resultados de la función periódica simultáneamente mediante superposición.

Mientras Shor buscaba aplicaciones para su algoritmo cuántico de búsqueda de períodos, redescubrió un teorema matemático previamente conocido pero oscuro: para cada número, existe una función periódica cuyos períodos están relacionados con los factores primos del número. Entonces, si hay un número que desea factorizar, puede calcular la función correspondiente y luego resolver el problema usando la búsqueda de períodos: "exactamente en qué son tan buenos los ordenadores cuánticos", dijo Regev.

En una computadora clásica, esta sería una forma terriblemente lenta de factorizar un número grande; más lenta incluso que intentar todos los factores posibles. Pero el método de Shor acelera el proceso exponencialmente, lo que hace que encontrar una forma ideal de construir un algoritmo de factorización cuántica rápido.

El algoritmo de Shor fue uno de los primeros resultados clave que transformaron la computación cuántica de un oscuro subcampo de la informática teórica al gigante que es hoy. Pero poner el algoritmo en práctica es una tarea desalentadora, porque las computadoras cuánticas son notoriamente susceptibles a errores: además de los qubits necesarios para realizar sus cálculos, necesitan muchos otros para realizarlos. trabajo extra para evitar que fracasen. A documento reciente por Ekerå y el investigador de Google craig gidney estima que utilizar el algoritmo de Shor para factorizar un número estándar de seguridad de 2,048 bits (de unos 600 dígitos de longitud) requeriría una computadora cuántica con 20 millones de qubits. Las máquinas más modernas de hoy en día tienen como máximo unos cientos.

Es por eso que algunos protocolos críticos de Internet todavía dependen de lo difícil que es factorizar números grandes, pero los investigadores no quieren volverse demasiado complacientes. teorético y las innovaciones tecnológicas podrían reducir aún más la cuenta de qubits requerida, y no hay pruebas de que el algoritmo de Shor sea óptimo; podría haber un algoritmo de factorización cuántica mejor que nadie ha descubierto.

Si es así, dijo Regev, "deberíamos saberlo lo antes posible, antes de que sea demasiado tarde".

perdido en los arboles

Regev comenzó su carrera académica a finales de la década de 1990, cuando los criptógrafos buscaban una nueva forma de criptografía de clave pública que no fuera vulnerable al algoritmo de Shor. El enfoque más prometedor, llamado criptografía basada en celosía, se basa en la aparente dificultad de los problemas computacionales que involucran matrices de puntos o redes de alta dimensión. Uno de esos problemas es similar a la tarea de localizar el árbol más cercano a un punto aleatorio en un bosque.

"Si se trata de un bosque de cien dimensiones, entonces es mucho más complicado que si se trata de un bosque de dos dimensiones", dijo Greg Kuperberg, matemático de la Universidad de California, Davis.

Regev comenzó a estudiar la criptografía basada en celosías como postdoctorado, inicialmente como atacante; quería probar el nuevo enfoque encontrando debilidades que una computadora cuántica podría explotar. Pero no pudo hacer ningún progreso y pronto se preguntó si había una razón más profunda para ello. En 2005, encontró una manera de convertir esos ataques fallidos en una forma de criptografía basada en celosía superior a todas las demás variantes.

"Oded es absolutamente brillante con las celosías", dijo Kuperberg.

A lo largo de los años, mientras Regev enseñaba el algoritmo de Shor a sucesivas generaciones de estudiantes, se preguntó si las técnicas que había utilizado para atacar la criptografía basada en celosías podrían resultar realmente útiles en los algoritmos de factorización. Esto se debe a que un paso en la etapa final y clásica del algoritmo de Shor equivale a encontrar el punto más cercano en una red unidimensional. Ese problema unidimensional es trivialmente sencillo, pero el parecido con el problema análogo en cientos de dimensiones cuya dureza sustenta la criptografía basada en celosías era inconfundible.

“Si eres alguien que hace celosías como yo, piensas: 'Está bien, hay una celosía aquí'”, dijo Regev. "Pero no tenía claro cómo utilizarlo". Durante años jugó con otras ideas para nuevos algoritmos de factorización cuántica, pero nunca llegó a ninguna parte. Luego, el invierno pasado volvió al problema y decidió precisar esa tentadora conexión entre el factoring y la criptografía basada en celosías. Esta vez encontró el éxito.

Dimensiones adicionales

Regev sabía que necesitaba comenzar generalizando la función periódica en el corazón del algoritmo de Shor de una dimensión a muchas dimensiones. En el algoritmo de Shor, esa función implica multiplicar repetidamente un número aleatorio, denominado g, consigo mismo. Pero el período de esta función (el número de veces que debes multiplicar por g antes de que la salida de la función comience a repetirse, puede ser muy grande, y eso significa que una computadora cuántica debe multiplicar números grandes en algunos componentes de la superposición que usa para calcular la función periódica. Esas grandes multiplicaciones son la parte más costosa desde el punto de vista computacional del algoritmo de Shor.

La función bidimensional análoga utiliza en cambio un par de números, g₁ y g₂. Implica multiplicar g₁ consigo mismo muchas veces y luego multiplicando repetidamente por g₂. El período de esta función también es bidimensional: está definido por el número de g₁ multiplicaciones y g₂ multiplicaciones que juntas hacen que la salida de la función comience a repetirse. Hay muchas combinaciones diferentes de g₁ y g₂ multiplicaciones que funcionarán.

Regev trabajó en los detalles técnicos para generalizar el algoritmo a un número arbitrario de dimensiones, no sólo dos, pero sus resultados iniciales no fueron alentadores. Para calcular la función periódica en muchas dimensiones, la computadora cuántica todavía tendría que multiplicar muchos números. No sería necesario multiplicar cada número tantas veces como en el caso unidimensional, pero había más números distintos para multiplicar. Todo parecía un lavado de cara.

“Piensas: 'Genial, hice todo en dimensiones altas y tiene exactamente el mismo tiempo de ejecución que el de Shor'”, dijo Regev. "Me quedé atrapado con eso por un tiempo". Luego se dio cuenta de que podía solucionar el problema cambiando el orden de las multiplicaciones. En lugar de agregar repetidamente números a un solo producto que crecería progresivamente a lo largo del cálculo cuántico, comenzó con pares de números pequeños, multiplicó los productos resultantes y prosiguió hacia arriba. El número total de multiplicaciones no cambió mucho, pero ahora casi todas involucran números relativamente pequeños, lo que hace que el cálculo sea más rápido.

“Eso marca la diferencia en el mundo”, dijo Vinod Vaikuntanathan, criptógrafo del MIT.

Al principio, parecía como si Regev acabara de sustituir un problema por otro. Había acelerado el cálculo cuántico de la función periódica aumentando el número de dimensiones, pero el cálculo clásico posterior requerido para extraer el período ahora era similar a localizar el punto reticular más cercano en un espacio de alta dimensión, una tarea que se creía ampliamente que Se duro. La analogía con la criptografía reticular que motivó su nuevo enfoque parecía condenarlo al fracaso.

Una fría mañana de marzo, antes de un viaje a un seminario en la Universidad de Princeton, Regev se encontró esperando al colega con el que compartía el viaje. “Llegué temprano y él llegó tarde a recoger el auto”, dijo. Mientras estaba sentado esperando, de repente se le ocurrió la última pieza del rompecabezas. "Ese fue el momento en que las cosas encajaron, pero estuvo cocinándose por un tiempo".

Todo se redujo al número correcto de dimensiones. Cuando la dimensión de la red era demasiado baja, su algoritmo no podía aprovechar al máximo la aceleración obtenida al multiplicar números más pequeños. Cuando era demasiado alto, el cálculo cuántico era rápido, pero la parte clásica requería resolver un problema de red prohibitivamente difícil. Regev había sabido desde el principio que para tener alguna esperanza de éxito, tendría que trabajar en algún punto intermedio, pero no estaba claro si existía un punto óptimo. Esa mañana de marzo, se dio cuenta de cómo podía modificar los detalles del algoritmo para que se ejecutara rápidamente en unas pocas docenas de dimensiones.

escribiendo en la arena

La mejora fue profunda. El número de pasos lógicos elementales en la parte cuántica del algoritmo de Regev es proporcional a n^1.5 al factorizar un n-número de bits, en lugar de n² como en el algoritmo de Shor. El algoritmo repite esa parte cuántica unas cuantas docenas de veces y combina los resultados para trazar una red de alta dimensión, de la cual puede deducir el período y factorizar el número. Por lo tanto, es posible que el algoritmo en su conjunto no se ejecute más rápido, pero acelerar la parte cuántica reduciendo el número de pasos requeridos podría facilitar su puesta en práctica.

Por supuesto, el tiempo que lleva ejecutar un algoritmo cuántico es sólo una de varias consideraciones. Igualmente importante es el número de qubits necesarios, que es análogo a la memoria necesaria para almacenar valores intermedios durante un cálculo clásico ordinario. El número de qubits que requiere el algoritmo de Shor para factorizar un nEl número de bits es proporcional a n, mientras que el algoritmo de Regev en su forma original requiere un número de qubits proporcional a n^1.5 – una gran diferencia para los números de 2,048 bits.

En la informática clásica, la velocidad suele ser una consideración más importante que la memoria, porque los bits clásicos son extremadamente robustos: puedes guardar un archivo en tu computadora y no preocuparte de que cambie aleatoriamente cuando lo vuelvas a abrir más tarde. Los investigadores de computación cuántica no siempre tienen tanta suerte.

"Nuestros qubits intentan constantemente desmoronarse y nosotros intentamos evitar que se desmoronen", dijo Gidney. "Es como si intentaras escribir en la arena y el viento se lo llevara". Eso significa que los qubits adicionales requeridos por el algoritmo de Regev podrían ser un gran inconveniente.

Pero el artículo de Regev no es el final de la historia. Hace dos semanas, Vaikuntanathan y su estudiante graduado Seyoon Ragavan encontraron una manera de reducir el uso de memoria del algoritmo. Su variante del algoritmo de Regev, al igual que el algoritmo original de Shor, requiere un número de qubits proporcional a n más bien que n^1.5. Ekerå escribió en un correo electrónico que el trabajo "nos acerca mucho más a una implementación que sería más eficiente en la práctica".

La lección más amplia del nuevo algoritmo de Regev, más allá de las implicaciones para la factorización, es que los investigadores de la computación cuántica siempre deben estar abiertos a las sorpresas, incluso en problemas que se han estudiado durante décadas.

"Esta variante de mi algoritmo no se descubrió durante 30 años y surgió de la nada", dijo Shor. "Probablemente todavía queden muchos otros algoritmos cuánticos por encontrar".

Nota del editor: Oded Regev recibe financiación del Fundación Simons, que también financia esta revista editorialmente independiente. Las decisiones de financiación de la Fundación Simons no influyen en nuestra cobertura. Más detalles son disponible aquí.

¿Cuánto está realizando una serie de encuestas para servir mejor a nuestra audiencia. Toma nuestro encuesta a lectores de informática y entrarás para ganar gratis ¿Cuánto merchandising