yuvadm/quantumslopSolução quântica para o Problema do Logaritmo Discreto em Curvas Elípticas usando o algoritmo de Shor, implementando múltiplas estratégias de oráculo para recuperar chaves privadas ECC em hardware quântico real.
Solver quântico para o Problema do Logaritmo Discreto de Curva Elíptica (ECDLP), construído para o Desafio Q-Day Prize pela Project Eleven. O objetivo: recuperar chaves privadas ECC em hardware quântico real usando o algoritmo de Shor.
Todas as curvas do desafio usam y^2 = x^3 + 7 sobre F_p (a = 0, b = 7), correspondendo à família secp256k1. O solver implementa a variante de dois registradores do algoritmo de Shor para ECDLP:
A chave privada d é recuperada coletando múltiplas amostras (j, k) que satisfazem a mesma relação linear módulo a ordem do grupo n. O solver suporta seis estratégias de oráculo para as adições de pontos controladas, selecionadas automaticamente com base no tamanho da curva ou manualmente via --oracle.
Usada para curvas com ordem de grupo até ~6 bits. Implementada em projecteleven.py.
Cada adição de ponto controlada "add S" é representada como uma matriz de permutação 2^(n+1) x 2^(n+1) aplicada via qc.unitary(). A matriz codifica a ação completa do grupo: o bloco superior esquerdo é identidade (controle=0), o bloco inferior direito permuta os estados base de acordo com o mapa P -> P+S (controle=1).
Usada para curvas maiores. Implementada em quantum_arithmetic.py.
Em vez de construir matrizes densas, cada permutação "add S" é decomposta em ciclos convertidos em transposições. Cada transposição (troca de dois estados base |a> <-> |b>) é implementada com:
O MCX usa decomposição em cadeia-V com (n-2) qubits ancilla dedicados, resultando em O(n) portas Toffoli por MCX em vez de O(n^2) sem ancillas. Cada adição controlada é construída como um subcircuito isolado e anexada como uma única porta opaca, evitando o crescimento quadrático do DAG no Qiskit.
--oracle coordinate)Disponível para curvas de até ~6 bits. Implementada em quantum_oracle.py.
Em vez de codificar pontos como índices de grupo, o registrador quântico mantém as coordenadas reais (x, y) dos elementos de campo em binário mais um sinalizador de identidade. O layout do registrador de ponto é:
x_reg: f_bits qubits (f_bits = ceil(log2(p)))y_reg: f_bits qubitsid_flag: 1 qubit (1 = ponto no infinito)Cada "add S" controlada é computada a partir da fórmula de adição de EC sobre todas as codificações de coordenadas válidas, produzindo uma permutação no registrador de coordenadas. Essa permutação é decomposta em ciclos convertidos em transposições usando a mesma infraestrutura de redução CNOT + MCX da Estratégia 2.
--oracle arithmetic)Estrutura para adição de pontos com escalonamento polinomial. Implementada em quantum_oracle.py e quantum_arithmetic.py.
Usa codificação de coordenadas (mesmo da Estratégia 3) com primitivas aritméticas modulares baseadas em QFT como blocos de construção para adição de pontos totalmente aritmética. O código inclui implementações testadas de:
As primitivas aritméticas alcançam escalonamento O(n^3) por adição de ponto vs O(N*n) para a abordagem de permutação. No entanto, as operações baseadas em QFT carregam um fator constante ~150x maior, tornando a abordagem aritmética mais eficiente apenas para curvas acima de ~20 bits de ordem de grupo. Para os tamanhos atuais do desafio (até 12 bits), o somador baseado em permutação permanece mais rápido e é usado por padrão.
--oracle google)Implementada em google_semiclassical.py. Inspirada na técnica de estimativa de fase com reciclagem de qubits de Griffiths & Niu (1996), aplicada em escala por Babbush et al. (2026) para estimativas de recursos do secp256k1 ECDLP. O artigo de Babbush et al. foi publicado em 30 de março de 2026.
Substitui os dois registradores de contagem multiqubit (j, k) e a QFT inversa em massa por dois qubits reciclados únicos e correções de fase condicionadas classicamente. Cada bit do registrador de contagem é processado sequencialmente: preparar em |+>, aplicar adição de ponto controlada, corrigir fase com base em todos os bits medidos anteriormente, então medir. Os primitivos de circuito dinâmico reset + if_test no Qiskit permitem isso em hardware IBM Quantum.
O oráculo para adições de pontos controladas é delegado à infraestrutura existente (unitário denso para <= 6 bits, permutação eficiente para > 6 bits), então a economia de qubits vem inteiramente da eliminação dos registradores de contagem.
| Tamanho da curva | Qubits padrão | Qubits semiclássicos | Economia | Verificado em hardware |
|---|---|---|---|---|
| 4-bit (n=7) | 11 | 5 | 55% | Sim |
| 6-bit (n=31) | 17 | 7 | 59% | Sim |
| 7-bit (n=79) | 26 + anc | 14 | 46% | Sim |
| 8-bit (n=139) | 25 + anc | 10 + anc | 60% | Não (sobrecarga de sincronização QPU) |
| 10-bit (n=547) | 31 + anc | 12 + anc | 61% | Não (sobrecarga de sincronização QPU) |
--oracle ripple)