⚛️ quantum physics

ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm

Este artigo apresenta o "Open Autoresearch", um paradigma de colaboração humano-IA que otimizou com sucesso circuitos de adição de pontos reversíveis secp256k1 para o algoritmo de Shor, alcançando uma redução de 86,1% no custo de espaço-tempo e superando os limiares de eficiência publicados pelo Google para quebrar o ECDSA.

Autores originais: Jieyi Long, Theodore Pender, Zhao Huang, Manuel B. Santos, Samrendra Kumar Singh, Bartosz Naskręcki, Bit Wonka, Joe Doyle, Pierre-Luc Dallaire-Demers, Francesco Giannicola, Ruben M. L. Paschoarelli, O

Publicado 2026-09-10

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Jieyi Long, Theodore Pender, Zhao Huang, Manuel B. Santos, Samrendra Kumar Singh, Bartosz Naskręcki, Bit Wonka, Joe Doyle, Pierre-Luc Dallaire-Demers, Francesco Giannicola, Ruben M. L. Paschoarelli, Oli Freuler, Jackie Chia-Hsun Lee, Vasily Gnuchev, Gopi Kannappan, John Boyer, Xavier Butler, Akash Balasubramani, Jordan Newman, Bereket Dereje, Alexander Hertlein, Robert Kodra, Lucas Levy, Shaan Patel, JT Rose, Matt Zweil, Okechukwu Wisdom, Tarek El-Eter, Edison Lee, Michael Dong, Alan Li, Anto Joseph, Gajesh Naik, Gautham Anant, Soubhik Deb, Justin Drake

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

No mundo da segurança moderna, muitas de nossas fechaduras digitais dependem de um enigma matemático envolvendo pontos em uma linha curva. Este enigma é tão difícil para os computadores de hoje que protege tudo, desde contas bancárias até a moeda digital Bitcoin. No entanto, cientistas sabem há muito tempo que um tipo futuro de computador, um que utiliza as estranhas leis da física quântica, poderia resolver este enigma muito mais rápido do que qualquer máquina que temos agora. Para entender o quão próximos estamos de construir tal máquina, pesquisadores tentam estimar os recursos que ela precisaria. Eles calculam quantos pequenos bits quânticos, chamados qubits, e quantos passos lógicos complexos seriam necessários para quebrar essas fechaduras. Essas estimativas são cruciais porque nos dizem quando devemos mudar para novos sistemas de segurança inquebráveis antes que os antigos falhem.

Um novo projeto chamado ECDSA.Fail adotou uma abordagem inovadora para este problema ao transformar a busca por melhores designs quânticos em uma competição aberta. Em vez de uma única equipe trabalhando em segredo, centenas de pessoas e agentes de inteligência artificial colaboraram para melhorar uma parte específica do código quântico necessário para decifrar o enigma da curva elíptica. O objetivo era tornar o circuito — o projeto das ações do computador quântico — o mais eficiente possível. Os pesquisadores mediram a eficiência observando duas coisas: o número de qubits que o circuito precisava para rodar simultaneamente e o número total de operações complexas que ele realizava. Eles multiplicaram esses dois números para obter uma pontuação única, onde um número menor significava um design melhor e mais eficiente.

Os resultados desta colaboração aberta foram impressionantes. A equipe começou com um design de base que exigia mais de dois mil qubits e quase quatro milhões de operações. Através de um processo de melhoria contínua, onde os participantes compartilhavam suas melhores ideias e agentes de IA ajudavam a testar milhares de variações, o grupo conseguiu reduzir a pontuação de eficiência em mais de oitenta e seis por cento. Quando os dados foram coletados, o melhor design exigia apenas cerca de mil cento e cinquenta qubits e aproximadamente um ponto três milhões de operações. Este novo recorde é significativamente melhor do que estimativas anteriores de grandes grupos de pesquisa, incluindo um do Google, que mantinha seu design de circuito específico oculto. A equipe do ECDSA.Fail alcançou isso tornando o circuito menor e mais rápido, provando que uma comunidade de humanos e máquinas trabalhando juntos pode resolver problemas de engenharia complexos mais rapidamente do que especialistas isolados.

O projeto fez mais do que apenas encontrar um número melhor; ele revelou como diferentes estratégias funcionam. Um grupo de participantes focou em tornar o circuito o menor possível, comprimindo-o para usar apenas oitocentos e vinte e cinco qubits. Embora esta versão utilizasse muito menos bits quânticos, ela exigiu muito mais operações para rodar, mostrando um claro compromisso entre espaço e tempo. Outro grupo focou na pontuação geral, equilibrando os dois fatores para encontrar o caminho mais eficiente. Os pesquisadores também construíram uma versão do melhor design que poderia funcionar com um método mais avançado de execução do algoritmo quântico, mostrando que as melhorias não eram apenas teóricas, mas poderiam ser adaptadas para o uso no mundo real.

O que torna esta conquista particularmente notável é o método utilizado para alcançá-la. Os pesquisadores criaram um sistema onde qualquer pessoa podia enviar um design, e um programa de computador verificava imediatamente se ele funcionava corretamente e calculava sua pontuação. Isso permitiu que agentes de inteligência artificial atuassem como pesquisadores incansáveis, propondo mudanças, testando-as e aprendendo com as falhas sem a necessidade de supervisão humana constante. Os humanos intervinham para guiar a direção geral, escolhendo quais ideias perseguir e interpretando os resultados. O projeto mostrou que, quando um problema pode ser verificado de forma rápida e precisa por uma máquina, um grupo diversificado de humanos e IA pode superar equipes de pesquisa tradicionais.

O artigo também esclarece o que estes resultados significam para o futuro. Embora os novos designs sejam muito mais eficientes, eles ainda não são um blueprint completo para uma máquina que possa quebrar a criptografia atual. Os circuitos testados são apenas uma peça de um quebra-cabeça muito maior, e o sistema completo ainda exigiria quantidades massivas de correção de erros e hardware físico que ainda não existe. Além disso, os designs foram testados em um conjunto específico de entradas para garantir que funcionassem, mas não há garantia de que funcionarão perfeitamente em todos os cenários possíveis. Os pesquisadores são cuidadosos ao afirmar que estas são melhorias para o entendimento teórico do problema, não um aviso de que as fechaduras estão prestes a quebrar amanhã.

Em última análise, o projeto ECDSA.Fail serve como uma demonstração poderosa de como a ciência pode evoluir quando é aberta e colaborativa. Ao tornar o problema público e os resultados verificáveis, a equipe criou um registro vivo de progresso que qualquer pessoa poderia estudar. Eles mostraram que o caminho para resolver problemas difíceis não é mais apenas sobre o gênio individual, mas sobre construir sistemas onde o insight humano e a velocidade da máquina possam se reforçar mutuamente. À medida que o mundo se move em direção a um futuro com computadores quânticos, este tipo de pesquisa aberta e transparente será essencial para compreender os riscos e preparar as defesas necessárias para proteger o nosso mundo digital.

Resumo Técnico: ECDSA.Fail: Autopesquisa Aberta para Otimização da Adição de Pontos em Curvas Elípticas no Algoritmo de Shor

1. Declaração do Problema

O artigo aborda a otimização de circuitos quânticos reversíveis para a adição de pontos em curvas elípticas, um gargalo crítico no algoritmo de Shor para resolver o Problema do Logaritmo Discreto de Curva Elíptica (ECDLP). Especificamente, o desafio foca na curva secp256k1, que sustenta o Bitcoin e o Ethereum.

O objetivo principal é minimizar uma métrica de custo inspirada em espaço-tempo, $S = Q \times T$ , onde:

$Q$ : A largura máxima de qubits lógicos (espaço).
$T$ : A contagem média de portas Toffoli executadas (trabalho não-Clifford).

A tarefa de referência é implementar um circuito de adição de ponto mista reversível ( $R \leftarrow R + A$ ), onde o acumulador $R$ é um dado quântico e o adendo $A$ é especificado classicamente. O circuito deve ser "limpo" (os qubits ancila retornam a $|0\rangle$ ) e "limpo de fase" (sem fases residuais) para funcionar corretamente dentro de um algoritmo coerente maior, como o de Shor.

2. Metodologia: Autopesquisa Aberta

O artigo introduz e instacia um novo paradigma de pesquisa chamado Autopesquisa Aberta (Open Autoresearch). Diferente da pesquisa tradicional impulsionada por especialistas individuais ou pequenas equipes, esta abordagem envolve uma comunidade heterogênea de humanos e agentes de IA competindo e colaborando por meio de um ranking público (leaderboard).

Mecanismo: Os participantes propõem modificações de circuito para um repositório compartilhado. Estas são avaliadas por um avaliador verificável por máquina que verifica a correção clássica, a limpeza da ancila e a limpeza de fase em um conjunto de testes determinístico dependente da submissão (derivado via hashing Fiat-Shamir).
Processo: Melhorias verificadas tornam-se "bases" públicas para otimizações subsequentes. O processo é aberto, observável e cumulativo, permitindo que equipes independentes de humanos e agentes construam sobre o trabalho uns dos outros sem coordenação prévia.
Ferramentas: Os participantes utilizaram agentes de Grandes Modelos de Linguagem (LLMs) (ex: Claude Code, Codex) para geração de hipóteses, implementação de código e depuração, guiados pelo direcionamento humano para estratégia de alto nível e restrições de domínio.

3. Principais Contribuições

A. O Paradigma da Autopesquisa Aberta

O artigo formaliza um framework onde:

Objetivos Verificáveis: Os problemas são definidos por métricas eficientemente computáveis e verificáveis por máquina.
Busca Cumulativa: Agentes independentes contribuem para um registro público compartilhado de sucessos e falhas.
Sinergia Humano-Agente: Humanos fornecem direção arquitetônica e interpretam resultados, enquanto agentes lidam com implementação, experimentação repetitiva e otimização local.
O artigo argumenta que este modelo é eficaz para problemas de otimização de fronteira onde a avaliação é barata e confiável.

B. Otimizações de Circuito de Nível de Fronteira

O desafio produziu reduções significativas nas estimativas de recursos para a adição de pontos secp256k1. As principais inovações arquitetônicas incluem:

Algoritmo Euclidiano Jump-2: Um retiming do algoritmo de diálogo-GCD (registro-e-reprodução) que agrupa etapas euclidianas consecutivas em macro-etapas, reduzindo o número de comparações e trocas (swaps).
Codec de Transcrição Base-5: Uma técnica de compressão que codifica três símbolos Jump-2 (que possuem apenas 5 estados válidos de 8) em um registro de 7 qubits em vez de 9, reduzindo significamente o armazenamento de transcrição necessário para a reprodução reversível.
Diálogo-GCD Ping-Pong Sem Comparação: Uma arquitetura pós-cutoff que elimina comparações de magnitude de largura total usando verificações de paridade de baixo bit e direções de atualização alternadas, trocando largura de qubits por redução na contagem de Toffoli.
Algoritmo Euclidiano Estendido (EEA) com Compartilhamento de Registrador: Uma estratégia agressiva de compartilhamento de registradores (derivada de Luo et al. e TrailMix) que empacota restos decrescentes e coeficientes de Bézout crescentes em bancos físicos compartilhados, permitindo uma redução extrema de largura.
Aritmética Especializada: Implementação de o quadrado de Karatsuba com redução de módulo pseudo-Mersenne e propagação de constantes para eliminar operações redundantes baseadas em entradas clássicas.

C. Registro Público Abrangente

O projeto lançou um histórico completo e auditável de mais de 400 submissões promovidas, incluindo:

A trajetória completa de melhorias de recursos.
Uma classificação de 400 commits aceitos por mecanismo de otimização (ex: eliminação de código morto, alocação de registrador, substituição algorítmica).
Artefatos reproduzíveis permitindo a verificação independente de todos os pontos operacionais relatados.

4. Resultados

Métricas de Desempenho

No corte de dados (26 de julho de 2026), o desafio alcançou o seguinte:

Baseline: $Q = 2.715$ , $T = 3.960.753$ , $S \approx 10,75$ bilhões.
Melhor Circuito $Q \times T$ (8e9c9a2): Reduzido para $Q = 1.151$ e $T = 1.299.453$ , resultando em $S \approx 1,496$ bilhão.
- Isso representa uma redução de 86,1% no score.
- O score é mais de 50% menor do que o ponto operacional anteriormente relatado pelo Google/Babbush et al. (aprox. 2,993B).
Melhor Circuito de Baixo $Q$ (b6f2b0a): Alcançou $Q = 825$ (posteriormente melhorado para 813 em uma submissão pós-cutoff) com $T \approx 489$ milhões.
Melhoria Pós-Cutoff: Uma variante "ping-pong" (3616dbf) reduziu ainda mais o score para $S \approx 1,259$ bilhão ( $Q=1.321, T=952.707$ ).

Comparação com Trabalhos Anteriores

O melhor circuito $Q \times T$ situa-se abaixo dos pontos operacionais relatados pelo Google/Babbush e Schrottenloher em ambos os eixos $Q$ e $T$ . O artigo observa que, embora o score numérico seja superior, a dominância formal é impedida por diferenças de interfaces (o benchmark usa um adendo clássico, enquanto o Shor de janela requer um adendo coerente) e convenções de contabilidade.

Compatibilidade de Janela (Windowed Compatibility)

Os autores construíram uma variante compatível com adição de janela do melhor circuito pontuado. Esta variante aceita o adendo coerentemente via QROM, adicionando 11 qubits e ~29,6% de overhead de Toffoli. Mantém uma probabilidade de sucesso empírica de $\hat{p} \approx 0,998$ , resultando em um proxy score ajustado por tentativa de $\approx 1,961$ bilhão, ainda abaixo dos pontos Google/Schrottenloher.

5. Significância e Alegações

O artigo reivindica significância em duas áreas distintas:

Estimativa de Recursos Criptográficos: Os resultados fornecem os menores scores numéricos de $Q \times T$ relatados para a adição de pontos secp256k1 até o corte de dados. Esses números refinam a compreensão dos recursos lógicos necessários para um computador quântico relevante para a criptografia (CRQC) quebrar a criptografia de curva elíptica, embora o artigo declare explicitamente que estes não são estimativas de recursos tolerantes a falhas completas (omitindo correção de erro física, roteamento e integração total de Shor).
Validação Metodológica: O artigo apresenta o ECDSA.Fail como a primeira demonstração em larga escala de Autopesquisa Aberta. Ele fornece evidências de que:
- Uma comunidade de humanos e agentes de IA pode coletivamente resolver problemas de otimização difíceis mais rápido do que equipes isoladas.
- A combinação de compartilhamento aberto, verificação verificável por máquina e experimentação em escala de agente cria um processo de pesquisa cumulativo.
- O julgamento humano permanece essencial para direcionar, interpretar resultados e preencher lacunas conceituais, enquanto os agentes se destacam na implementação e no refinamento iterativo.

Os autores mantêm uma postura modesta, enfatizando que os resultados são pontos operacionais em um benchmark específico com suporte de validação finito. Eles não alegam ter quebrado o secp256k1 ou estabelecido um cronograma definitivo para o "Q-day", mas sim terem fornecido uma base transparente, reproduzível e significativamente melhorada para futuras estimativas de recursos e planejamento de migração pós-quântica.