Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition

This repository contains Qiskit code for resource estimation of the space-efficient quantum modular inversion and affine point-addition circuits used in elliptic-curve discrete logarithm settings.

The current codebase is centered on three workflows:

1. chunkwise recursive counting of the modular inversion circuit;
2. optional local NCT-template optimization of the circuit;
3. compiled blockwise resource estimation of the wrapped affine point-addition circuit.

---

Repository structure

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

Main entry scripts

• run_eea_s835_fastdual_recursive_chunks_checkpoint.py
  Counts the EEA Algorithm-3 steps recursively, in checkpointed chunks.

• run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
  Same EEA counting workflow, but with local NCT-template optimization.

• count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
  Counts the wrapped point-addition circuit by recursively counting reusable compiled subblocks and assembling the repeated arithmetic components with exact multiplicities.

EEA files

• eea_circuit_s835_fastdual.py: Main implementation of the production EEA circuit.
• eea_circuit_s835_lowaux.py: Low-auxiliary helper routines used by the main implementation.
• eea_circuit_updated.py: Shared EEA building blocks and recursive resource-counting utilities.
• eea_circuit.py: Backward-compatibility wrapper for tests.

Point-addition and arithmetic files

• point_addition_fig14_s835_fastdual_wrapped_quadratic.py: builds the wrapped affine point-addition circuit corresponding to the Fig.14 schedule.
• quadratic_fig15_inplace_s835_fastdual_wrapped.py: builds the Fig.15 in-place division and in-place multiplication structure with EEA, multiplication, measurement, reset, and feed-forward phase correction.
• quadratic_modular_arithmetic.py: modular addition/subtraction, multiplication, inverse multiplication, doubling, and halving instructions used by the point-addition counter.
• quadratic_gidney_arithmetic.py: Gidney-style arithmetic primitives and measurement and feed-forward helpers used by the quadratic modular arithmetic layer.
• quadratic_squ_minus.py: square-minus block used in the affine point-addition schedule.
• under1000_eea_shared_s835_fastdual_wrapped.py: shared EEA wrapper and helper used by the point-addition circuit.
• under1000_modular_arithmetic_base.py: small shared modular-arithmetic utilities.

Counting and optimization utilities

• ccx_recursive_block_counter.py: recursive counter for Qiskit circuits, with policies for MCX expansion and SWAP expansion.
• nct_template_segment_optimizer.py: local template-based optimizer for {X, CX, CCX} segments.

---

Requirements

Recommended environment:

• Python 3.10+
• Qiskit

Install the main dependency with:

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

---

Quick start

Run the test suite:

python test_eea_strict_main.py
python test_point_addition_strict_main.py

For a faster point-addition smoke test:

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

---

1. EEA recursive chunk counting

The standard EEA counting entry point is:

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

Important arguments:

• --n: bit width.
• --T-max: optional override for the number of Algorithm-3 steps; by default the value from eea.get_n_config(n) is used.
• --chunk-size: number of Algorithm-3 steps counted per checkpoint chunk.
• --aux-size: optional override for the helper-qubit pool; if omitted, the layout helper size is computed automatically.
• --measurement-uncompute: enables measurement-based uncomputation in the counted EEA blocks.
• --resume: reuses existing non-empty chunk JSON files in --workdir.
• --workdir: directory for per-chunk checkpoint files.
• --out: cumulative JSON summary written after every chunk.

The script writes per-chunk files such as:

eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json

and a cumulative output JSON containing fields such as:

mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far

---

2. EEA counting with NCT-template optimization

The optimized counting entry point is:

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

This workflow attempts local template optimization on {X, CX, CCX} segments. It is designed as a bounded fail-open counter: if an optimized step times out or raises an exception, that step is counted exactly without template rounds and then checkpointed, so the final reported counts remain complete.

Useful arguments in addition to the standard EEA arguments:

• --templates {small-nct,all-nct}: template library selection.
• --rounds: number of template-optimization rounds.
• --max-nct-segment-gates: maximum size of a reversible segment sent to template optimization.
• --max-nct-segment-qubits: maximum number of qubits in a segment.
• --segment-timeout-s: timeout for individual segment optimization.
• --step-timeout-s: timeout for a whole Algorithm-3 step before falling back to unchanged counting.
• --fallback-step-timeout-s: timeout for the exact fallback count.
• --force: recompute even if step/chunk checkpoints already exist.
• --ignore-policy-mismatch: reuse old checkpoints even when the optimization policy differs; this is mainly for debugging.

The optimized workflow writes both step-level checkpoints under:

<workdir>/steps/

and chunk-level summaries under:

<workdir>/

---

3. Wrapped point-addition compiled blockwise counting

The point-addition counter depends on an EEA Algorithm-3 JSON produced by one of the EEA workflows above. The --n value of the point-addition counter should match the n field in the EEA JSON.

Example for 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

Then run: