Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice
Authors
Quan Gu, Han Ye, Junjie Chen, Xiongfeng Ma
Categories
Abstract
Quantum computers have the potential to break classical cryptographic systems by efficiently solving problems such as the elliptic curve discrete logarithm problem using Shor's algorithm. While resource estimates for factoring-based cryptanalysis are well established, comparable evaluations for Shor's elliptic curve algorithm under realistic architectural constraints remain limited. In this work, we propose a carry-lookahead quantum adder that achieves Toffoli depth $\log n + \log\log n + O(1)$ with only $O(n)$ ancillas, matching state-of-the-art performance in depth while avoiding the prohibitive $O(n\log n)$ space overhead of existing approaches. Importantly, our design is naturally compatible with the two-dimensional nearest-neighbor architectures and introduce only a constant-factor overhead. Further, we perform a comprehensive resource analysis of Shor's elliptic curve algorithm on two-dimensional lattices using the improved adder. By leveraging dynamic circuit techniques with mid-circuit measurements and classically controlled operations, our construction incorporates the windowed method, Montgomery representation, and quantum tables, and substantially reduces the overhead of long-range gates. For cryptographically relevant parameters, we provide precise resource estimates. In particular, breaking the NIST P-256 curve, which underlies most modern public-key infrastructures and the security of Bitcoin, requires about $4300$ logical qubits and logical Toffoli fidelity about $10^{-9}$. These results establish new benchmarks for efficient quantum arithmetic and provide concrete guidance toward the experimental realization of Shor's elliptic curve algorithm.
Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice
Categories
Abstract
Quantum computers have the potential to break classical cryptographic systems by efficiently solving problems such as the elliptic curve discrete logarithm problem using Shor's algorithm. While resource estimates for factoring-based cryptanalysis are well established, comparable evaluations for Shor's elliptic curve algorithm under realistic architectural constraints remain limited. In this work, we propose a carry-lookahead quantum adder that achieves Toffoli depth $\log n + \log\log n + O(1)$ with only $O(n)$ ancillas, matching state-of-the-art performance in depth while avoiding the prohibitive $O(n\log n)$ space overhead of existing approaches. Importantly, our design is naturally compatible with the two-dimensional nearest-neighbor architectures and introduce only a constant-factor overhead. Further, we perform a comprehensive resource analysis of Shor's elliptic curve algorithm on two-dimensional lattices using the improved adder. By leveraging dynamic circuit techniques with mid-circuit measurements and classically controlled operations, our construction incorporates the windowed method, Montgomery representation, and quantum tables, and substantially reduces the overhead of long-range gates. For cryptographically relevant parameters, we provide precise resource estimates. In particular, breaking the NIST P-256 curve, which underlies most modern public-key infrastructures and the security of Bitcoin, requires about $4300$ logical qubits and logical Toffoli fidelity about $10^{-9}$. These results establish new benchmarks for efficient quantum arithmetic and provide concrete guidance toward the experimental realization of Shor's elliptic curve algorithm.
Authors
Quan Gu, Han Ye, Junjie Chen et al. (+1 more)
Click to preview the PDF directly in your browser