Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice

• URL: http://arxiv.org/abs/2510.23212v1
• Date: Mon, 27 Oct 2025 11:02:10 GMT
• Title: 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,
• Abstract summary: Quantum computers have the potential to break classical cryptographic systems.<n>We propose a carry-lookahead quantum adder that achieves Toffoli depth $log n + loglog n + O(1)$ with only $O(n)$ ancillas.<n>We perform a comprehensive resource analysis of Shor's elliptic curve algorithm on two-dimensional lattices.
• Score: 7.999752490202695
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Analytical construction of $(n, n-1)$ quantum random access codes saturating the conjectured bound [0.0]
  Quantum Random Access Codes (QRACs) embody the fundamental trade-off between the compressibility of information into limited quantum resources.<n>We establish an analytical construction method for $(n, n-1)$-QRACs by using an explicit operator formalism.<n>We present a systematic algorithm to decompose the derived optimal POVM into standard quantum gates.
  arXiv  Detail & Related papers  (2026-01-27T04:43:43Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  This paper revisits the weighted strategy for non-stationary parametric bandits.<n>We propose a simpler weight-based algorithm that is as efficient as window/restart-based algorithms.<n>Our framework can be used to improve regret bounds of other parametric bandits.
  arXiv  Detail & Related papers  (2026-01-03T04:50:21Z)
• Efficient circuits for leaf-separable state preparation [0.0]
  We present a state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing leaf-separable" quantum states.<n>We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits.<n>These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.
  arXiv  Detail & Related papers  (2025-11-14T12:30:08Z)
• Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited [4.843809993270313]
  Efficiently solving the Shortest Vector Problem (SVP) in two-dimensional lattices holds practical significance in cryptography and computational geometry.<n>We develop an efficient adaptive lattice reduction algorithm textbfCrossEuc that strategically applies the Euclidean algorithm across dimensions.<n>By iteratively invoking textbfHVec, our optimized algorithm textbfHVecSBP achieves a reduced basis in $O(log n M(n) )$ time for arbitrary input bases with bit-length $n$.
  arXiv  Detail & Related papers  (2025-04-17T13:50:51Z)
• Quantum resource estimates for computing binary elliptic curve discrete logarithms [0.0]
  We adopt a windowed approach to design our circuit implementation of Shor's algorithm.<n>We provide exact logical gate and qubit counts of our algorithm for cryptographically relevant binary field sizes.<n>We estimate the hardware footprint and runtime of our algorithm executed on surface-code matter-based quantum computers.
  arXiv  Detail & Related papers  (2025-03-04T20:18:50Z)
• Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing [47.32366699399839]
  Finding an approximate secondepsilon dependence (SOSP) is a well-studied and fundamental problem. In this paper we apply our framework to the problem of lowdimension sensing machine optimization.
  arXiv  Detail & Related papers  (2024-03-12T01:27:44Z)
• New Space-Efficient Quantum Algorithm for Binary Elliptic Curves using the Optimized Division Algorithm [1.2183405753834562]
  We suggest a new quantum division algorithm on the binary field which uses a smaller number of qubits. For elements in a field of $2n$, we can save $lceil n/2 rceil - 1$ qubits instead of using $8n2+4n-12+(16n-8)lfloorlog(n)rfloor$ more Toffoli gates.
  arXiv  Detail & Related papers  (2023-03-12T05:00:46Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  This paper revisits the weighted strategy for non-stationary parametric bandits. We propose a refined analysis framework, which produces a simpler weight-based algorithm. Our new framework can be used to improve regret bounds of other parametric bandits.
  arXiv  Detail & Related papers  (2023-03-05T15:11:14Z)
• Digital-analog co-design of the Harrow-Hassidim-Lloyd algorithm [0.0]
  Harrow-Hassidim-Lloyd quantum algorithm was proposed to solve linear systems of equations $Avecx = vecb$. There is not an explicit quantum circuit for the subroutine which maps the inverse of the problem matrix $A$ into an ancillary qubit. We present a co-designed quantum processor which reduces the depth of the algorithm.
  arXiv  Detail & Related papers  (2022-07-27T13:58:13Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.