Por outro lado, os computadores quânticos prometem quebrar rapidamente sistemas criptográficos complexos que um computador clássico talvez nunca seja capaz de desvendar. Essa promessa se baseia em um algoritmo quântico de fatoração proposto em 1994 por Peter Shor, que atualmente é professor no MIT.
No entanto, embora os pesquisadores tenham avançado muito nos últimos 30 anos, ainda não conseguiram 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 aprimorar o algoritmo de Shor para que ele possa ser executado 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 ser executado mais rapidamente, mas o circuito exigiria mais memória.
Baseando-se nesses resultados, pesquisadores do MIT propuseram uma abordagem que combina a velocidade do algoritmo de Regev com a eficiência de memória do algoritmo de Shor. Esse novo algoritmo é tão rápido quanto o de Regev, requer menos blocos quânticos conhecidos como qubits e tem uma maior tolerância ao ruído quântico, o que poderia torná-lo mais viável de implementar na prática.
A longo prazo, esse novo algoritmo poderia informar o desenvolvimento de novos métodos de criptografia capazes de resistir ao poder de quebra de códigos dos computadores quânticos.
“Se os computadores quânticos em grande escala forem construídos, a fatoração estará comprometida e teremos que encontrar algo mais para usar na criptografia. Mas quão real é essa ameaça? Podemos tornar a fatoração quântica prática? Nosso trabalho poderia potencialmente nos aproximar de uma implementação prática”, diz Vinod Vaikuntanathan, professor da Fundação Ford de Engenharia, 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, 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 Conferência Internacional de Criptologia de 2024.
Para transmitir mensagens de forma segura pela internet, provedores de serviços como clientes de e-mail e aplicativos de mensagens geralmente contam com o RSA, um esquema de criptografia inventado por pesquisadores do MIT Ron Rivest, Adi Shamir e Leonard Adleman na década de 1970 (daí o nome “RSA”). O sistema se baseia na ideia de que a fatoração de um número inteiro de 2.048 bits (um número com 617 dígitos) é muito difícil para um computador fazer em um período razoável de tempo.
Essa ideia foi revolucionada em 1994, quando Shor, então trabalhando na Bell Labs, introduziu um algoritmo que provou que um computador quântico poderia fatorar rapidamente o suficiente para quebrar a criptografia RSA.
“Isso 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 serão construídos algum dia”, diz Vaikuntanathan.
Estima-se que um computador quântico precisaria de cerca de 20 milhões de qubits para executar o algoritmo de Shor. Atualmente, 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 por 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 as portas quânticas introduzem ruído, então ter menos portas melhoraria o desempenho da máquina. Os 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.
“Isso foi uma grande notícia, pois 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 a ser fatorado. Isso significa que, se alguém fosse fatorar um número 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 muitos mais qubits para fornecer memória suficiente. Isso apresenta um novo problema.
“De certa forma, alguns tipos de qubits são como maçãs ou laranjas. Se você os mantiver por perto, eles se degradam ao longo do 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 apresentação, Regev fez uma pergunta: Alguém poderia melhorar seu circuito para que ele precisasse de menos qubits? Vaikuntanathan e Ragavan assumiram essa questão.
Para fatorar um número muito grande, um circuito quântico precisaria ser executado muitas vezes, realizando operações que envolvem o cálculo de potências, como 2 elevado à potência de 100.
Mas calcular essas potências grandes é caro e difícil de realizar em um computador quântico, já que os computadores quânticos só podem realizar 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 calcular 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. Seu método precisa apenas de 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 vamos e voltamos, multiplicando entre duas unidades 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 seja 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 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 implantar.
“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, um dia, usá-lo para testar a fatoração em um circuito quântico real.
“A pergunta que fica após este trabalho é: Isso realmente nos aproxima de quebrar a criptografia RSA? Isso ainda não está claro; essas melhorias só entram em vigor quando os inteiros são muito maiores do que 2.048 bits. Podemos impulsionar este 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, a Agência de Projetos de Pesquisa Avançada de Defesa dos EUA, a Fundação Nacional de Ciência, o Laboratório de IA MIT-IBM Watson, uma Bolsa de Inovação em Pesquisa da Família Thornton e um Prêmio de Investigador da Simons.
Redação Confraria Tech
Referências:
Toward a code-breaking quantum computer
