Por que os computadores quânticos ainda não conseguiram fatorar 21

• Após a fatoração de 15 por um computador quântico em 2001, parece que não houve progresso, e aqui se explica por quê
• Um circuito para fatorar 21 exige 100 vezes mais portas de emaranhamento do que para fatorar 15
• Essa diferença vem da complexidade da multiplicação modular condicional e de otimizações especiais que só se aplicam ao 15
• A correção de erros quânticos e os limites do hardware também elevam ainda mais a barreira para fatorar 21
• Até hoje, a maioria dos relatos de fatoração de 21 usou truques, sem realizar multiplicação de verdade no sentido estrito

---

Por que os computadores quânticos ainda não conseguiram fatorar 21

Por que a fatoração de 21 não apareceu depois da fatoração de 15

• Em 2001, houve um experimento que fatorou 15 com um computador quântico
• Mesmo em 2025, ainda não há um caso bem-sucedido de fatoração de 21
• Com base nisso, espalhou-se a percepção de que não houve absolutamente nenhum avanço em computação quântica
• Mas, na prática, ao comparar os circuitos de fatoração de 15 e de 21, existe um motivo muito mais surpreendente

Diferenças estruturais entre o circuito de fatoração de 15 e o de 21

• O circuito de fatoração de 15 é implementado com apenas 21 portas quânticas (21 portas de emaranhamento)
  • Consiste em 6 portas de emaranhamento de dois qubits (portas CNOT e CPHASE) e
  • 2 portas Toffoli (cada uma decomposta em 6 portas de emaranhamento), totalizando 21 portas de emaranhamento
• O circuito de fatoração de 21 exige 191 CNOT, 369 Toffoli e, no total, 2405 portas de emaranhamento
  • Isso impõe uma carga de 115 vezes mais portas de emaranhamento do que ao fatorar 15
  • O tamanho do circuito não aumenta simplesmente 25% ou 2 vezes, mas fica mais de 100 vezes mais caro
• Mesmo considerando o nível de otimização do circuito, uma diferença de até 500 vezes também parece realisticamente possível

Por que surge uma diferença tão grande

• Nos circuitos quânticos de fatoração (algoritmo de Shor), o custo dominante é a multiplicação modular condicional
  • Para um número N de n bits, é preciso realizar várias multiplicações modulares condicionais em um acumulador
  • No caso de 15, entre 8 multiplicações condicionais, 6 podem ser tratadas como multiplicação por 1 (sem fazer nada)
    • A primeira multiplicação pode ser implementada de forma quase gratuita, porque a entrada é 1
    • A segunda (a única restante) também pode ser tratada de forma barata com duas CSWAPs
    • Como resultado, de fato só é preciso pagar o custo de 2
    • Essa estrutura é uma propriedade especial que vale apenas para 15, com várias multiplicações próximas de 1, reduzindo drasticamente o custo
• Mas, no caso de 21, todas as multiplicações são diferentes de 1 e têm valores variados, então todas têm custo
  • As 8 operações de multiplicação geram custo, o que faz o aumento não ser apenas de 4 a 5 vezes, mas de 20 a 100 vezes
  • Multiplicações por 4 ou 16, por exemplo, não têm uma estrutura que permita implementação via CSWAP (troca condicional)
  • A complexidade da multiplicação varia de caso a caso, e a otimização não é simples

Limites práticos de hardware e correção de erros

• No passado (2001), a fatoração de 15 foi implementada em um computador quântico de NMR, com muitas limitações de escalabilidade
• Além disso, cresce também a necessidade de correção de erros quânticos
  • Se o número de portas aumenta 100 vezes, a taxa de erro precisa ser 100 vezes menor
  • Na prática, pode ser necessário aumentar também o número de qubits em 100 vezes, elevando o custo total em 10.000 vezes

Controvérsias nas tentativas de fatoração e resultados incorretos

• Alguns artigos recentes afirmam ter conseguido fatorar 21 com computadores quânticos, mas
  • na prática, muitas vezes omitem a execução da multiplicação no algoritmo ou simplificam o circuito já sabendo o resultado de antemão
  • sem realizar a operação real de multiplicação, isso não pode ser considerado fatoração
  • trata-se de resultados que ignoram a diferença essencial entre simples "busca de período" e fatoração
• Alguns artigos usam truques de forma explícita, e até surgiram artigos satíricos em resposta a esses trabalhos
  • há vários artigos satíricos, como experimentos que replicam recordes de campeões de fatoração
  • benchmarks como variational factoring continuam aparecendo, apesar de não terem base para escalar

Qual é o indicador correto de avanço real em computação quântica

• No momento, a fatoração não é o principal benchmark de avanço em computação quântica
  • ao passar de 15, o custo explode, o que dificulta a validação prática
• Em vez disso, a adoção de correção de erros quânticos (por exemplo, melhorias em surface code) ou
  • mudanças na arquitetura de hardware que resolvam problemas de escalabilidade (por exemplo, substituição contínua em átomos neutros)
  • são pontos de observação muito mais importantes para mostrar progresso real

[GN⁺]

Comentários no Hacker News

• Isso se deve ao fato de que, até agora, nunca se havia fatorado na prática um número ainda menor. Se o programa só funciona porque o processo de compilação já precisa saber a resposta, então isso não é fatoração de verdade, mas apenas "imprimir 3"

• Fico curioso sobre quantos quantum gates seriam necessários para fatorar um número realmente relevante do ponto de vista criptográfico. Também queria saber se existe um caminho prático para que um computador quântico útil surja ainda neste século

  • Como exemplo, pode-se citar a estimativa da Tabela 5 deste artigo, segundo a qual seriam necessários cerca de 7 bilhões de portas Toffoli para fatorar um RSA de 2048 bits (link do artigo). O método para atingir dezenas de bilhões de operações é justamente a correção de erros quânticos, e o artigo afirma que um surface code de distance 25 seria suficiente. Nesse caso, seriam escalados 1.400 qubits lógicos para cerca de 1 milhão de qubits físicos ruidosos. Vale também ver a palestra de Samuel Jacques na PQCrypto (YouTube). Sou o autor deste blog e dos artigos relacionados
  • Há dois motivos pelos quais essa pergunta é difícil. Primeiro, não dá para traçar uma linha clara para o que é "criptograficamente relevante". Segundo, a arquitetura de um QC capaz de realmente executar essa operação ainda não é conhecida com clareza. É parecido com tentar estimar, em 1985, quantas portas lógicas tradicionais seriam necessárias para construir redes neurais. Ainda assim, parece certo que seriam necessárias mais de alguns milhões de portas. Em terceiro lugar, existe um trade-off, na correção de erros quânticos, entre taxas de erro mais baixas nos qubits físicos e a quantidade de gates necessária para construir qubits virtuais confiáveis com correção de erros. Hoje não sabemos até onde a taxa de erro dos qubits físicos poderá cair. Se os computadores quânticos tiverem um progresso parecido com o da computação nos últimos 75 anos, então por volta de 2100 a criptografia atual estaria totalmente anulada. É difícil prever até surgir uma inovação única, como o transistor. O avanço tecnológico sempre parece impossível até alguém encontrar a primeira forma de fazê-lo. (descrição do UNIVAC I)
  • Também cito um tweet recente sobre o tema (link do tweet). Do ponto de vista de uma pessoa comum, esse caminho parece escondido atrás de várias grandes inovações em ciência dos materiais
  • No caso do RSA 4096, seriam necessários aproximadamente 10^7 qubits com taxa de erro de 10^-4. Já é possível fazer cálculos úteis de química quântica com algo em torno de 100 qubits, e, à medida que algoritmos pós-quânticos se espalham, o incentivo para desenvolver computadores quânticos voltados à quebra de criptografia diminui. Acho que a computação quântica avançará mais rápido em direções não relacionadas à criptografia
  • Os números mais recentes apontam para cerca de 1 milhão de qubits com taxa de erro de 1e-4 (link do artigo). A quantidade de gates é medida de forma diferente no nível do código, dependendo da operação real, e com um "clock" de 1MHz (tempo de ciclo do código), o tempo total de computação seria de cerca de uma semana. Atingir esse tempo de computação é uma métrica mais difícil do que atingir a quantidade de qubits. Graças ao efeito quase mágico da correção de erros quânticos (quanto menor a taxa de erro, maior a redução no número de qubits), uma melhoria de um nível na qualidade dos qubits reduz drasticamente a quantidade necessária. Por outro lado, se for preciso dividir a computação entre vários sistemas, a situação piora muito

• O artigo 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' é interessante (ler artigo)

• Tenho interesse no tamanho do circuito e na viabilidade prática de fatorar números criptograficamente relevantes como RSA1024

  • As estimativas de custo para RSA1024 não são obtidas por simples extrapolação de números pequenos (como 4 bits), mas por projetos de circuito adequados à escala real. Ou seja, o problema de descontinuidade mencionado neste texto já está implicitamente refletido nelas. Portanto, esta postagem não afeta as estimativas de custo existentes
  • (Observação: a otimização do circuito de fatoração de 21 provavelmente é difícil de aplicar à fatoração de números grandes. Um custo 500 vezes maior em relação ao circuito de fatoração de 15 pode ser mais realista. Claro, mesmo um overhead de 100 vezes já basta para ilustrar o argumento. Agradeço especialmente a Noah Shutty por ter feito uma busca computacional cara por essa otimização de circuito)
  • Fugindo um pouco do tema, fico curioso se os criptógrafos estão confiantes de que, mesmo em datacenters gigantescos recentes, fatorar RSA1024 continua sendo praticamente impossível. No estado atual, nem o algoritmo mais rápido consegue fatorar dentro de um tempo realista. Mas queria saber se há consenso de que não surgirá uma melhoria revolucionária nesse algoritmo tão cedo

• Fico curioso se algum dia computadores quânticos poderiam mirar um post-quantum RSA (artigo relacionado). Há quem diga que operações RSA comuns (geração de chave, criptografia, descriptografia) são assimetricamente favoráveis contra o algoritmo de Shor, então bastaria usar chaves grandes o suficiente. Isso produz um efeito parecido com os quebra-cabeças de Merkle, com a condição adicional de que o atacante necessariamente teria de usar um computador quântico. Já cheguei a criar uma chave pública RSA de gigabits (arquivo de chave). O formato é: 4 bytes little-endian com a quantidade de bytes da chave, seguidos da chave e do inverso da chave (módulo 256^bytes). O expoente público é 3

  • Post-Quantum RSA é uma piada do djb feita para responder à pergunta "não basta usar chaves grandes para ficar seguro?". Ele foi projetado para levar 100 horas por operação de criptografia com uma chave de 1TB. Nem computadores quânticos conseguiriam quebrá-lo

• Achei bem engraçado ver o erro de digitação "error corection"

• Tive dificuldade para entender a parte de "custo de circuito 500 vezes maior em comparação com fatorar 15". O autor já apresentou um caso de 115 vezes, então fiquei me perguntando como uma otimização adicional poderia levar a um resultado pior

  • Isso significa que a enorme quantidade de trabalho de otimização investida na construção de circuitos para fatorar números pequenos é impraticável para números grandes. Ou seja, intuitivamente, ao aumentar o tamanho do número a ser fatorado, o normal seria precisar de algo em torno de 500 vezes mais gates (e não algo tão pequeno quanto 115 vezes)
  • Na prática, em grande escala o efeito das otimizações diminui, e o ganho não será tão grande quanto no circuito para N=21
  • Uma implementação mínima é instável e difícil de tornar confiável. Para desenvolver um circuito prático, é preciso muita pesquisa para garantir qubits estáveis, e conceitos como "tempo de decoerência" também são mencionados. Portanto, a quantidade de qubits inevitavelmente explode
  • O fator 115x é resultado de muitas otimizações (nada realistas)

• A ideia central desta postagem sugere que a necessidade de circuitos Big-O para a fatoração de Schorr é superpolinomial?

  • Pelo texto, o custo em gates vem principalmente de O(n) operações de multiplicação modular, e cada uma pode ser implementada com O(n^2) gates. No total, mesmo no pior caso, isso parece ter complexidade aproximadamente cúbica

• O motivo para adotar criptografia PQ (pós-quântica) não é necessariamente a certeza de que QC chegará em breve. O momento em que QC surgirá é incerto, dependendo do ritmo do desenvolvimento tecnológico. O objetivo da criptografia é encontrar métodos que sejam, em teoria, praticamente impossíveis de quebrar; se um ataque é teoricamente possível, então também é fisicamente possível, e por isso é preciso se preparar. ECC e RSA já têm um caminho teórico de ataque conhecido, então considera-se que podem ser atacados mesmo sem existir ainda o equipamento real. Por isso, faz todo sentido se preparar antes que o QC exista. Já para SHA2, AES, ChaCha etc., não há um caminho de ataque prático visível, então não existe plano imediato de substituição. Criptografia não é a única, nem necessariamente a principal, direção de aplicação de QC. Existe a expectativa de que surjam inovações ainda desconhecidas em áreas como sistemas físicos, folding de proteínas e aprendizado de máquina

  • Fico curioso se ainda há espaço para mais avanços em áreas como folding de proteínas (mesmo depois do AlphaFold). (artigo de referência)

  • No caso de criptografia de chave simétrica (AES, ChaCha, SHA-2), o ataque quântico na prática equivale a enfraquecer o comprimento da chave pela metade (como nos casos de 3DES e 2DES). Na prática, não dá para afirmar que é exatamente metade, porque o desempenho de computadores quânticos reais não será equivalente ou idêntico, mas basta migrar para AES-256 e o problema fica resolvido. O ponto em que devemos nos concentrar é o Key Exchange. Isso porque o Key Exchange é usado para permitir que os dois lados cheguem a uma chave secreta sem revelá-la diretamente. Se existir um Quantum Computer, ele poderá ler também conversas gravadas no passado. Quebrar um algoritmo de assinatura não permite voltar no tempo para assinar algo retroativamente, mas quando o Key Exchange é quebrado, todas as conversas passadas também ficam expostas. Por isso, é urgente ter um substituto seguro para Key Exchange