Algoritmo Quântico para Logaritmos Discretos em Curvas Elípticas com Adição de Pontos Eficiente em Espaço

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:

1. contagem recursiva em blocos do circuito de inversão modular;
2. otimização local opcional de template NCT do circuito;
3. estimativa de recursos compilada em blocos do circuito de adição de pontos afins encapsulado.

---

Estrutura do repositório

.
├── 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

Scripts de entrada principais

• 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.

Arquivos EEA

• 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.

Arquivos de adição de pontos e aritmética

• 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.

Utilitários de contagem e otimização

• 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}.

---

Requisitos

Ambiente recomendado:

• Python 3.10+
• Qiskit

Instale a dependência principal com:

python -m pip install --upgrade pip
python -m pip install qiskit

---

Início rápido

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

---

1. Contagem recursiva de blocos EEA

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

---

2. Contagem EEA com otimização de template NCT

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>/

---

3. Contagem compilada em blocos de adição de pontos encapsulada

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: