giancarlolelli/quantumEste repositório contém o código e os detalhes de submissão para o desafio do prêmio QDay por https://www.projecteleven.com/
Solucionador quântico para o Problema do Logaritmo Discreto em Curvas Elípticas (ECDLP), desenvolvido para o Q-Day Prize Challenge 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), coincidindo com a família secp256k1. O solucionador implementa a variante de dois registros 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 solucionador 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 de 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 é a 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 transposições a partir de sua estrutura de ciclos. 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 portas Toffoli O(n) 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 registro quântico mantém as coordenadas reais (x, y) dos elementos de campo em binário mais uma flag de identidade. O layout do registro 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 curvas elípticas sobre todas as codificações de coordenadas válidas, produzindo uma permutação no registro de coordenadas. Essa permutação é decomposta 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 por coordenadas (mesmo da Estratégia 3) com primitivas de aritmética modular baseadas em QFT como blocos de construção para uma 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 versus 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 de 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 estimação de fase com reciclagem de qubits de Griffiths & Niu (1996), aplicada em escala por Babbush et al. (2026) para estimativas de recursos do ECDLP secp256k1. O artigo de Babbush et al. foi publicado em 30 de março de 2026.
Substitui os dois registros de contagem multi-qubit (j, k) e a QFT inversa em massa por dois qubits reciclados únicos e correções de fase condicionadas classicamente. Cada bit do registro de contagem é processado sequencialmente: preparar em |+>, aplicar adição de ponto controlada, corrigir a fase com base em todos os bits previamente medidos e então medir. Os primitivos de circuitos dinâmicos reset + if_test no Qiskit permitem isso no 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), portanto a economia de qubits vem inteiramente da eliminação dos registros de contagem.
| Tamanho da curva | Qubits padrão | Qubits semiclássicos | Economia | Verificado em hardware |
|---|---|---|---|---|
| 4 bits (n=7) | 11 | 5 | 55% | Sim |
| 6 bits (n=31) | 17 | 7 | 59% | Sim |
| 7 bits (n=79) | 26 + anc | 14 | 46% | Sim |
| 8 bits (n=139) | 25 + anc | 10 + anc | 60% | Não (overhead de sincronização QPU) |
| 10 bits (n=547) | 31 + anc | 12 + anc | 61% | Não (overhead de sincronização QPU) |