O e-mail mais recente que você enviou provavelmente foi criptografado usando um método testado e comprovado que se baseia na ideia de que mesmo o computador mais rápido seria incapaz de dividir com eficiência um número gigantesco em fatores.

Os computadores quânticos, por outro lado, prometem quebrar rapidamente sistemas criptográficos complexos que um computador clássico nunca seria capaz de desvendar. Essa promessa é baseada em um algoritmo de fatoração quântica proposto em 1994 por Peter Shor , que agora é professor no MIT.

Mas, embora os pesquisadores tenham feito grandes avanços nos últimos 30 anos, os cientistas ainda precisam construir um computador quântico poderoso o suficiente para executar o algoritmo de Shor.

Enquanto alguns pesquisadores trabalham para construir computadores quânticos maiores, outros têm tentado melhorar o algoritmo de Shor para que ele possa rodar em um circuito quântico menor. Cerca de um ano atrás, o cientista da computação da Universidade de Nova York, Oded Regev, propôs uma  grande melhoria teórica . Seu algoritmo poderia rodar mais rápido, mas o circuito exigiria mais memória.

Com base nesses resultados, pesquisadores do MIT propuseram uma abordagem do melhor dos dois mundos que combina a velocidade do algoritmo de Regev com a eficiência de memória de Shor. Esse novo algoritmo é tão rápido quanto o de Regev, requer menos blocos de construção quânticos conhecidos como qubits e tem uma tolerância maior ao ruído quântico, o que pode torná-lo mais viável para implementação na prática.

A longo prazo, esse novo algoritmo pode informar o desenvolvimento de novos métodos de criptografia que podem suportar o poder de quebra de código dos computadores quânticos.

“Se computadores quânticos de larga escala forem construídos, então a fatoração estará acabada e teremos que encontrar outra coisa para usar na criptografia. Mas quão real é essa ameaça? Podemos tornar a fatoração quântica prática? Nosso trabalho pode potencialmente nos levar um passo mais perto de uma implementação prática”, diz Vinod Vaikuntanathan, Professor de Engenharia da Fundação Ford, membro do Laboratório de Ciência da Computação e Inteligência Artificial (CSAIL) e autor sênior de um artigo que descreve o algoritmo .

O autor principal do artigo é Seyoon Ragavan, um estudante de pós-graduação no Departamento de Engenharia Elétrica e Ciência da Computação do MIT. A pesquisa será apresentada na International Cryptology Conference de 2024.

Para transmitir mensagens com segurança pela internet, provedores de serviços como clientes de e-mail e aplicativos de mensagens normalmente contam com RSA, um  esquema de criptografia inventado pelos pesquisadores do MIT Ron Rivest, Adi Shamir e Leonard Adleman na década de 1970 (daí o nome “RSA”). O sistema é baseado na ideia de que fatorar um inteiro de 2.048 bits (um número com 617 dígitos) é muito difícil para um computador fazer em um período de tempo razoável.

Essa ideia foi virada de cabeça para baixo em 1994, quando Shor, então trabalhando no Bell Labs, introduziu um algoritmo que provou que um computador quântico poderia fatorar rápido o suficiente para quebrar a criptografia RSA.

“Aquele foi um ponto de virada. Mas em 1994, ninguém sabia como construir um computador quântico grande o suficiente. E ainda estamos bem longe disso. Algumas pessoas se perguntam se eles algum dia serão construídos”, diz Vaikuntanathan.

Estima-se que um computador quântico precisaria de cerca de 20 milhões de qubits para executar o algoritmo de Shor. No momento, os maiores computadores quânticos têm cerca de 1.100 qubits.

Um computador quântico realiza cálculos usando circuitos quânticos, assim como um computador clássico usa circuitos clássicos. Cada circuito quântico é composto de uma série de operações conhecidas como portas quânticas. Essas portas quânticas utilizam qubits, que são os menores blocos de construção de um computador quântico, para realizar cálculos.

Mas portas quânticas introduzem ruído, então ter menos portas melhoraria o desempenho de uma máquina. Pesquisadores têm se esforçado para aprimorar o algoritmo de Shor para que ele possa ser executado em um circuito menor com menos portas quânticas.

Foi exatamente isso que Regev fez com o circuito que ele propôs há um ano.

“Foi uma grande notícia porque foi a primeira melhoria real no circuito de Shor desde 1994”, diz Vaikuntanathan.

O circuito quântico proposto por Shor tem um tamanho proporcional ao quadrado do número que está sendo fatorado. Isso significa que se alguém fosse fatorar um inteiro de 2.048 bits, o circuito precisaria de milhões de portas.

O circuito de Regev requer significativamente menos portas quânticas, mas precisa de muito mais qubits para fornecer memória suficiente. Isso apresenta um novo problema.

“Em certo sentido, alguns tipos de qubits são como maçãs ou laranjas. Se você os mantiver por perto, eles decaem com o tempo. Você quer minimizar o número de qubits que precisa manter por perto”, explica Vaikuntanathan.

Ele ouviu Regev falar sobre seus resultados em um workshop em agosto passado. No final de sua palestra, Regev fez uma pergunta: Alguém poderia melhorar seu circuito para que ele precisasse de menos qubits Vaikuntanathan e Ragavan abordaram essa questão.

Para fatorar um número muito grande, um circuito quântico precisaria ser executado muitas vezes, realizando operações que envolvem poderes de computação, como 2 elevado a 100.

Mas computar poderes tão grandes é custoso e difícil de executar em um computador quântico, já que computadores quânticos só podem executar operações reversíveis. Elevar um número ao quadrado não é uma operação reversível, então cada vez que um número é elevado ao quadrado, mais memória quântica deve ser adicionada para computar o próximo quadrado.

Os pesquisadores do MIT encontraram uma maneira inteligente de calcular expoentes usando uma série de  números de Fibonacci que requer multiplicação simples, que é reversível, em vez de elevar ao quadrado. O método deles precisa de apenas duas unidades de memória quântica para calcular qualquer expoente.

“É como um jogo de pingue-pongue, onde começamos com um número e depois saltamos para frente e para trás, multiplicando entre dois registros de memória quântica”, acrescenta Vaikuntanathan.

Eles também enfrentaram o desafio da correção de erros. Os circuitos propostos por Shor e Regev exigem que cada operação quântica esteja correta para que seu algoritmo funcione, diz Vaikuntanathan. Mas portas quânticas sem erros seriam inviáveis em uma máquina real.

Eles superaram esse problema usando uma técnica para filtrar resultados corrompidos e processar apenas os corretos.

O resultado final é um circuito que é significativamente mais eficiente em termos de memória. Além disso, sua técnica de correção de erros tornaria o algoritmo mais prático de implementar.

“Os autores resolvem os dois gargalos mais importantes no algoritmo de fatoração quântica anterior. Embora ainda não seja imediatamente prático, seu trabalho aproxima os algoritmos de fatoração quântica da realidade”, acrescenta Regev.

No futuro, os pesquisadores esperam tornar seu algoritmo ainda mais eficiente e, algum dia, usá-lo para testar a fatoração em um circuito quântico real.

“A questão do elefante na sala após esse trabalho é: ele realmente nos deixa mais perto de quebrar a criptografia RSA? Isso ainda não está claro; essas melhorias atualmente só entram em ação quando os inteiros são muito maiores que 2.048 bits. Podemos empurrar esse algoritmo e torná-lo mais viável do que o de Shor, mesmo para inteiros de 2.048 bits?” diz Ragavan.

Este trabalho é financiado por uma bolsa presidencial da Akamai, pela Agência de Projetos de Pesquisa Avançada de Defesa dos EUA, pela National Science Foundation, pelo MIT-IBM Watson AI Lab, pela Thornton Family Faculty Research Innovation Fellowship e pelo Simons Investigator Award.