Los investigadores proponen un circuito de factorización cuántica más pequeño y tolerante al ruido para la criptografía

Es probable que el correo electrónico más reciente que envió haya sido cifrado mediante un método probado y verdadero que se basa en la idea de que incluso la computadora más rápida sería incapaz de dividir eficientemente un número gigantesco en factores.

Por otra parte, los ordenadores cuánticos prometen descifrar rápidamente sistemas criptográficos complejos que un ordenador clásico tal vez nunca podría descifrar. Esta promesa se basa en un algoritmo de factorización cuántica propuesto en 1994 por Peter Shor, que ahora es profesor del MIT.

Pero aunque los investigadores han logrado grandes avances en los últimos 30 años, los científicos aún no han construido una computadora cuántica lo suficientemente potente como para ejecutar el algoritmo de Shor.

Mientras algunos investigadores trabajan para construir ordenadores cuánticos más grandes, otros han estado tratando de mejorar el algoritmo de Shor para que pudiera funcionar en un circuito cuántico más pequeño. Hace aproximadamente un año, el científico informático de la Universidad de Nueva York Oded Regev propuso una importante mejora teórica. Su algoritmo podría funcionar más rápido, pero el circuito requeriría más memoria.

A partir de esos resultados, los investigadores del MIT han propuesto un enfoque que combina la velocidad del algoritmo de Regev con la eficiencia de memoria del de Shor. Este nuevo algoritmo es tan rápido como el de Regev, requiere menos bloques de construcción cuánticos conocidos como qubits y tiene una mayor tolerancia al ruido cuántico, lo que podría hacer que sea más factible de implementar en la práctica.

A largo plazo, este nuevo algoritmo podría contribuir al desarrollo de nuevos métodos de cifrado que puedan resistir el poder de descifrado de códigos de las computadoras cuánticas.

«Si alguna vez se construyen ordenadores cuánticos a gran escala, la factorización se acabará y tendremos que encontrar algo más que utilizar para la criptografía. Pero ¿qué tan real es esta amenaza? ¿Podemos hacer que la factorización cuántica sea práctica?

«Nuestro trabajo podría potencialmente acercarnos un paso más a una implementación práctica», dice Vinod Vaikuntanathan, profesor de Ingeniería de la Fundación Ford, miembro del Laboratorio de Ciencias de la Computación e Inteligencia Artificial (CSAIL) y autor principal de un artículo. papel describiendo el algoritmo.

El autor principal del artículo es Seyoon Ragavan, estudiante de posgrado del Departamento de Ingeniería Eléctrica y Ciencias de la Computación del MIT. La investigación se presentó en la Conferencia Internacional de Criptología de 2024 (Criptomonedas 2024).

Descifrando la criptografía

Para transmitir mensajes de forma segura a través de Internet, los proveedores de servicios como los clientes de correo electrónico y las aplicaciones de mensajería suelen recurrir al sistema RSA, un sistema de cifrado inventado por los investigadores del MIT Ron Rivest, Adi Shamir y Leonard Adleman en la década de 1970 (de ahí el nombre «RSA»). El sistema se basa en la idea de que factorizar un entero de 2048 bits (un número con 617 dígitos) es demasiado difícil para que un ordenador lo haga en un tiempo razonable.

Esa idea cambió radicalmente en 1994, cuando Shor, que entonces trabajaba en Bell Labs, presentó un algoritmo que demostraba que una computadora cuántica podía factorizar lo suficientemente rápido como para romper la criptografía RSA.

«Fue un punto de inflexión, pero en 1994 nadie sabía cómo construir un ordenador cuántico lo suficientemente grande y todavía estamos muy lejos de lograrlo. Hay quien se pregunta si algún día se construirán», afirma Vaikuntanathan.

Se estima que un ordenador cuántico necesitaría unos 20 millones de cúbits para ejecutar el algoritmo de Shor. En la actualidad, los ordenadores cuánticos más grandes tienen alrededor de 1.100 cúbits.

Un ordenador cuántico realiza cálculos utilizando circuitos cuánticos, al igual que un ordenador clásico utiliza circuitos clásicos. Cada circuito cuántico se compone de una serie de operaciones conocidas como puertas cuánticas. Estas puertas cuánticas utilizan cúbits, que son los bloques de construcción más pequeños de un ordenador cuántico, para realizar cálculos.

Pero las puertas cuánticas introducen ruido, por lo que tener menos puertas mejoraría el rendimiento de una máquina. Los investigadores han estado trabajando para mejorar el algoritmo de Shor para que pueda ejecutarse en un circuito más pequeño con menos puertas cuánticas.

Eso es precisamente lo que hizo Regev con el circuito que propuso hace un año.

«Esa fue una gran noticia porque fue la primera mejora real del circuito de Shor desde 1994», dice Vaikuntanathan.

El circuito cuántico que propuso Shor tiene un tamaño proporcional al cuadrado del número que se está factorizando. Esto significa que si se factorizara un entero de 2048 bits, el circuito necesitaría millones de puertas.

El circuito de Regev requiere una cantidad significativamente menor de puertas cuánticas, pero necesita muchos más cúbits para proporcionar suficiente memoria, lo que plantea un nuevo problema.

«En cierto sentido, algunos tipos de cúbits son como manzanas o naranjas. Si los conservamos, se desintegran con el tiempo. Lo que queremos es minimizar la cantidad de cúbits que necesitamos conservar», explica Vaikuntanathan.

En agosto pasado, en un taller, Vaikuntanathan escuchó a Regev hablar sobre sus resultados. Al final de su charla, Regev planteó una pregunta: ¿Alguien podría mejorar su circuito para que necesitara menos cúbits? Vaikuntanathan y Ragavan abordaron esa cuestión.

Ping-pong cuántico

Para factorizar un número muy grande, un circuito cuántico necesitaría ejecutarse muchas veces, realizando operaciones que involucran poderes de cómputo, como 2 elevado a 100.

Pero calcular potencias tan grandes es costoso y difícil de realizar en un ordenador cuántico, ya que los ordenadores cuánticos solo pueden realizar operaciones reversibles. Elevar al cuadrado un número no es una operación reversible, por lo que cada vez que se eleva un número al cuadrado, se debe agregar más memoria cuántica para calcular el siguiente cuadrado.

Los investigadores del MIT encontraron una forma inteligente de calcular exponentes utilizando una serie de números de Fibonacci que requiere una simple multiplicación, que es reversible, en lugar de elevar al cuadrado. Su método necesita solo dos unidades de memoria cuántica para calcular cualquier exponente.

«Es como un juego de ping-pong, donde empezamos con un número y luego rebotamos de un lado a otro, multiplicando entre dos registros de memoria cuántica», añade Vaikuntanathan.

También abordaron el desafío de la corrección de errores. Los circuitos propuestos por Shor y Regev requieren que cada operación cuántica sea correcta para que su algoritmo funcione, dice Vaikuntanathan. Pero las puertas cuánticas libres de errores serían inviables en una máquina real.

Superaron este problema utilizando una técnica para filtrar los resultados corruptos y procesar sólo los correctos.

El resultado final es un circuito que hace un uso mucho más eficiente de la memoria. Además, su técnica de corrección de errores haría que el algoritmo fuera más práctico de implementar.

«Los autores resuelven los dos obstáculos más importantes del algoritmo de factorización cuántica anterior. Aunque todavía no es inmediatamente práctico, su trabajo acerca los algoritmos de factorización cuántica a la realidad», añade Regev.

En el futuro, los investigadores esperan hacer su algoritmo aún más eficiente y, algún día, usarlo para probar la factorización en un circuito cuántico real.

«La pregunta que queda en el aire después de este trabajo es: ¿realmente nos acerca a descifrar la criptografía RSA? Eso no está claro todavía; estas mejoras actualmente sólo se aplican cuando los números enteros son mucho mayores que 2.048 bits. ¿Podemos impulsar este algoritmo y hacerlo más factible que el de Shor incluso para números enteros de 2.048 bits?», dice Ragavan.

Esta historia se vuelve a publicar por cortesía de MIT News (web.mit.edu/newsoffice/), un sitio popular que cubre noticias sobre investigación, innovación y enseñanza del MIT.