Algoritmo Quantistico per i Logaritmi Discreti su Curve Ellittiche con Addizione di Punti Efficiente in Spazio

Questo repository contiene codice Qiskit per la stima delle risorse dei circuiti quantistici di inversione modulare e di addizione di punti affine efficienti in termini di spazio, usati in contesti di logaritmi discreti su curve ellittiche.

Il codebase attuale è incentrato su tre flussi di lavoro:

1. conteggio ricorsivo a chunk del circuito di inversione modulare;
2. ottimizzazione locale opzionale del circuito tramite template NCT;
3. stima compilata delle risorse a blocchi del circuito di addizione di punti affine incapsulato.

Struttura del repository

.
├── README.md
│
├── eea_model/: original classical EEA reference implementation used for algorithm prototyping and correctness validation.
│
├── 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

Script di ingresso principali

• run_eea_s835_fastdual_recursive_chunks_checkpoint.py
  Conta i passi dell'Algoritmo-3 EEA ricorsivamente, in chunk con checkpoint.

• run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
  Stesso flusso di conteggio EEA, ma con ottimizzazione locale tramite template NCT.

• count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
  Conta il circuito di addizione di punti incapsulato contando ricorsivamente i sottoblocchi compilati riutilizzabili e assemblando i componenti aritmetici ripetuti con molteplicità esatte.

File EEA

• eea_circuit_s835_fastdual.py: Implementazione principale del circuito EEA di produzione.
• eea_circuit_s835_lowaux.py: Routine helper con pochi qubit ausiliari usate dall'implementazione principale.
• eea_circuit_updated.py: Blocchi di costruzione EEA condivisi e utilità di conteggio ricorsivo delle risorse.
• eea_circuit.py: Wrapper di compatibilità all'indietro per i test.

File per addizione di punti e aritmetica

• point_addition_fig14_s835_fastdual_wrapped_quadratic.py: costruisce il circuito di addizione di punti affine incapsulato corrispondente allo schedule della Fig.14.
• quadratic_fig15_inplace_s835_fastdual_wrapped.py: costruisce la struttura di divisione in-place e moltiplicazione in-place della Fig.15 con EEA, moltiplicazione, misurazione, reset e correzione di fase feed-forward.
• quadratic_modular_arithmetic.py: istruzioni di addizione/sottrazione modulare, moltiplicazione, moltiplicazione inversa, raddoppio e dimezzamento usate dal contatore di addizione di punti.
• quadratic_gidney_arithmetic.py: primitive aritmetiche in stile Gidney e helper di misurazione e feed-forward usati dal livello di aritmetica modulare quadratica.
• quadratic_squ_minus.py: blocco square-minus usato nello schedule dell'addizione di punti affine.
• under1000_eea_shared_s835_fastdual_wrapped.py: wrapper EEA condiviso e helper usati dal circuito di addizione di punti.
• under1000_modular_arithmetic_base.py: piccole utilità condivise di aritmetica modulare.

Utilità di conteggio e ottimizzazione

• ccx_recursive_block_counter.py: contatore ricorsivo per circuiti Qiskit, con policy per l'espansione MCX e l'espansione SWAP.
• nct_template_segment_optimizer.py: ottimizzatore locale basato su template per i segmenti {X, CX, CCX}.

Requisiti

Ambiente consigliato:

• Python 3.10+
• Qiskit

Installa la dipendenza principale con:

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

Avvio rapido

Esegui la suite di test:

python test_eea_strict_main.py
python test_point_addition_strict_main.py

Per uno smoke test più rapido dell'addizione di punti:

python test_point_addition_strict_main.py --skip-n256 --skip-report

1. Conteggio ricorsivo a chunk dell'EEA

Il punto di ingresso standard per il conteggio 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

Argomenti importanti:

• --n: larghezza in bit.
• --T-max: override opzionale per il numero di passi dell'Algoritmo-3; di default viene usato il valore da eea.get_n_config(n).
• --chunk-size: numero di passi dell'Algoritmo-3 contati per chunk di checkpoint.
• --aux-size: override opzionale per il pool di qubit helper; se omesso, la dimensione degli helper del layout viene calcolata automaticamente.
• --measurement-uncompute: abilita l'uncomputation basato su misurazione nei blocchi EEA contati.
• --resume: riutilizza i file JSON di chunk non vuoti esistenti in --workdir.
• --workdir: directory per i file di checkpoint per chunk.
• --out: riepilogo JSON cumulativo scritto dopo ogni chunk.

Lo script scrive file per chunk come:

eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json

e un JSON di output cumulativo contenente campi come:

mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far

2. Conteggio EEA con ottimizzazione tramite template NCT

Il punto di ingresso per il conteggio ottimizzato è:

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

Questo flusso di lavoro tenta l'ottimizzazione locale tramite template sui segmenti {X, CX, CCX}. È progettato come un contatore fail-open con limite: se un passo ottimizzato va in timeout o solleva un'eccezione, quel passo viene contato esattamente, senza round di template, e poi salvato tramite checkpoint, così i conteggi finali riportati rimangono completi.

Argomenti utili in aggiunta a quelli standard dell'EEA:

• --templates {small-nct,all-nct}: selezione della libreria di template.
• --rounds: numero di round di ottimizzazione tramite template.
• --max-nct-segment-gates: dimensione massima di un segmento reversibile inviato all'ottimizzazione tramite template.
• --max-nct-segment-qubits: numero massimo di qubit in un segmento.
• --segment-timeout-s: timeout per l'ottimizzazione del singolo segmento.
• --step-timeout-s: timeout per un intero passo dell'Algoritmo-3 prima di ripiegare sul conteggio invariato.
• --fallback-step-timeout-s: timeout per il conteggio di fallback esatto.
• --force: ricalcola anche se i checkpoint di passo/chunk esistono già.
• --ignore-policy-mismatch: riutilizza i vecchi checkpoint anche quando la policy di ottimizzazione differisce; serve principalmente al debug.

Il flusso di lavoro ottimizzato scrive sia i checkpoint a livello di passo in:

<workdir>/steps/

sia i riepiloghi a livello di chunk in:

<workdir>/

3. Conteggio compilato a blocchi dell'addizione di punti incapsulata

Il contatore di addizione di punti dipende da un JSON dell'Algoritmo-3 EEA prodotto da uno dei flussi di lavoro EEA descritti sopra. Il valore --n del contatore di addizione di punti deve corrispondere al campo n nel JSON EEA.

Esempio per 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

Quindi esegui:

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

Esempio per l'output EEA ottimizzato 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

Argomenti importanti:

• --n: larghezza in bit.
• --p: modulo; di default è il primo secp256k1.
• --s-qubits: override opzionale per la dimensione del registro aritmetico EEA condiviso.
• --point-constant {secp256k1-generator,zero,custom}: selezione della costante del punto per gli aggiornamenti a coordinate costanti della Fig.14.
• --x2, --y2: coordinate personalizzate del punto; richieste quando si usa --point-constant custom.
• --eea-steps-json: file JSON contenente i conteggi EEA ricorsivi dell'Algoritmo-3.
• --allow-eea-n-mismatch: override solo per debug che consente all'n del JSON EEA di differire dal --n richiesto.
• --mcx-policy {clean-vchain,keep}: policy di espansione MCX per il conteggio ricorsivo.

Il report di output include:

counting_mode
n
p
point_constant_kind
qiskit_width_report
eea_meta
block_summaries
raw_block_counters
key_ccx
validation
elapsed_s

Il contatore di addizione di punti costruisce circuiti Qiskit riutilizzabili, li conta ricorsivamente nella base {CCX, CX, X} e poi assembla blocchi ripetuti più grandi, come moltiplicazione, moltiplicazione inversa, divisione in-place, moltiplicazione in-place, square-minus e il blocco totale di addizione di punti della Fig.14.

Test

Questo repository include due driver di test in Python puro. Sono scritti intenzionalmente senza pytest, Aer o simulazione completa dello statevector. I test espandono ricorsivamente le definizioni Qiskit dove opportuno e simulano gli stati della base computazionale per i blocchi di reti Toffoli.

Test EEA rigorosi

I test EEA si trovano in:

test_eea_strict_main.py

Esegui la suite EEA predefinita con:

python test_eea_strict_main.py

La suite predefinita verifica:

• l'assenza di scorciatoie per gli endpoint a n piccolo;
• la presenza dello schedule a blocchi tratteggiati dell'Algoritmo-3;
• le formule della finestra attiva su diverse larghezze piccole;
• i blocchi di iterazione unaria, shift pre/post, aggiornamento di fase, swap controllato dalla posizione e aggiornamento della lunghezza;
• gli endpoint dell'Algoritmo-3 per i primi predefiniti 3, 5, 7, 11, 13, 17, usando sia i conteggi esatti dei passi sia un T_max fisso;
• il wrapper completo dell'Algoritmo-1 per i piccoli primi predefiniti 3, 5, 7.

Varianti utili:

# Fast structural + block tests only.
python test_eea_strict_main.py --skip-endpoint --skip-alg1

# Include the heavier PDF/Table-4 p=37, x=13 trace benchmark.
python test_eea_strict_main.py --table4

# Test all x values for primes above 13 as well.
python test_eea_strict_main.py --primes 3 5 7 11 13 17 --mid-all-x --verbose

Test rigorosi dell'addizione di punti

I test dell'addizione di punti si trovano in:

test_point_addition_strict_main.py

Esegui la suite predefinita di addizione di punti con:

python test_point_addition_strict_main.py

La suite predefinita di addizione di punti verifica:

• il layout dei registri dell'addizione di punti incapsulata;
• l'identità di larghezza n=256 835 = 1 + 3*256 + 66;
• l'ordine delle operazioni di primo livello delle Fig.14/Fig.15;
• la struttura esplicita di circuito dinamico che coinvolge operazioni H, measure, reset, Z controllate classicamente e swap;
• l'assemblaggio compilato dei sottoblocchi aritmetici per un modulo piccolo;
• un piccolo report integrato del contatore di addizione di punti che usa un JSON sintetico dell'Algoritmo-3, così il percorso del report viene testato senza eseguire un grande conteggio EEA.

La matrice di regressione con primi grandi copre coppie rappresentative della larghezza in bit del campo n e del modulo primo p, spaziando da campi primi a 12 bit fino a 512 bit. Le istanze testate includono, ad esempio, n=16, p=65521, n=32, p=4294967291, il primo secp256k1 a n=256 e primi rappresentativi a n=128, 160, 192, 224, 384, 512.

Per ogni coppia (n,p), i test includono tracce EEA di confine, simmetriche, casuali e relativamente lunghe. L'assemblaggio completo dell'aritmetica compilata viene eseguito solo per istanze selezionate di larghezza moderata, mentre le coppie (n,p) più grandi vengono usate per validare la costruzione del circuito, il layout dei registri, la schedulazione e i percorsi di conteggio ricorsivo delle risorse.

Varianti utili:

# Skip the tiny integrated report and only check construction/schedule/assembly.
python test_point_addition_strict_main.py --skip-report

# Fast smoke test that also skips the n=256 width construction check.
python test_point_addition_strict_main.py --skip-n256 --skip-report

# Use a different small prime/width for compiled-block validation.
python test_point_addition_strict_main.py --n 5 --p 17

Se Qiskit non è installato, test_point_addition_strict_main.py stampa un messaggio di skip ed esce con successo. Il test EEA rigoroso richiede Qiskit perché costruisce le porte a blocchi EEA/PDF.

Riproduzione delle statistiche principali

Il nostro articolo riporta risultati numerici di stima delle risorse per:

n = 64, 128, 160, 192, 224, 256, 384, 512

Un flusso di lavoro tipico è:

1. esegui il contatore dell'Algoritmo-3 EEA per un dato n;
2. se lo si desidera, esegui la versione ottimizzata NCT per lo stesso n;
3. passa il JSON EEA risultante al contatore dell'addizione di punti incapsulata;
4. raccogli i campi key_ccx, block_summaries e qiskit_width_report dal report di output.

Per larghezze grandi, usa --resume e conserva le directory --workdir, poiché i checkpoint di chunk e di passo sono pensati per supportare esecuzioni lunghe interrotte.

Citazione

Se utilizzi questo codebase nella tua ricerca, ti preghiamo di citare:

@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}, 
}