Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

This paper presents a detailed quantum logical circuit architecture for optimized point addition on elliptic curves over prime fields, achieving a 6.5% to 10% reduction in Toffoli gate counts for secp256k1 compared to Babbush et al.'s zero-knowledge-proof-based results, while incurring only a marginal 1.5% increase in qubit usage.

The Gist

Imagine you are trying to crack a very complex lock. For decades, mathematicians have known that a special kind of "super-key" (a quantum computer) could open this lock almost instantly, breaking the security of most of the internet's encryption. This is known as Shor's Algorithm.

However, building this super-key is incredibly expensive and difficult. It requires a massive amount of "magic energy" (quantum resources) to work. The goal of this paper is to figure out how to build a smaller, more efficient version of that key.

Here is the breakdown of what the author, André Schrottenloher, achieved, explained through everyday analogies.

1. The Big Problem: The Heavy Backpack

Think of running Shor's algorithm like hiking up a mountain. To get to the top (cracking the code), you need to carry a heavy backpack full of supplies (quantum bits, or "qubits").

• Previous attempts: Other researchers recently built a very efficient backpack that was lighter than ever before. However, they kept the blueprints secret, using a "magic trick" (a zero-knowledge proof) to convince everyone the backpack was light without showing them how it was made.
• This paper's goal: The author wanted to build a backpack that is just as light as the secret one, but with the blueprints fully open so anyone can check the work.

2. The Core Task: Adding Points on a Curve

The main job of the algorithm is to perform a specific math operation called "point addition" on an elliptic curve.

• The Analogy: Imagine you are walking on a giant, curved trampoline. You need to jump from one spot to another based on a set of rules. Doing this jump perfectly is hard.
• The Bottleneck: The hardest part of the jump is a specific move called "in-place multiplication." It's like trying to multiply two numbers together while you are only allowed to use the space you are currently standing on, without any extra room to write down scratch paper.

3. The Solution: The "Two-Step Dance"

To solve the "no scratch paper" problem, the author used a clever two-step strategy (based on a method called the Extended Euclidean Algorithm):

• Step 1: The Memory Tape (Recording the Moves)
  Instead of doing the math and keeping the result, the computer first just records what moves it would have made on a long tape of bits. It doesn't actually do the heavy lifting yet; it just writes down the instructions. This tape is surprisingly short.
• Step 2: The Reconstruction (Playing Back the Moves)
  Once the tape is written, the computer plays it back in reverse. It uses the instructions on the tape to perform the actual math on the numbers.
• Why this helps: By separating the "planning" from the "doing," the computer saves a massive amount of space. It's like writing a recipe on a sticky note before you start cooking, so you don't have to hold all the ingredients in your hands at once.

4. The Shortcut: The "Pseudo-Mersenne" Prime

The paper focuses on a specific type of lock called secp256k1 (used by Bitcoin). This lock has a special shape.

• The Analogy: Imagine a generic lock is a perfect square. But the Bitcoin lock is a square with one tiny corner cut off.
• The Optimization: Because the corner is cut off, the math required to open it is slightly easier. The author designed special tools that take advantage of this "cut corner" to skip unnecessary steps.
  • For a generic lock (any prime number), the tools are standard and slightly heavier.
  • For the Bitcoin lock (secp256k1), the tools are streamlined and lighter because they know exactly where the corner is missing.

5. The Results: A Slightly Lighter Backpack

The author built the full "blueprint" for this new backpack and tested it.

• Space (Qubits): The new backpack is about 1.5% heavier than the secret one from the other researchers. It's a tiny trade-off.
• Energy (Gates): However, the new backpack is 6.5% to 10% more efficient in terms of the energy (Toffoli gates) needed to run it.
• Reliability: The author proved that this backpack works just as reliably as the secret one. If you try to use it on random inputs, it succeeds almost every time, just like the secret version.

Summary

In simple terms, this paper says: "We figured out how to build the quantum computer needed to crack modern encryption. We didn't just guess; we wrote down the exact instructions. Our version is slightly bigger in size but uses less energy to run than the previous 'secret' version, and we proved it works for both generic locks and the specific lock used by Bitcoin."

The author emphasizes that this is a logical design (the theoretical blueprint). It doesn't mean we can build it today, but it tells us exactly how much "magic energy" we will need when quantum computers finally become powerful enough to try.

Technical Summary

Problem Statement
The paper addresses the resource estimation of Shor's algorithm for computing elliptic curve discrete logarithms (ECDL), a primary threat to current public-key cryptography. While recent works by Babbush et al. (arXiv 2026) demonstrated significant reductions in gate and qubit counts for the curve secp256k1, they relied on a zero-knowledge proof to validate their results without revealing the underlying logical quantum circuits. This lack of transparency hinders reproducibility and independent verification. The paper aims to provide a fully detailed, reproducible logical quantum circuit architecture that achieves comparable efficiency to Babbush et al. while explicitly revealing the design principles and implementation details.

Methodology
The authors employ a top-down approach, starting from the high-level structure of Shor's algorithm and refining the arithmetic components. The core of the optimization lies in the implementation of windowed point addition on elliptic curves over prime fields.

1. High-Level Structure: The algorithm utilizes a semiclassical Fourier transform with qubit recycling to reduce the point multiplication $|u, v\rangle|0\rangle \to |u, v\rangle|[u]P + [v]Q\rangle$ to a sequence of windowed point additions. Points are represented in affine coordinates.
2. Modular In-Place Multiplication: The most costly operation in point addition is in-place modular multiplication $|x, y\rangle \to |x, yx \pmod q|$. The authors adapt a technique from [14] that decouples the Extended Euclidean Algorithm (EEA) into two distinct phases:
   • Euclidean Algorithm (Forward): Instead of computing Bézout coefficients directly, this phase processes inputs $(q, x)$ and outputs a "garbage" bit-vector encoding the sequence of operations (swaps, subtractions, divisions by 2). This reduces space complexity.
   • Bézout Reconstruction (Backward): This phase takes the garbage bit-vector and applies the recorded operations to a pair $(y, 0)$ to compute $|y, yx^{-1} \pmod q\rangle$. By running this in reverse or with specific inputs, the authors achieve in-place multiplication and inversion simultaneously.
3. Arithmetic Optimization:
   • Space vs. Gate Trade-offs: The authors strategically switch between the CDKM adder (low space) and the Gidney adder (low gate count, higher space) depending on the availability of ancilla qubits during different stages of the algorithm.
   • Approximate Arithmetic: To reduce gate counts, the authors introduce approximate arithmetic circuits. Comparisons are performed using only the most significant bits (MSBs) rather than full-width comparisons. This introduces a failure probability, which is managed by optimizing constants to ensure success on random inputs with high probability (specifically, failure probability $\le 2^{-13.3}$).
   • Instance-Specific Optimization: For the secp256k1 curve, which uses a pseudo-Mersenne prime ($q = 2^{256} - 4294968273$), the modular reduction circuits are further simplified. The authors exploit the small difference $f$ in the form $2^u - f$ to replace expensive modular subtractions with simple bit manipulations and additions of $f$.

Key Contributions

• Reproducible Circuit Architecture: The paper details the first fully specified logical quantum circuit for ECDL on secp256k1 that matches the efficiency claims of the opaque Babbush et al. work. The code is implemented and available via the Qarton library.
• Optimized Resource Counts: The authors present two variants of the circuit:
  • Space-optimized: Uses approximately $4.36n + O(\sqrt{n})$ qubits.
  • Gate-optimized: Uses approximately $4.36n + O(\sqrt{n})$ qubits but reduces the Toffoli gate count.
• Generic Variant: A version of the circuit is provided that is valid for any prime field, not just secp256k1, though it incurs a slightly higher gate cost due to the lack of pseudo-Mersenne optimizations.
• Detailed Cost Analysis: The paper provides a granular breakdown of Toffoli gate costs, distinguishing between the GCD construction, Bézout reconstruction, and modular arithmetic components.

Results
The authors report the following resource estimates for the curve secp256k1 (where $n=256$):

• Qubit Count:
  • Space-optimized variant: 1,192 qubits (compared to 1,175 in Babbush et al.).
  • Gate-optimized variant: 1,446 qubits (compared to 1,425 in Babbush et al.).
  • This represents a slight increase of approximately 1.5% in qubit count.
• Gate Count (Toffolis):
  • Space-optimized variant: $2^{21.19}$ (approx. $2.3 \times 10^6$).
  • Gate-optimized variant: $2^{20.83}$ (approx. $1.8 \times 10^6$).
  • This represents a reduction of 6.5% to 10% in Toffoli gate count compared to Babbush et al.
• Full Algorithm Cost: For the complete Shor's algorithm on secp256k1, the gate-optimized variant requires approximately $2^{25.78}$ Toffoli gates and 1,462 qubits. This is a significant improvement over previous work by Litinski (arXiv 2023), which required roughly $2^{27.57}$ Toffoli gates and twice the number of qubits.

Significance
The paper claims significance primarily in the realm of reproducibility and transparency. By providing the explicit logical circuit architecture, the authors allow the cryptographic community to verify the resource estimates for breaking elliptic curve cryptography, which were previously hidden behind a zero-knowledge proof. The work demonstrates that similar or slightly improved efficiency can be achieved through explicit design choices, specifically the separation of the EEA into a recording phase and a reconstruction phase, combined with approximate arithmetic. The authors note that their circuits are not exact and rely on a high probability of success on random inputs, a property shared with the work they replicate. The results confirm that the cost of breaking secp256k1 is lower than previously estimated by some logical circuit models, reinforcing the urgency of post-quantum migration.