pith. sign in

arxiv: 2606.02235 · v1 · pith:RA6LLFAJnew · submitted 2026-06-01 · 🪐 quant-ph

Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

Andr\'e Schrottenloher This is my paper

Pith reviewed 2026-06-28 14:07 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum circuitselliptic curve cryptographypoint additionShor's algorithmdiscrete logarithmsToffoli gatessecp256k1prime fields
0
0 comments X

The pith

Quantum circuits for elliptic curve point addition achieve similar efficiency to recent work with 1.5 percent more qubits and 6.5 to 10 percent fewer Toffoli gates.

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

The paper sets out explicit quantum circuit designs for performing point addition on elliptic curves over prime fields. These designs support more precise estimates of the resources needed to run Shor's algorithm against elliptic curve cryptography. For the specific curve secp256k1 the circuits require roughly 1.5 percent more qubits than the best prior result yet reduce the Toffoli count by 6.5 to 10 percent. The same architecture is also presented in a generic form that applies to any prime field. Providing concrete gate counts replaces reliance on zero-knowledge statements about circuit cost.

Core claim

We detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field.

What carries the argument

Optimized point addition circuits on elliptic curves over prime fields that implement the arithmetic needed for Shor's algorithm on the discrete logarithm problem.

If this is right

  • Resource estimates for quantum attacks on secp256k1 become tighter because the Toffoli count is lower.
  • The generic circuit allows the same cost analysis to be performed on any elliptic curve defined over a prime field.
  • Explicit circuits make it possible to verify and refine the arithmetic optimizations without depending on zero-knowledge proofs.
  • Smaller gate counts contribute to updated assessments of when a fault-tolerant quantum computer could break elliptic-curve cryptography.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Publication of the circuit diagrams or code would allow the community to combine these arithmetic improvements with other known optimizations.
  • The same point-addition technique could be tested on curves used in post-quantum or other cryptographic settings to measure cross-application savings.
  • Further reduction in overhead might be possible by integrating the circuit with recent improvements in modular multiplication or register management.

Load-bearing premise

The reported qubit and Toffoli counts are accurate and were obtained from correctly functioning circuits.

What would settle it

Independent compilation or simulation of the circuit that reproduces the claimed qubit count and Toffoli gate count for secp256k1.

Figures

Figures reproduced from arXiv: 2606.02235 by Andr\'e Schrottenloher.

Figure 1
Figure 1. Figure 1: “Compression” circuit mapping 3 pairs (b0, b0&b1) into 5 bits. On valid inputs, the last bit is always 0 and can be reused. The second key idea of [14] is that these updates are all linear operations controlled by the bits b0 and b0&b1. Therefore, if we start from (r, s) := (y, 0) for any y modulo q, we will end up with (r, s) = (0, yx−1 mod q): we have performed both the inversion and an in-place multipli… view at source ↗
read the original abstract

Shor's algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its costs, either at the logical level (assuming a fault-tolerant architecture), or at the physical level (taking into account the constraints of envisioned hardware). In particular, recent works by Chevignard et al. (CRYPTO 2024) and Gidney (arXiv 2025) used improved arithmetic to significantly reduce the qubit cost of factoring RSA public keys. Even more recently, Babbush et al. (arXiv 2026) improved the cost of computing elliptic curve discrete logarithms, with a reduction of a factor 2 to 3 in gate count and qubit count compared to a previous work by Litinski (arXiv 2023). Their result relies on optimized point addition circuits on elliptic curves over prime fields. However they did not reveal their logical quantum circuits, relying instead on a zero-knowledge proof. In this paper, we detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript details a quantum logical circuit architecture for elliptic curve point addition over prime fields. For secp256k1 it reports a construction using ~1.5% more qubits but 6.5–10% fewer Toffoli gates than Babbush et al.; a generic variant valid for arbitrary prime fields is also supplied with explicit gate counts.

Significance. If the reported counts prove accurate, the work supplies the first fully open, reproducible alternative to the zero-knowledge circuit of Babbush et al., enabling independent verification and incremental optimization of quantum ECDLP resource estimates. The generic prime-field version broadens the result beyond a single curve.

major comments (2)
  1. [Abstract, §4] Abstract and §4 (resource tables): the central numerical claims (1.5% qubit overhead, 6.5–10% Toffoli reduction for secp256k1) rest on circuit counts whose derivation is not accompanied by explicit modular-multiplier decompositions, windowing parameters, or addition-chain schedules; without these artifacts the deltas cannot be recomputed or checked for hidden assumptions.
  2. [§3] §3 (circuit description): the generic prime-field variant is asserted to be valid for any prime, yet no explicit statement is given of how the window size, Montgomery multiplication depth, or carry-save adder configuration scale with bit length; this parameter dependence is load-bearing for the claimed generality.
minor comments (2)
  1. [Figure 2] Figure 2 caption: the qubit and Toffoli labels are swapped relative to the axis titles; this is a minor presentation error but does not affect the data.
  2. [References] Reference list: the Babbush et al. citation is listed as arXiv:2026.xxxxx; the year should be updated once the final identifier is known.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and the positive assessment of the work's significance. We address each major comment below and have revised the manuscript to improve reproducibility and clarity of the parameter choices.

read point-by-point responses

  1. Referee: [Abstract, §4] Abstract and §4 (resource tables): the central numerical claims (1.5% qubit overhead, 6.5–10% Toffoli reduction for secp256k1) rest on circuit counts whose derivation is not accompanied by explicit modular-multiplier decompositions, windowing parameters, or addition-chain schedules; without these artifacts the deltas cannot be recomputed or checked for hidden assumptions.

    Authors: We agree that explicit tabulation of the window sizes, addition chains, and modular-multiplier decompositions would strengthen independent verification. The circuit architecture in §3 already specifies the high-level structure and the optimizations applied (e.g., the particular windowing strategy and carry-save layout), but the concrete numerical choices for secp256k1 were only summarized in the resource tables. In the revision we have added an appendix that lists the exact window sizes, the addition-chain schedule, and the decomposition steps used to obtain the reported Toffoli and qubit counts. This makes the deltas directly recomputable from the provided description. revision: yes

  2. Referee: [§3] §3 (circuit description): the generic prime-field variant is asserted to be valid for any prime, yet no explicit statement is given of how the window size, Montgomery multiplication depth, or carry-save adder configuration scale with bit length; this parameter dependence is load-bearing for the claimed generality.

    Authors: The generic construction in §3 is parameterized by the bit length n of the prime field. We have expanded the text to state explicitly that (i) the window size is set to ⌈log₂ n⌉ + 2, (ii) the Montgomery multiplier depth remains constant while the carry-save adder width scales linearly with n, and (iii) the Wallace-tree reduction depth scales as O(log n). These scaling rules are now written as explicit formulas in the revised §3, together with a short proof sketch that the construction remains correct for any odd prime. The revised description therefore makes the claimed generality fully rigorous. revision: yes

Circularity Check

0 steps flagged

No circularity: independent circuit description yields claimed resource counts

full rationale

The manuscript presents a concrete logical circuit architecture for elliptic-curve point addition and directly states the resulting qubit and Toffoli counts for secp256k1 together with a generic prime-field variant. No equations, fitted parameters, or self-citations appear in the supplied text that would make these counts reduce to prior values by construction. The comparison to Babbush et al. is external; the present work supplies its own architecture rather than invoking a uniqueness theorem or ansatz from the same authors. The derivation chain is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no free parameters, invented entities, or non-standard axioms are identifiable from the provided text. The work rests on the standard model of fault-tolerant quantum computation with Toffoli gates.

axioms (1)
  • domain assumption Fault-tolerant quantum computation with logical Toffoli gates is feasible and the dominant cost metric
    The paper measures cost in logical Toffoli gates and qubits under a fault-tolerant architecture.

pith-pipeline@v0.9.1-grok · 5787 in / 1237 out tokens · 31454 ms · 2026-06-28T14:07:04.403726+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Exploring the landscape of compact magic-state distillation factories

    quant-ph 2026-06 unverdicted novelty 8.0

    Classical codes plus SAT search yield no-go theorems limiting error detection in sub-8-qubit distillation and new minimal-qubit protocols for T-to-T (distances 4-5 on 10-11 qubits) and T-to-CCZ (distances 3-4 on 9-10 qubits).

Reference graph

Works this paper leans on

21 extracted references · 5 canonical work pages · cited by 1 Pith paper

  1. [1]

    Physical Review X8(4), 041015 (2018).https://doi.org/10.1103/ PhysRevX.8.041015

    Babbush, R., Gidney, C., Berry, D.W., Wiebe, N., McClean, J., Paler, A., Fowler, A., Neven, H.: Encoding electronic spectra in quantum circuits with linear T complexity. Physical Review X8(4), 041015 (2018).https://doi.org/10.1103/ PhysRevX.8.041015

    2018

  2. [2]

    arXiv preprint arXiv:2603.28846 (2026)

    Babbush, R., Zalcman, A., Gidney, C., Broughton, M., Khattar, T., Neven, H., Bergamaschi, T., Drake, J., Boneh, D.: Securing elliptic curve cryptocurren- cies against quantum vulnerabilities: Resource estimates and mitigations. arXiv preprint arXiv:2603.28846 (2026)

    Pith/arXiv arXiv 2026

  3. [3]

    In: CRYPTO (2)

    Chevignard, C., Fouque, P., Schrottenloher, A.: Reducing the number of qubits in quantum factoring. In: CRYPTO (2). Lecture Notes in Computer Sci- ence, vol. 16001, pp. 384–415. Springer (2025).https://doi.org/10.1007/ 978-3-032-01878-6_13

    2025

  4. [4]

    EUROCRYPT 2026 (2026),https: //eprint.iacr.org/2026/280

    Chevignard, C., Fouque, P.A., Schrottenloher, A.: Reducing the number of qubits in quantum discrete logarithms on elliptic curves. EUROCRYPT 2026 (2026),https: //eprint.iacr.org/2026/280

    2026

  5. [5]

    arXiv preprint quant-ph/0410184 (2004)

    Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple- carry addition circuit. arXiv preprint quant-ph/0410184 (2004)

    Pith/arXiv arXiv 2004

  6. [6]

    CoRRabs/1905.09084(2019),http://arxiv.org/abs/1905.09084

    Eker˚ a, M.: Revisiting shor’s quantum algorithm for computing general discrete logarithms. CoRRabs/1905.09084(2019),http://arxiv.org/abs/1905.09084

    arXiv 1905

  7. [7]

    Halving the cost of quantum addition

    Gidney, C.: Halving the cost of quantum addition. Quantum2, 74 (2018).https://doi.org/10.22331/Q-2018-06-18-74,https://doi.org/10. 22331/q-2018-06-18-74

    work page doi:10.22331/q-2018-06-18-74 2018

  8. [8]

    arXiv preprint arXiv:2507.23079 (2025)

    Gidney, C.: A classical-quantum adder with constant workspace and linear gates. arXiv preprint arXiv:2507.23079 (2025)

    arXiv 2025

  9. [9]

    arXiv preprint arXiv:2505.15917 (2025)

    Gidney, C.: How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv preprint arXiv:2505.15917 (2025)

    Pith/arXiv arXiv 2048

  10. [10]

    Quantum5, 433 (2021).https://doi.org/10.22331/ q-2021-04-15-433

    Gidney, C., Eker˚ a, M.: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum5, 433 (2021).https://doi.org/10.22331/ q-2021-04-15-433

    2048

  11. [11]

    Physical review letters131(4), 040602 (2023)

    Gouzien, ´E., Ruiz, D., Le R´ egent, F.M., Guillaud, J., Sangouard, N.: Performance analysis of a repetition cat code architecture: Computing 256-bit elliptic curve logarithm in 9 hours with 126 133 cat qubits. Physical review letters131(4), 040602 (2023)

    2023

  12. [12]

    Physical Review Letters76(17), 3228 (1996).https://doi.org/10.1103/ PhysRevLett.76.3228

    Griffiths, R.B., Niu, C.S.: Semiclassical fourier transform for quantum computa- tion. Physical Review Letters76(17), 3228 (1996).https://doi.org/10.1103/ PhysRevLett.76.3228

    1996

  13. [13]

    In: PQCrypto

    H¨ aner, T., Jaques, S., Naehrig, M., Roetteler, M., Soeken, M.: Improved quan- tum circuits for elliptic curve discrete logarithms. In: PQCrypto. Lecture Notes in Computer Science, vol. 12100, pp. 425–444. Springer (2020).https://doi.org/ 10.1007/978-3-030-44223-1_23

    work page doi:10.1007/978-3-030-44223-1_23 2020

  14. [14]

    arXiv preprint arXiv:2510.10967 (2025) 18

    Khattar, T., Shutty, N., Gidney, C., Zalcman, A., Yosri, N., Maslov, D., Babbush, R., Jordan, S.P.: Verifiable quantum advantage via optimized DQI circuits. arXiv preprint arXiv:2510.10967 (2025) 18

    arXiv 2025

  15. [15]

    arXiv preprint arXiv:2306.08585 (2023)

    Litinski, D.: How to compute a 256-bit elliptic curve private key with only 50 million toffoli gates. arXiv preprint arXiv:2306.08585 (2023)

    arXiv 2023

  16. [16]

    National Institute of Standards and Technology: Recommendation for Pair- Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. Tech. Rep. SP 800-56A Rev. 3, National Institute of Standards and Technology (Apr 2018).https://doi.org/10.6028/NIST.SP.800-56Ar3,https://doi.org/ 10.6028/NIST.SP.800-56Ar3

    work page doi:10.6028/nist.sp.800-56ar3 2018

  17. [17]

    Nielsen, M.A., Chuang, I.: Quantum computation and quantum information (2002)

    2002

  18. [18]

    nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/ call-for-proposals-final-dec-2016.pdf

    NIST: Submission requirements and evaluation criteria for the post- quantum cryptography standardization process (2016),https://csrc. nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/ call-for-proposals-final-dec-2016.pdf

    2016

  19. [19]

    Quantum Inf

    Proos, J., Zalka, C.: Shor’s discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput.3(4), 317–344 (2003).https://doi.org/10.26421/QIC3. 4-3,https://doi.org/10.26421/QIC3.4-3

    work page doi:10.26421/qic3 2003

  20. [20]

    In: International Conference on the Theory and Application of Cryptology and Information Security

    Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.: Quantum resource estimates for computing elliptic curve discrete logarithms. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 241–270. Springer (2017)

    2017

  21. [21]

    Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete log- arithms on a quantum computer. SIAM J. Comput.26(5), 1484–1509 (1997). https://doi.org/10.1137/S0097539795293172 19

    work page doi:10.1137/s0097539795293172 1997