zerowang030221/quantum-algorithm-for-elliptic-curve-discrete-logarithms-with-space-efficient-point-additionFramework de estimativa de recursos baseado em Qiskit para circuitos de inversão modular quântica e adição de pontos afins com eficiência de espaço, usados em algoritmos de logaritmo discreto em curvas elípticas.
Este repositório contém código Qiskit para estimativa de recursos dos circuitos quânticos de inversão modular eficiente em espaço e adição de pontos afins usados em configurações de logaritmos discretos em curvas elípticas.
O código atual está centrado em três fluxos de trabalho:
.
├── README.md
│
├── eea_model/: implementação original clássica de referência do EEA, usada para prototipagem do algoritmo e validação de correção.
│
├── run_eea_s835_fastdual_recursive_chunks_checkpoint.py
├── run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
├── count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
│
├── eea_circuit.py
├── eea_circuit_s835_fastdual.py
├── eea_circuit_s835_lowaux.py
├── eea_circuit_updated.py
├── under1000_eea_shared_s835_fastdual_wrapped.py
├── under1000_modular_arithmetic_base.py
│
├── point_addition_fig14_s835_fastdual_wrapped_quadratic.py
├── quadratic_fig15_inplace_s835_fastdual_wrapped.py
├── quadratic_gidney_arithmetic.py
├── quadratic_lazy_instruction.py
├── quadratic_modular_arithmetic.py
├── quadratic_squ_minus.py
│
├── ccx_recursive_block_counter.py
├── nct_template_segment_optimizer.py
│
├── test_eea_strict_main.py
└── test_point_addition_strict_main.py
run_eea_s835_fastdual_recursive_chunks_checkpoint.py
Conta os passos do Algoritmo-3 do EEA recursivamente, em blocos com checkpoint.
run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
Mesmo fluxo de contagem do EEA, mas com otimização local de template NCT.
count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
Conta o circuito de adição de pontos encapsulado contando recursivamente sub-blocos reutilizáveis compilados e montando os componentes aritméticos repetidos com multiplicidades exatas.
eea_circuit_s835_fastdual.py: Implementação principal do circuito EEA de produção.eea_circuit_s835_lowaux.py: Rotinas auxiliares de baixo nível usadas pela implementação principal.eea_circuit_updated.py: Blocos de construção EEA compartilhados e utilitários de contagem recursiva de recursos.eea_circuit.py: Encapsulador de compatibilidade reversa para testes.point_addition_fig14_s835_fastdual_wrapped_quadratic.py: constrói o circuito encapsulado de adição de pontos afins correspondente ao cronograma da Fig.14.quadratic_fig15_inplace_s835_fastdual_wrapped.py: constrói a estrutura da Fig.15 de divisão in-place e multiplicação in-place com EEA, multiplicação, medição, reset e correção de fase feed-forward.quadratic_modular_arithmetic.py: instruções de adição/subtração modular, multiplicação, multiplicação inversa, duplicação e redução pela metade usadas pelo contador de adição de pontos.quadratic_gidney_arithmetic.py: primitivas aritméticas estilo Gidney e auxiliares de medição e feed-forward usados pela camada aritmética modular quadrática.quadratic_squ_minus.py: bloco square-minus usado no cronograma de adição de pontos afins.under1000_eea_shared_s835_fastdual_wrapped.py: encapsulador EEA compartilhado e auxiliar usado pelo circuito de adição de pontos.under1000_modular_arithmetic_base.py: pequenos utilitários aritméticos modulares compartilhados.ccx_recursive_block_counter.py: contador recursivo para circuitos Qiskit, com políticas para expansão MCX e expansão SWAP.nct_template_segment_optimizer.py: otimizador local baseado em templates para segmentos {X, CX, CCX}.Ambiente recomendado:
Instale a dependência principal com:
python -m pip install --upgrade pip
python -m pip install qiskit
Execute o conjunto de testes:
python test_eea_strict_main.py
python test_point_addition_strict_main.py
Para um teste rápido de adição de pontos:
python test_point_addition_strict_main.py --skip-n256 --skip-report
O ponto de entrada padrão para contagem EEA é:
python run_eea_s835_fastdual_recursive_chunks_checkpoint.py \
--n 192 \
--chunk-size 25 \
--measurement-uncompute \
--resume \
--workdir eea_s835_fastdual_chunks25 \
--out eea_s835_fastdual_algorithm3_recursive_chunks_n192_measurement.json
Argumentos importantes:
--n: largura de bits.--T-max: substituição opcional para o número de passos do Algoritmo-3; por padrão, o valor de eea.get_n_config(n) é usado.--chunk-size: número de passos do Algoritmo-3 contados por bloco de checkpoint.--aux-size: substituição opcional para o pool de qubits auxiliares; se omitido, o tamanho do layout auxiliar é computado automaticamente.--measurement-uncompute: habilita a descomputação baseada em medição nos blocos EEA contados.--resume: reutiliza arquivos JSON de bloco existentes e não vazios em --workdir.--workdir: diretório para arquivos de checkpoint por bloco.--out: resumo JSON cumulativo escrito após cada bloco.O script escreve arquivos por bloco como:
eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json
e um JSON de saída cumulativo contendo campos como:
mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far
O ponto de entrada para contagem otimizada é:
python run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py \
--n 128 \
--chunk-size 25 \
--measurement-uncompute \
--templates small-nct \
--rounds 1 \
--max-nct-segment-gates 40 \
--segment-timeout-s 10 \
--timeout-mode auto \
--resume \
--workdir eea_s835_fastdual_chunks_nctopt_failopen_r1_128_seg40_to10 \
--out eea_s835_fastdual_algorithm3_recursive_chunks_n128_measurement_nctopt_failopen_r1_seg40_to10.json
Este fluxo tenta otimização local de template em segmentos {X, CX, CCX}. Ele é projetado como um contador fail-open limitado: se um passo otimizado expirar ou gerar uma exceção, esse passo é contado exatamente sem rodadas de template e então checkpointado, de modo que as contagens finais relatadas permanecem completas.
Argumentos úteis além dos argumentos padrão do EEA:
--templates {small-nct,all-nct}: seleção da biblioteca de templates.--rounds: número de rodadas de otimização de template.--max-nct-segment-gates: tamanho máximo de um segmento reversível enviado para otimização de template.--max-nct-segment-qubits: número máximo de qubits em um segmento.--segment-timeout-s: tempo limite para otimização de segmento individual.--step-timeout-s: tempo limite para um passo inteiro do Algoritmo-3 antes de recair na contagem inalterada.--fallback-step-timeout-s: tempo limite para a contagem exata de fallback.--force: recalcula mesmo que checkpoints de passo/bloco já existam.--ignore-policy-mismatch: reutiliza checkpoints antigos mesmo quando a política de otimização difere; isso é principalmente para depuração.O fluxo otimizado escreve checkpoints de nível de passo sob:
<workdir>/steps/
e resumos de nível de bloco sob:
<workdir>/
O contador de adição de pontos depende de um JSON do Algoritmo-3 EEA produzido por um dos fluxos EEA acima. O valor --n do contador de adição de pontos deve corresponder ao campo n no JSON EEA.
Exemplo para n=64:
python run_eea_s835_fastdual_recursive_chunks_checkpoint.py \
--n 64 \
--chunk-size 25 \
--measurement-uncompute \
--resume \
--workdir eea_s835_fastdual_chunks25_n64 \
--out eea_s835_fastdual_algorithm3_recursive_chunks_n64_measurement.json
Então execute:
python count_s835_fastdual_wrapped_point_addition_blocks_compiled.py \
--n 64 \
--eea-steps-json eea_s835_fastdual_algorithm3_recursive_chunks_n64_measurement.json \
--out point_addition_s835_fastdual_wrapped_blocks_compiled_counts_n64.json
Exemplo para a saída EEA otimizada n=128:
python count_s835_fastdual_wrapped_point_addition_blocks_compiled.py \
--n 128 \
--eea-steps-json eea_s835_fastdual_algorithm3_recursive_chunks_n128_measurement_nctopt_failopen_r1_seg40_to10.json \
--out point_addition_s835_fastdual_wrapped_blocks_compiled_counts_n128.json
Argumentos importantes:
--n: largura de bits.--p: módulo; padrão é o primo secp256k1.--s-qubits: substituição opcional para o tamanho do registo aritmético EEA compartilhado.--point-constant {secp256k1-generator,zero,custom}: seleção de constante de ponto para as atualizações de coordenadas constantes da Fig.14.--x2, --y2: coordenadas de ponto personalizadas; necessário quando --point-constant custom é usado.--eea-steps-json: arquivo JSON contendo contagens recursivas do Algoritmo-3 EEA.--allow-eea-n-mismatch: substituição apenas de depuração permitindo que o n do JSON EEA difira do --n solicitado.--mcx-policy {clean-vchain,keep}: política de expansão MCX para contagem recursiva.O relatório de saída inclui:
counting_mode
n
p
point_constant_kind
qiskit_width_report
eea_meta
block_summaries
raw_block_counters
key_ccx
validation
elapsed_s
O contador de adição de pontos constrói circuitos Qiskit reutilizáveis, conta-os recursivamente na base {CCX, CX, X} e então monta blocos repetidos maiores como multiplicação, multiplicação inversa, divisão in-place, multiplicação in-place, square-minus e o bloco total de adição de pontos da Fig.14.
Este repositório inclui dois drivers de teste Python simples. Eles foram intencionalmente escritos sem pytest, Aer ou simulação completa de statevector. Os testes expandem recursivamente definições Qiskit quando apropriado e simulam estados de base computacional para blocos de rede de Toffoli.
Os testes EEA estão em:
test_eea_strict_main.py
Execute o conjunto padrão EEA com:
python test_eea_strict_main.py
O conjunto padrão verifica:
n pequeno;3, 5, 7, 11, 13, 17, usando contagens exatas de passos e T_max fixo;3, 5, 7.Variantes úteis:
# Apenas testes estruturais e de bloco rápidos.
python test_eea_strict_main.py --skip-endpoint --skip-alg1
# Inclui o benchmark de rastreamento PDF/Tabela-4 p=37, x=13 mais pesado.
python test_eea_strict_main.py --table4
# Testa todos os valores x para primos acima de 13 também.
python test_eea_strict_main.py --primes 3 5 7 11 13 17 --mid-all-x --verbose
Os testes de adição de pontos estão em:
test_point_addition_strict_main.py
Execute o conjunto padrão de adição de pontos com:
python test_point_addition_strict_main.py
O conjunto padrão de adição de pontos verifica:
n=256 de largura 835 = 1 + 3*256 + 66;H, measure, reset, Z controlado classicamente e swap;A matriz de regressão de primo grande cobre pares representativos da largura de bits do corpo n e do módulo primo p, variando de corpos primos de 12 bits a 512 bits. As instâncias testadas incluem, por exemplo, n=16, p=65521, n=32, p=4294967291, o primo secp256k1 em n=256 e primos representativos em n=128, 160, 192, 224, 384, 512.
Para cada par (n,p), os testes incluem traços EEA de limite, simétricos, aleatórios e relativamente longos. A montagem aritmética compilada completa é executada apenas para instâncias de largura moderada selecionadas, enquanto os pares (n,p) maiores são usados para validar construção de circuito, layout de registo, cronograma e caminhos de contagem recursiva de recursos.
Variantes úteis:
# Ignora o relatório integrado minúsculo e verifica apenas construção/cronograma/montagem.
python test_point_addition_strict_main.py --skip-report
# Teste rápido que também ignora a verificação de construção da largura n=256.
python test_point_addition_strict_main.py --skip-n256 --skip-report
# Usa um primo/largura pequeno diferente para validação de bloco compilado.
python test_point_addition_strict_main.py --n 5 --p 17
Se o Qiskit não estiver instalado, test_point_addition_strict_main.py imprime uma mensagem de ignorar e sai com sucesso. O teste estrito EEA requer Qiskit porque ele constrói os blocos de portas EEA/PDF.
Nosso artigo relata resultados numéricos de estimativa de recursos para:
n = 64, 128, 160, 192, 224, 256, 384, 512
Um fluxo de trabalho típico é:
n;n;key_ccx, block_summaries e qiskit_width_report do relatório de saída.Para larguras grandes, use --resume e mantenha os diretórios --workdir, pois os checkpoints de bloco e passo são projetados para suportar execuções longas interrompidas.
Se você usar este código em sua pesquisa, por favor cite:
@misc{luo2026quantumalgorithmellipticcurve,
title={Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition},
author={Han Luo and Ziyi Yang and Jingquan Luo and Ziruo Wang and Yuexin Su and Xiaoming Sun and Lvzhou Li and Tongyang Li},
year={2026},
eprint={2607.13816},
archivePrefix={arXiv},
primaryClass={quant-ph},
url={https://arxiv.org/abs/2607.13816},
}
--validate-full-mul: para n pequeno, conta recursivamente definições completas de multiplicação/quadrado e as compara com as contagens de blocos montados.--out: caminho do JSON de saída.