Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
Han Luo, Ziyi Yang, Ziruo Wang, Yuexin Su, Tongyang Li
Abstract
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 logical qubits and 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 qubits and 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.
AI Impact Assessments
(3 models)Scientific Impact Assessment
1. Core Contribution
This paper addresses a fundamental bottleneck in quantum attacks on elliptic curve cryptography: the number of logical qubits required to implement Shor's algorithm for ECDLP. The main technical contribution is a space-efficient, fully reversible modular inversion circuit based on the Extended Euclidean Algorithm (EEA) that uses only 3n + 4⌊log₂n⌋ + O(1) logical qubits, which when integrated into the full ECDLP circuit yields 5n + 4⌊log₂n⌋ + O(1) total qubits. For the practically important ECC-256 parameter set, this translates to 1333 logical qubits, down from 2124 in the previous best low-width implementation by Häner et al. (2020)—a ~37% reduction.
The paper resolves a longstanding gap between the theoretical space bound of Proos and Zalka (2003), which was stated at a high level of abstraction with O(n⁻²) fidelity loss, and practical circuit-level implementations. The authors achieve this bound exactly (no fidelity loss) with concrete, fully specified quantum circuits.
2. Methodological Rigor
The paper demonstrates strong methodological rigor across several dimensions:
Algorithmic correctness: The authors provide complete pseudocode (Algorithms 1-3), a detailed worked example (Table 4 for p=37, x=13), and formal proofs of key bounds (step counts in Appendix A.1, active window bounds in A.2). The step-count analysis proving N ∈ [4n, 4⌈cn⌉] with c = 1/log₂(φ) is tight and well-argued via Fibonacci sequences.
Register sharing refinement: The key innovation is making the register-sharing strategy of Proos-Zalka deterministic rather than probabilistic. By introducing length registers and location-controlled arithmetic, every input x in superposition uses the same register allocation scheme, eliminating the O(√n) overhead and O(n⁻²) fidelity loss of the original approach. This is a clean and important technical improvement.
Circuit-level detail: The paper provides explicit circuit diagrams (Figures 5-9) for all building blocks, including the non-trivial location-controlled operations. The step-dependent active window optimization (Section 4.3) is carefully analyzed to bound gate complexity.
Numerical validation: Resource estimates are validated via Qiskit implementations with transpilation to CCX/CX/X basis, with results reported for n ∈ {64,...,512}. The open-source code enhances reproducibility.
One limitation in rigor is that the gate counts for non-inversion components (modular multiplication, squaring) are inherited from prior work [RNSL17] without re-optimization, so the claimed overall Toffoli count of 976n³ + O(n³/log₂n) depends on those earlier estimates.
3. Potential Impact
Cryptographic security assessment: This work directly informs the quantum threat timeline for ECC-based systems (TLS, SSH, Bitcoin, etc.). Reducing the qubit requirement from 2124 to 1333 for ECC-256 is significant because it lowers the hardware threshold at which quantum computers can break real-world cryptography. This has implications for post-quantum migration planning by standards bodies (NIST, IETF) and industry.
Comparison with RSA: The paper notes that Chevignard et al. showed RSA-2048 can be factored with ~1730 qubits, while ECC-224 (comparable classical security) previously required 1862 qubits. This work reduces ECC-224 to 1169 qubits, making ECC potentially *easier* to break quantumly than RSA at equivalent classical security—an important reversal in the comparative quantum vulnerability landscape.
Modular inversion as a building block: The reversible modular inversion circuit is a general-purpose component applicable beyond ECDLP, potentially useful in any quantum algorithm requiring modular arithmetic (e.g., class group computations, lattice algorithms with modular operations).
Gate complexity: The O(n³) Toffoli count compares favorably with the concurrent O(n⁴(log n)²) of Chevignard et al. [CFS26], though the latter uses a different approach (residue number system with projective coordinates).
4. Timeliness & Relevance
This work is highly timely. The quantum computing community is actively estimating resources for cryptanalytic attacks, with recent breakthroughs in RSA factoring resource estimates (Regev, Ragavan-Vaikuntanathan, Gidney 2025). ECDLP resource estimates have lagged behind, and this paper helps close that gap. The existence of concurrent work (CFS26, BZG+26) on the same problem underscores the timeliness.
The practical relevance is amplified by the widespread deployment of ECC in critical infrastructure and the ongoing NIST post-quantum cryptography standardization process, where understanding the actual quantum threat to existing systems is crucial for transition planning.
5. Strengths & Limitations
Key Strengths:
Notable Limitations:
6. Additional Observations
The paper's structure is exemplary for a resource estimation paper: algorithm → circuit → resource count → numerical validation. The worked example in Table 4 is particularly valuable for verification and pedagogical clarity. The step-dependent active window technique is a clever optimization that meaningfully reduces the leading constant in gate count.
Generated Apr 3, 2026
Comparison History (71)
Paper 2 likely has higher scientific impact: it addresses a major scalability bottleneck in device-independent self-testing by reducing sample complexity from exponential to polynomial for almost all n-qubit states, with an experimentally plausible implementation using only linear ancillary Bell pairs. This is a broadly enabling advance for certification, learning, and verification across quantum networks and device-independent protocols, affecting theory and near-term experiments. Paper 1 is rigorous and valuable for quantum cryptanalysis resource estimation, but its impact is more specialized and incremental (qubit-count optimization within Shor/ECDLP implementations).
Paper 1 demonstrates chip-to-chip entanglement distribution over 80 km using silicon photonic integrated circuits with path encoding—a significant experimental milestone for quantum networks and QKD. It bridges photonic integration with long-distance entanglement, directly enabling scalable quantum communication infrastructure. Paper 2 presents valuable algorithmic optimizations for ECDLP qubit counts, but is incremental in nature (reducing qubit estimates from 2124 to 1333). Paper 1's experimental breakthrough has broader impact across quantum networking, cryptography deployment, and photonic integration, and is more timely given the push toward practical quantum networks.
Paper 2 likely has higher impact due to broader, timely relevance and cross-field reach: it connects LLM agents, automated experimentation, and variational quantum optimization, offering a general framework applicable beyond specific problem instances and potentially extensible to many VQA settings. Its closed-loop policy-search methodology and findings about proxy-evaluation pitfalls are widely useful for AutoML/agentic science and quantum optimization. Paper 1 is methodologically rigorous and important for post-quantum security/resource estimation, but it is narrower (ECDLP circuits) and primarily advances a specific subroutine’s qubit/Toffoli counts.
Paper 1 addresses the critical and timely problem of quantum cryptanalysis of elliptic curve cryptography, achieving a significant ~37% reduction in logical qubits for 256-bit ECDLP. This has direct implications for post-quantum cryptography migration planning and security assessments. Paper 2 introduces interesting theoretical concepts for quantum optimization circuits, but its practical impact is limited by small problem sizes (up to 9 cities) and the broader challenge of quantum optimization algorithms competing with classical methods. Paper 1's concrete resource estimates are immediately actionable for the cryptography community.
Paper 2 is more novel: it introduces an intrinsically quantum decoding method for classical LDPC codes under coherent superpositions, connecting quantum algorithms, coding theory, and average-case optimization (max-k-XORSAT). Its potential breadth is larger (optimization, decoding, quantum algorithms), and it is timely given interest in quantum advantage for structured problems. Although it does not yet demonstrate a clear quantum advantage, the framework and empirical regime improvements suggest impactful follow-up directions. Paper 1 is rigorous and practically relevant for cryptographic resource estimation, but is a more incremental circuit-optimization advance within an established line of Shor/ECDLP resource work.
Paper 2 addresses a fundamental and widely relevant problem—quantum cryptanalysis of elliptic curve cryptography—with concrete, quantifiable improvements (reducing logical qubits from 2124 to 1333 for 256-bit curves). This has direct implications for post-quantum cryptography standards and security planning across all sectors. The results are rigorous, with explicit circuit constructions and resource estimates. Paper 1, while interesting in combining LLMs with variational quantum algorithms, addresses a narrower niche (automated VQA configuration) with less immediate practical impact, and its reliance on current noisy quantum hardware limits its near-term applicability.
Paper 2 addresses a highly critical and timely problem: the quantum resource requirements to break widely deployed elliptic-curve cryptography (ECDLP). By significantly reducing the logical qubit count for a 256-bit curve, it provides concrete implications for cybersecurity and the timeline for transitioning to post-quantum cryptography. Paper 1 introduces an interesting theoretical approach for quantum combinatorial optimization (like TSP), but quantum advantage for such heuristic optimization problems remains uncertain, making Paper 2's impact more immediate and globally consequential.
Paper 1 addresses a fundamental problem in post-quantum cryptography—reducing qubit requirements for breaking elliptic curve cryptography via Shor's algorithm. The concrete 37% reduction in logical qubits (1333 vs 2124 for 256-bit curves) has direct implications for quantum security timeline estimates and cryptographic migration planning, affecting industry and government policy. Paper 2, while intellectually interesting in connecting optimization to quantum decoding, explicitly acknowledges it falls short of demonstrating quantum advantage, with classical algorithms matching its performance. Paper 1's practical relevance to cryptographic security gives it broader and more immediate impact.
Paper 2 likely has higher scientific impact due to immediate applicability to near-term superconducting quantum devices, broad relevance to quantum compilation and hardware-aware transpilation, and strong practical benchmarks (up to 36% CNOT reduction and 553× speedup, scaling beyond 10 qubits where others time out). Paper 1 is rigorous and valuable for long-term cryptanalysis resource estimation, but targets fault-tolerant regimes and a narrower application (ECDLP). Paper 2’s methods can impact many algorithms and workflows across platforms, making it more timely and broadly influential.
Paper 2 addresses a fundamental question about why macroscopic quantum variables in superconducting circuits obey quantum commutation relations, deriving this from microscopic BCS theory via 'third quantization.' This provides a unified theoretical framework for circuit QED with broad implications for quantum computing hardware, condensed matter physics, and quantum foundations. While Paper 1 offers valuable practical optimization for quantum cryptanalysis (reducing qubit counts for ECDLP), it is primarily an incremental engineering improvement. Paper 2's conceptual contribution—bridging microscopic superconductivity to macroscopic circuit quantization—has wider cross-disciplinary impact and deeper theoretical significance.