CHEVIGNARD_2026_TRANSCRIPTION_CHECKLIST.md

Chevignard 2026 Transcription Checklist

Purpose

This checklist maps the 2026 paper's actual construction to the current direct Qualtran implementation in this repo.

Its goal is not to restate the benchmark headline. Its goal is to answer:

1. Which parts of the paper are explicitly implemented?
2. Which parts are only approximately or structurally reconstructed?
3. Which parts are still our own engineering search space rather than paper transcription?

Primary paper:

• Chevignard, Fouque, Schrottenloher, "Reducing the Number of Qubits in Quantum Discrete Logarithms on Elliptic Curves", ePrint 2026/280

Source discrepancy that must stay visible

The paper contains an internal tension that matters for our benchmarking:

• The abstract says that for n = 256, the estimate is 1098 qubits with 22 independent runs and 2^38.10 Toffoli gates each.
• The detailed Table 8 on page 27 shows:
  • P-224 -> 1098
  • P-256 -> 1193
  • P-384 -> 1494
  • P-521 -> 1895

For our purposes this means:

• 1098 is definitely paper-backed as a published number.
• But 1098 is not unambiguously the paper's P-256 / secp256k1-comparable line.
• For P-256-style comparison, the detailed table currently points to 1193, not 1098.

So any external claim must specify whether it is comparing against:

• the abstract-level n = 256 headline, or
• the detailed P-256 Table 8 row.

Paper elements we can now verify directly

From the paper text we can now confirm the following high-level structure:

• The core target is point multiplication on a fixed point kP, not explicit affine recovery of the point.
• The paper computes projective coordinates directly in an RNS.
• The paper avoids modular inversion by compressing with a Legendre symbol, reducing the problem to computing XZ mod q.
• The paper uses May-Schlieper compression plus the compressed Ekerå-Håstad algorithm.
• The low-space XZ mod q computation is done via:
  • windowing
  • a binary tree of point additions
  • spooky pebbling
  • RNS reconstruction
• The point addition formula is a degree-4 complete projective addition formula from the cited source [33], implemented reversibly as Algorithm 1.
• The paper's detailed-table P-224 line is:
  • 1098 qubits
  • 22 runs
  • 2^38.10 Toffoli gates per run
• The paper's detailed-table P-256 line is:
  • 1193 qubits
  • 22 runs
  • 2^39.98 Toffoli gates per run

Mapping: paper -> current implementation

Paper item	Paper status	Repo mapping	Mapping status	Notes
Fixed-point multiplication kP in low-space Shor/Ekerå-Håstad setting	Explicit in paper intro and Section 3/4	qualtran_chevignard_backend.py top-level attack model	Partial	We implement the fixed-point low-space family, but the exact paper call structure is still reconstructed.
Complete projective point addition formula from [33]	Explicit, Section 2.2 / Algorithm 1	ProjectivePointAddBloq	Partial	We model reversible projective point addition with explicit subkernels, but not as a literal line-by-line transcription of Algorithm 1.
Algorithm 1 uses 34 multiply-adds and 8 temporary registers	Explicit, Lemma 1 / Algorithm 1	qualtran_chevignard_backend.py	Missing exact transcription	Our point-add bloq models aggregate costs; it does not yet encode the exact 20 forward + 14 reverse multiply-add structure.
RNS reconstruction of T(e) mod q	Explicit, Section 2.3 / Algorithm 2	qualtran_chevignard_independent_counter.py and qualtran_chevignard_backend.py	Partial	We implement explicit residue-level kernels and reconstruction-style aggregation, but not a literal transcription of Algorithm 2 with quotient register structure.
Legendre-symbol hash family replacing affine recovery	Explicit, Section 4.1	LegendreCompressionBloq and qualtran_chevignard_correctness.py	Implemented at family level	The core XZ-to-Legendre idea is implemented and checked semantically.
Space-efficient Legendre / Jacobi circuit	Explicit, Section 4.2 / Algorithm 3/4 / Lemma 4	LegendreAccumulatorBloq	Partial	We model a direct Legendre stage, but not a literal bit-level reversible Jacobi circuit with the exact garbage-reuse scheme of Section 4.3.
Multi-addition with windowing	Explicit, Section 5.1	LookupWindowBloq	Implemented at family level	Windowed fixed-point accumulation is explicit in our backend.
Binary tree of additions	Explicit, Section 5.2	FaithfulChevignardAttackBloq	Implemented structurally	The attack is built as lookup -> tree-style projective accumulation -> compression.
Spooky pebbling strategy	Explicit, Section 5.4 / Lemma 7 / Cor. 1	qualtran_chevignard_backend.py	Not literally transcribed	We account for the low-space tree regime, but we do not yet encode the exact ghost-pebble strategy from [25] step by step.
1098 / 22 / 2^38.10 reference point	Explicit in abstract and in the detailed P-224 row of Table 8	qualtran_chevignard_candidate.py default config	Reproduced	Default direct candidate reproduces 1098, 22 runs, and the same Toffoli scale.
P-256 -> 1193 row	Explicit in detailed Table 8	chevignard_p256_table8_candidate.py and baselines.py	Profile added	This is now the paper-backed detailed-table comparator we should use for P-256/secp256k1-style comparisons.

Mapping: repo kernels -> paper support level

Repo kernel / knob	Paper-backed?	Status
CarrylessResidueAddBloq	Indirectly	Reasonable residue-arithmetic building block; not named as a standalone primitive in the paper.
ConstantResidueAddBloq	Indirectly	Same as above.
RNSMultiplyBloq	Yes, family-level	The paper explicitly requires RNS arithmetic over small primes, but our exact kernel cost model is reconstructed.
SpecialPrimeReduceBloq	No clear paper commitment	The paper focuses on prime-field arithmetic and RNS reconstruction; our special-prime strategy knob is an engineering choice.
ProjectivePointAddBloq	Yes, family-level	Paper explicitly uses projective point addition, but our implementation is not a line-by-line Algorithm 1 transcription yet.
LegendreAccumulatorBloq	Yes, family-level	Paper explicitly uses a Legendre/Jacobi stage, but our accumulator is still a modeled stage, not the exact reversible loop structure of Section 4.
LegendreCompressionBloq	Yes	This maps directly to the paper's compression idea.
LookupWindowBloq	Yes	Windowing is explicitly described in Section 5.1.
CoordinatePackBloq / CoordinateUnpackBloq	No	These are our reconstruction/engineering choices.
LookupPreparationBloq / LookupCleanupBloq	No	Our engineering choices for lookup materialization.
QuotientFoldBloq	No	Our engineering choice for reduction folding.

Current reconstructed engineering knobs that are not paper-faithful by default

These dimensions are useful for search, but should not be presented as paper-provided constructions:

• coordinate_packing
• lookup_materialization
• reduction_pipeline
• register_sharing_strategy
• multiple legendre_strategy variants
• multiple projective_schedule variants
• multiple rns_variant layouts beyond what is explicitly recoverable from the paper text

Current example: the 969 winner depends on:

• coordinate_packing=xz_streamed
• reduction_pipeline=quotient_folding
• register_sharing_strategy=full_overlap

These are not yet paper-transcribed features. They are our current best reconstruction/search choices.

What is now strong enough to say

We can now say:

We implemented a direct Qualtran reconstruction of the Chevignard-style low-space family, reproduced a paper-backed 1098 reference point, and verified both that reference point and our current 969 winner with two independent counting paths.

What is still too strong to say

We should still avoid saying:

We have a line-by-line faithful transcription of the full Chevignard circuit.

or:

We have definitively beaten the paper on the paper's own exact P-256 implementation.

That is still too strong for two separate reasons:

1. We do not yet have a line-by-line faithful transcription.
2. The paper's own abstract/detail discrepancy means the correct external comparator for P-256 is not just the 1098 headline.

Remaining transcription tasks

High priority

• Translate Algorithm 1 into an explicit reversible subcircuit checklist:
  • 20 forward multiply-adds
  • 14 reverse multiply-adds
  • 8 temporary registers
• Translate Algorithm 2 into an explicit reconstruction checklist:
  • quotient register handling
  • residue accumulation order
  • reversible cleanup path
• Translate the Section 4.2 / 4.3 Jacobi/Legendre circuit into a direct reversible implementation checklist:
  • fixed iteration count
  • garbage-bit storage policy
  • compact register reuse

Medium priority

• Replace paper-unbacked engineering knobs one by one with explicit paper-derived structure where possible.
• Identify which current low-width gains survive after that replacement.

Claim gate

We should only promote the 969 result to a paper-level external claim after:

1. Algorithm 1 / 2 / 4 are explicitly transcribed or reconciled line-by-line.
2. The 969 winner still exists after removing or isolating non-paper-backed engineering knobs.
3. The second counting path continues to match the paper-faithful implementation exactly.

Algorithm-by-algorithm transcription boxes

Algorithm 1: reversible projective point addition

• Represent the exact (X1:Y1:Z1) + (X2:Y2:Z2) formula from Section 2.2.
• Encode the exact temporary-register structure t0..t7.
• Preserve the exact operation count:
  • 20 forward multiply-adds
  • 14 reverse multiply-adds
  • 34 total multiply-adds
• Distinguish explicitly between:
  • multiply-adds modulo the current modulus
  • in-place additions
  • in-place doublings / halvings
• Verify that the direct backend point-add implementation can be traced back to these exact steps rather than only to an aggregate cost model.

Algorithm 2: RNS reconstruction

• Encode the exact reconstruction inputs:
  • [M]_q
  • (w_p floor(2^u / p))
  • [w_p M_p]_q
• Encode the quotient register / qM handling explicitly.
• Encode the reversible accumulation order explicitly.
• Verify the cleanup path against the paper's reversible reconstruction flow.
• Separate paper-specified reconstruction from our own reduction-pipeline search knobs.

Algorithm 3 / 4: Legendre / Jacobi circuit

• Encode the actual binary Jacobi loop structure from Section 4.2 / 4.3.
• Encode the exact fixed iteration budget implied by Heuristics 3 and 4.
• Encode the garbage-bit handling strategy explicitly.
• Encode the compact register-reuse policy explicitly.
• Verify that the current LegendreAccumulatorBloq is replaced or wrapped by a paper-faithful reversible subroutine.

Section 5.1: windowing

• Encode the exact windowed decomposition used in the paper.
• Record the paper's concrete window size used in Section 6 estimates:
  • window size = 16
• Separate this paper-specified windowing from our exploratory w4/w5/w6 search knobs.

Section 5.2 / 5.4: binary tree and spooky pebbling

• Encode the binary-tree structure on window outputs explicitly.
• Encode the root specialization that computes [XZ]_p.
• Encode the spooky-pebbling step logic explicitly, not only its asymptotic or aggregate effect.
• Verify node / phase / inverse-node counts against Table 3 where relevant.

Section 6: concrete estimate reconciliation

• Reconcile the abstract 1098 headline against detailed Table 8.
• Build an explicit repo profile for the detailed P-256 -> 1193 row.
• Decide which row is the correct external comparator for secp256k1 claims.
• Keep all external statements consistent with that decision.