Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2503.02984 · IEEE Transactions on Quantum Engineering

Quantum Resource Estimates for Computing Binary Elliptic Curve Discrete Logarithms

Michael Garn, Angus Kan

Published Jan 1, 2025• 2 citations
arXivHTMLPDF

Abstract

We perform logical and physical resource estimation for computing binary elliptic curve discrete logarithms using Shor's algorithm on fault-tolerant quantum computers. We adopt a windowed approach to design our circuit implementation of the algorithm, which comprises repeated applications of elliptic curve point addition operations and table look-ups. Unlike previous work, the point addition operation is implemented exactly, including all exceptional cases. We provide exact logical gate and qubit counts of our algorithm for cryptographically relevant binary field sizes. Furthermore, we estimate the hardware footprint and runtime of our algorithm executed on surface-code matter-based quantum computers with a baseline architecture, where logical qubits have nearest-neighbor connectivity, and on a surface-code photonic fusion-based quantum computer with an active-volume architecture, which enjoys a logarithmic number of non-local connections between logical qubits. At 10% threshold and compared to a baseline device with a$1μ s$code cycle, our algorithm runs$\gtrsim$2-20 times faster, depending on the operating regime of the hardware and over all considered field sizes, on a photonic active-volume device.

DOI
10.1109/tqe.2025.3586541

Related papers

Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms

André Schrottenloher

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.

quant-pharXiv:2606.02235•Jun 2, 2026•0 citations

Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation

Han Luo, Ziyi Yang, Ziruo Wang +2 more

Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses $3n + 4\lfloor \log_2 n \rfloor + O(1)$ logical qubits and $204n^2\log_2 n + O(n^2)$ Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with $5n + 4\lfloor \log_2 n \rfloor + O(1)$ qubits and $O(n^3)$ Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.

quant-pharXiv:2604.02311•Apr 3, 2026•0 citations

Resource analysis and modifications of quantum computing with noisy qubits for elliptic curve discrete logarithms

Jinyoung Ha, Jonghyun Lee, Jun Heo

We estimate the number of physical qubits and execution time by decomposing an implementation of Shor's algorithm for elliptic curve discrete logarithms into universal gate units at the logical level when surface codes are used. We herein also present modified quantum circuits for elliptic curve discrete logarithms and compare our results with those of the original quantum circuit implementations at the physical level. Through the analysis, we show that the use of more logical qubits in quantum algorithms does not always lead to the use of more physical qubits. We assumed using rotated surface code and logical qubits with all-to-all connectivity. The number of physical qubits and execution time are expressed in terms of bit length, physical gate error rate, and probability of algorithm failure. In addition, we compare our results with the number of physical qubits and execution time of Shor's factoring algorithm to assess the risk of attack by quantum computers in RSA and elliptic curve cryptography.

Scientific Reports•Feb 16, 2024•2 citations

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

Han Luo, Ziyi Yang, Jingquan Luo +5 more

The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only $3n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $1056n^3/\log_2 n+O(n^2)$ Toffoli gates, where $n$ is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only $2n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $229n^2+O(n\log_2 n)$ Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.

quant-pharXiv:2607.13816•Jul 16, 2026•0 citations

Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits

Madelyn Cain, Qian Xu, Robbie King +6 more

Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.

quant-pharXiv:2603.28627•Mar 31, 2026•3 citations

Concrete quantum cryptanalysis of binary elliptic curves

Gustavo Banegas, Daniel J. Bernstein, Iggy van Hoof +1 more

This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.

IACR Transactions on Cryptographic Hardware and Embedded Systems•Dec 3, 2020•47 citations
We perform logical and physical resource estimation for computing binary elliptic curve discrete logarithms using Shor's algorithm on fault-tolerant quantum computers. We adopt a windowed approach to design our circuit implementation of the algorithm, which comprises repeated applications of elliptic curve point addition operations and table look-ups. Unlike previous work, the point addition operation is implemented exactly, including all exceptional cases. We provide exact logical gate and qubit counts of our algorithm for cryptographically relevant binary field sizes. Furthermore, we estimate the hardware footprint and runtime of our algorithm executed on surface-code matter-based quantum computers with a baseline architecture, where logical qubits have nearest-neighbor connectivity, and on a surface-code photonic fusion-based quantum computer with an active-volume architecture, which enjoys a logarithmic number of non-local connections between logical qubits. At 10% threshold and compared to a baseline device with a1μs1μ s1μscode cycle, our algorithm runs≳\gtrsim≳2-20 times faster, depending on the operating regime of the hardware and over all considered field sizes, on a photonic active-volume device.
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.
Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses 3n+4⌊log⁡2n⌋+O(1)3n + 4\lfloor \log_2 n \rfloor + O(1)3n+4⌊log2​n⌋+O(1) logical qubits and 204n2log⁡2n+O(n2)204n^2\log_2 n + O(n^2)204n2log2​n+O(n2) Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with 5n+4⌊log⁡2n⌋+O(1)5n + 4\lfloor \log_2 n \rfloor + O(1)5n+4⌊log2​n⌋+O(1) qubits and O(n3)O(n^3)O(n3) Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.
We estimate the number of physical qubits and execution time by decomposing an implementation of Shor's algorithm for elliptic curve discrete logarithms into universal gate units at the logical level when surface codes are used. We herein also present modified quantum circuits for elliptic curve discrete logarithms and compare our results with those of the original quantum circuit implementations at the physical level. Through the analysis, we show that the use of more logical qubits in quantum algorithms does not always lead to the use of more physical qubits. We assumed using rotated surface code and logical qubits with all-to-all connectivity. The number of physical qubits and execution time are expressed in terms of bit length, physical gate error rate, and probability of algorithm failure. In addition, we compare our results with the number of physical qubits and execution time of Shor's factoring algorithm to assess the risk of attack by quantum computers in RSA and elliptic curve cryptography.
The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only 3n+6⌊log⁡2n⌋+O(1)3n+6\lfloor \log_2 n \rfloor+O(1)3n+6⌊log2​n⌋+O(1) logical qubits and 1056n3/log⁡2n+O(n2)1056n^3/\log_2 n+O(n^2)1056n3/log2​n+O(n2) Toffoli gates, where nnn is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only 2n+6⌊log⁡2n⌋+O(1)2n+6\lfloor \log_2 n \rfloor+O(1)2n+6⌊log2​n⌋+O(1) logical qubits and 229n2+O(nlog⁡2n)229n^2+O(n\log_2 n)229n2+O(nlog2​n) Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.
Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.
This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.