Validation of Quantum Elliptic Curve Point Addition Circuits

Francis P. Papa

REVIEW 3 major objections 6 minor 6 references

Validation of Quantum Elliptic Curve Point Addition Circuits

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper reports four places where a leading quantum elliptic-curve point-addition circuit leaves ancilla qubits dirty, and gives fixes that keep the leading-order gate cost unchanged.

desk verdict A useful, credible bug-report on Litinski's ECC point-addition circuit with concrete fixes and public code, but the 'works in all situations' claim is one convention too strong. read the letter →

arxiv 2506.03318 v2 pith:5FXTC6ZY submitted 2025-06-03 quant-ph

Francis P. Papa This is my paper

classification quant-ph MSC 81P6894A60 PACS 03.67.Lx

keywords ellipticcurvecryptographyquantumcircuitspointadditionancillauncomputationToffoligatecountclassicalsimulationcircuitvalidationMontgomeryarithmetic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that a published six-step quantum circuit for elliptic-curve point addition, advertised as exact and ancilla-clean, is not clean in four corner cases. The author shows that in steps 2, 5, and 6 the circuit diagram promises ancilla qubits return to the $|0\rangle$ state, but the intermediate values are not always uncomputed, which can cause decoherence in larger computations. By classical simulation and unit testing, the paper isolates each failure, proves when it occurs, and presents corrected circuits. The fixes add $18n-5$ Toffoli gates and one ancilla qubit while leaving the leading-order cost at $126n^2$ Toffoli gates. If correct, the corrected circuit is exact for all inputs and all ancillas are properly restored.

What carries the argument

The central object is the six-step reversible elliptic-curve point-addition circuit from Ref. [2], expressed as a hierarchy of quantum subroutines called Bloqs, each with explicit input and output registers, a classical emulation method, and an exact gate inventory. The validation machinery is classical simulation: unit tests pipe concrete computational-basis states through each Bloq and fail whenever a qubit allocated in $|0\rangle$ is freed in a different state. Montgomery-form modular arithmetic is the reference representation for the integer operations. The repairs are built from controlled equality gates and multi-controlled Toffoli gates that detect the rare input patterns and flip the offending flag qubits back to $|0\rangle$.

What would settle it

Take the published six-step schematic and apply its own input-to-output rules to the four edge cases identified in the paper: point doubling where the computed slope equals the doubling slope, point doubling where $a-x_r=0$, and the two zero-coordinate combinations in step 6. Run each case through a state-vector or classical simulator and check, qubit by qubit, whether the original circuit already returns every marked ancilla to $|0\rangle$ under its intended ancilla convention. If any of these cases already clears correctly in the original, the claimed inconsistencies do not exist.

Watch

Extended reading notes

Core claim

The central claim is that the six-step elliptic-curve point-addition circuit described in Ref. [2] leaves ancilla qubits in non-$|0\rangle$ states in four rare cases that the schematic does not handle. In step 2, the flag $|f_1\rangle$ is not cleared when the computed slope equals the doubling slope, $\lambda=\lambda_r$. In step 5, the register $|\lambda\rangle$ cannot be uncomputed by the modular inverse of $a-x_r$ when $a=x_r$, a case the paper proves occurs only during point doubling. In step 6 there are two failures: $|f_1\rangle$ or $|f_2\rangle$ can remain set for certain zero-coordinate inputs, and $|f_4\rangle$ can be cleared incorrectly when the result is the origin during point doubling. The paper supplies corrected circuits: a controlled equality check with one extra ancilla for step 2, a $2n$-controlled Toffoli gate for step 5, and four $3n$-controlled Toffoli gates plus a reordering of two existing gates for step 6. After the fixes, the circuit is claimed to be exact for all inputs with all ancillas returned to $|0\rangle$, at leading-order cost $126n^2$ Toffoli gates and total overhead $18n-5$ gates.

Load-bearing premise

The entire report rests on the assumption that the classical simulation faithfully transcribes the published circuit diagrams and that those diagrams really promise every ancilla shown exiting in the $|0\rangle$ state; if the original allows dirty ancillas or uses a different uncomputation convention, the reported inconsistencies are artifacts of the transcription, not bugs in the published circuit.

Editorial extensions

If this is right

The corrected circuit, if accepted, is exact for all points on the curve, including point doubling and the zero-coordinate edge cases the original schematic mishandled.
All ancilla qubits return to $|0\rangle$, so the circuit can be used as a clean reversible subroutine inside quantum phase estimation without garbage-induced decoherence.
The leading-order Toffoli count remains $126n^2$, so published asymptotic resource estimates for elliptic-curve discrete logarithms stand, with only a constant-factor correction of $18n-5$ gates and one extra ancilla qubit.
The step-5 proof that $a-x_r=0$ occurs only during point doubling gives a reusable lemma for simplifying or verifying other elliptic-curve point-addition constructions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the transcription faithfully represents how the published schematic is usually read, downstream work that reused the flagged gate layout may inherit the uncleaned-ancilla issue; rechecking those resource claims would be a natural follow-up.
The same classical-simulation discipline could be applied to other arithmetic-heavy quantum circuits whose diagrams promise clean ancillas, such as modular exponentiation for factoring or lattice-arithmetic subroutines, where leftover garbage can also break phase estimation.
Because the overhead is $18n-5$ gates, the fixes are negligible for cryptographically large $n$; for small curves or near-term test chips the relative cost increase is larger and should be included in cost modeling.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper does something genuinely useful: it takes Litinski's six-step elliptic curve point addition circuit, transcribes it into Qualtran, and finds four specific places where ancillas are not actually returned to |0>. For each it proposes a concrete fix, the leading-order Toffoli count stays at 126n^2, and the total overhead is only 18n-5. That is a real correction to a circuit people use for resource estimates, and I don't know of a prior publication that catches these cases. The step-5 proof that a-xr=0 only happens during point doubling is a genuine derivation, and the public code plus Classical simulation tests give the work a reproducible backbone. Credit where due: this is more than a parameter scan.

The soft spots are real but not fatal. The biggest one, which the stress-test note pins down correctly, is the step-5 fix. The paper's own text says the cleanup works because in this particular ModInv implementation, ModInv(|0>)=|0>. But the added controlled-XOR of lambda_r only restores the register to zero under that convention. A reversible modular inverse that maps 0 to some nonzero field element leaves the register in a nonzero state, and the fix does not clear it. So the headline 'works in all situations' is not established for the schematic in general; it is established for one concrete instantiation. The paper does flag the dependence, but the conclusion overstates it. That is the main reason I would not call this a full validation of Litinski's circuit as such.

The other issues are minor. The empirical check is 12 points on one small curve, and the exact test set is not enumerated. There's no commit hash for the code, so reproducibility is slightly weaker than it should be. The assumption that the Qualtran transcription faithfully represents Litinski's intent is reasonable but unstated; if the original figures allowed dirty ancillas, some of these inconsistencies would be transcription artifacts. None of this undermines the core finding that this particular transcription had clear bugs.

Who is this for? Anyone doing quantum ECC resource estimation who relies on Litinski's numbers should read it. It deserves a serious referee, and with a modest revision that scopes the universality claim to the chosen ModInv convention and pins down the test set, it would be a solid contribution. Send it to review.

Referee Report

3 major / 6 minor

Summary. The paper describes a Qualtran-based classical simulation and unit-testing validation of Litinski's six-step quantum elliptic curve point addition circuit. It reports four edge cases, in steps 2, 5, and 6 of the circuit, in which ancilla qubits shown as returning to |0> are not actually uncomputed, and it proposes circuit modifications that clear those qubits. The author gives updated Toffoli counts, claiming an unchanged leading-order cost of 126n^2 Toffoli gates and an added overhead of 18n-5 Toffoli gates, and the corrected circuits are available in the Qualtran repository.

Significance. If the claims are correct and convention-independent, the paper provides a valuable correction to a widely used resource estimate for elliptic curve point addition, with publicly available, machine-checkable code and explicit gate counts. The step-5 proof is a genuine attempt at a derivation, and the reported edge cases are concrete. The central weakness is that the 'exact for all inputs' claim depends on a modular-inverse convention that is stated only inside the proof, and the empirical validation is based on a small sample of points. With those issues fixed, this would be a useful research note for the quantum resource-estimation community.

major comments (3)

[III.B and IV] The step-5 fix is contingent on the modular-inverse convention ModInv(0)=0. The paper explicitly says, 'This leaves |lambda> in some nonzero state depending on your implementation of ModInv(|0>) (in this case ModInv(|0>)=|0> so the register is unchanged),' yet the abstract and conclusion state that the corrected circuit is exact and 'works in all situations.' If Litinski's original figures assume a different reversible modular-inverse implementation, the four reported inconsistencies are transcription artifacts rather than universal corrections of Ref. [2]. The manuscript should either state that the corrected circuit is exact only under the Qualtran convention and adjust the headline claim, or provide a fix that does not depend on this convention.
[III.B, proof] The proof that a-xr=0 arises only during point doubling uses the slope formula lambda=(y-b)/(x-a), which is undefined when x-a=0. The subsequent algebra to (x-a)^2(x+2a)=(y-b)^2 does not license the conclusion y=b because lambda was never defined. The edge case P2=-P1 (same x-coordinate, opposite y) is not explicitly handled. As written, the proof does not exclude a class of inputs for which the step-5 fix might fail, so the load-bearing step of the argument needs repair or a separate case analysis.
[II.B and IV] The conclusion states that the corrected circuit 'works in all situations,' but the empirical evidence in Section II.B is a unit test on 12 points from a single curve (p1707). No exhaustive simulation over a finite field or formal correctness argument for arbitrary n-bit inputs is presented. Since the paper's title and abstract assert validation and exactness, the authors should either provide exhaustive or symbolic verification for at least a small curve, or qualify the claim to 'validated on the tested inputs and the analyzed edge cases.' This is directly relevant to the central claim.

minor comments (6)

[Abstract] The phrase 'to-in theory-break' appears to be a formatting typo; it should read 'to—in theory—break' or similar.
[III.B] The inline fraction notation such as 'lambda = y - b / x - a' is ambiguous; please use parentheses or rac to clarify the numerator and denominator.
[III.C] The sentence 'This change can be see in Fig. 3' contains a typo and should read 'can be seen in Fig. 3.'
[III.D, Table I] The Toffoli counts for modular multiplication and modular inverse are listed as 2.25n^2 + 7.25n - 1 and 26n^2 + 9n - 1, but the text says 'I include constant factors.' It would be clearer to state explicitly that these are exact counts from the Qualtran implementations, not just leading-order expressions.
[III.A and III.D] The step-2 fix description says an additional Equals gate and a controlled Equals gate raise the Toffoli count by a factor of 4n; a sentence explaining how the two gates and the control contribute exactly 4n would help.
[V] The repository links point to pull requests but not to specific commits; pinning exact commit hashes would improve reproducibility of the reported validation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the validation is anchored to Litinski's external circuit and classical point arithmetic; the ModInv(0)=0 dependence is disclosed, not loaded circularly.

full rationale

The paper does not fit any parameter to its target claim or derive its conclusion from a self-authored uniqueness theorem. The central object under test is Litinski's published circuit (Ref. [2]) and classical elliptic-curve arithmetic. The Qualtran implementation is the instrument, not the benchmark; unit tests compare classical simulation against ordinary modular arithmetic reference values. The only dependence that could threaten universality is the modular-inverse convention in step 5, but the paper explicitly flags it: 'in this case ModInv(|0⟩)=|0⟩ so the register is unchanged.' That is an exposed assumption about the subroutine, not a conclusion defined in terms of itself. The proposed fixes are justified by direct circuit reasoning and the attached proof that a−xr=0 forces point doubling. Refs. [2] and [5] are external references; Ref. [3] is tooling used for simulation and cost bookkeeping, not a load-bearing theorem. No step reduces by construction to its own input, no fitted value is renamed a prediction, and no self-citation chain forces the result. The step-5 fix is conditional on a stated convention, but the paper acknowledges that contingency rather than hiding it, so this is a correctness caveat, not circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities are introduced. The central claim rests on the fidelity of the Litinski circuit transcription, the correctness of Qualtran's low-level arithmetic Bloqs, the particular modular-inverse convention, and the representativeness of the test set; these are listed as axioms below.

assumptions (5)

domain assumption The Qualtran transcription of Litinski's circuit figures is faithful to the intended operation.
All four purported inconsistencies are defined relative to the six-step circuit in Ref. [2]; if the original figures are read with different ancilla-clearing conventions, the reported failures would be transcription artifacts. Invoked throughout Methodology Section II and Results Section III.
domain assumption The low-level arithmetic Bloqs in Qualtran (ModAdd, ModSub, ModMult, ModInv, Equals) implement the stated modular operations correctly.
Classical simulation tests propagate correctness hierarchically by assuming low-level Bloqs are correct (Methodology II.B), so errors in those primitives would invalidate the validation.
ad hoc to paper In the Qualtran implementation, modular inverse of zero returns zero, leaving the lambda register unchanged.
The step-5 analysis explicitly relies on ModInv(|0>) = |0>; a different convention would change the diagnosis and the fix. Stated in Section III.B.
domain assumption The p1707 curve and the chosen 12 test points are representative of all branch conditions in the circuit.
The paper uses a subset of points from one small curve (Methodology II.B) as the empirical basis for claiming the corrected circuit works in all situations.
standard math The elliptic curve addition formulas in Eq. (2) of Ref. [2] are correct.
The step-5 proof and overall point addition logic depend on the lambda formula from Ref. [2].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Validation of Quantum Elliptic Curve Point Addition Circuits." pith.science (2026). https://pith.science/paper/5FXTC6ZY

@misc{pith2026250603318,
  author       = {Pith},
  title        = {Pith review of: Validation of Quantum Elliptic Curve Point Addition Circuits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5FXTC6ZY}},
  note         = {Machine review of arXiv:2506.03318}
}

abstract

Specific quantum algorithms exist to-in theory-break elliptic curve cryptographic protocols. Implementing these algorithms requires designing quantum circuits that perform elliptic curve arithmetic. To accurately judge a cryptographic protocol's resistance against future quantum computers, researchers figure out minimal resource-count circuits for performing these operations while still being correct. To assure the correctness of a circuit, it is integral to restore all ancilla qubits used to their original states. Failure to do so could result in decoherence of the computation's final result. Through rigorous classical simulation and unit testing, I surfaced four inconsistencies in the state-of-the-art quantum circuit for elliptic curve point addition where the circuit diagram states the qubits are returned in the original ($|0\rangle$) state, but the intermediate values are not uncomputed. I provide fixes to the circuit without increasing the leading-order gate cost.

Figures

Figures reproduced from arXiv: 2506.03318 by the authors.

**Figure 1.** Corrected circuit for step 2 of the elliptic curve point addition circuit; the changed part is highlighted in blue. In place of a single Equals gate, two [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 2.** Corrected circuit for step 5 of the elliptic curve point addition circuit; the changed part is highlighted in blue. A [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Corrected circuit for step 6 of the elliptic curve point addition circuit. The first fix involves 4 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[2]

How to compute a 256-bit elliptic curve private key with only 50 million toffoli gates, 2023

Daniel Litinski. How to compute a 256-bit elliptic curve private key with only 50 million toffoli gates, 2023

work page 2023
[1]

Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

Peter W Shor et al. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. los alamos physics preprint archive, 1995

work page 1995
[3]

Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D

Matthew P. Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D. Malone, Ryan Babbush, and Nicholas C. Rubin. Expressing and analyzing quantum algorithms with qualtran, 2024

work page 2024
[4]

Modular multiplication without trial division

Peter L Montgomery. Modular multiplication without trial division. Math. Comput., 44(170):519–521, 1985

work page 1985
[5]

Performance analysis of a repetition cat code architecture: Computing 256-bit elliptic curve logarithm in 9 hours with 126133 cat qubits

´Elie Gouzien, Diego Ruiz, Francois-Marie Le R ´egent, J ´er´emie Guillaud, and Nicolas Sangouard. Performance analysis of a repetition cat code architecture: Computing 256-bit elliptic curve logarithm in 9 hours with 126133 cat qubits. Physical Review Letters , 131(4), July 2023

work page 2023
[6]

Practical cryptography for developers: Elliptic curve cryptography (ecc)

Svetlin Nakov. Practical cryptography for developers: Elliptic curve cryptography (ecc). https://github.com/nakov/ Practical-Cryptography-for-Developers-Book/blob/master/ asymmetric-key-ciphers/elliptic-curve-cryptography-ecc.md, 2018

work page 2018

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [2]

How to compute a 256-bit elliptic curve private key with only 50 million toffoli gates, 2023

Daniel Litinski. How to compute a 256-bit elliptic curve private key with only 50 million toffoli gates, 2023

work page 2023

[2] [1]

Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

Peter W Shor et al. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. los alamos physics preprint archive, 1995

work page 1995

[3] [3]

Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D

Matthew P. Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D. Malone, Ryan Babbush, and Nicholas C. Rubin. Expressing and analyzing quantum algorithms with qualtran, 2024

work page 2024

[4] [4]

Modular multiplication without trial division

Peter L Montgomery. Modular multiplication without trial division. Math. Comput., 44(170):519–521, 1985

work page 1985

[5] [5]

Performance analysis of a repetition cat code architecture: Computing 256-bit elliptic curve logarithm in 9 hours with 126133 cat qubits

´Elie Gouzien, Diego Ruiz, Francois-Marie Le R ´egent, J ´er´emie Guillaud, and Nicolas Sangouard. Performance analysis of a repetition cat code architecture: Computing 256-bit elliptic curve logarithm in 9 hours with 126133 cat qubits. Physical Review Letters , 131(4), July 2023

work page 2023

[6] [6]

Practical cryptography for developers: Elliptic curve cryptography (ecc)

Svetlin Nakov. Practical cryptography for developers: Elliptic curve cryptography (ecc). https://github.com/nakov/ Practical-Cryptography-for-Developers-Book/blob/master/ asymmetric-key-ciphers/elliptic-curve-cryptography-ecc.md, 2018

work page 2018