Quantum resource estimates for computing binary elliptic curve discrete logarithms

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\mu 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.

Close to published version

References in corpus (26)

• Surface codes: Towards practical large-scale quantum computation
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Surface code quantum computing by lattice surgery
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Entanglement of trapped-ion qubits separated by 230 meters
• Novel constructions for the fault-tolerant Toffoli gate
• Assessing requirements to scale to practical quantum advantage
• Low overhead quantum computation using lattice surgery
• Logical blocks for fault-tolerant topological quantum computation
• Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations
• Depth optimization of CZ, CNOT, and Clifford circuits
• High photon-loss threshold quantum computing using GHZ-state measurements
• Scalable Multispecies Ion Transport in a Grid-Based Surface-Electrode Trap
• Tailoring fusion-based photonic quantum computing schemes to quantum emitters
• Creation of Entangled Photonic States Using Linear Optics
• Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
• Encoded-Fusion-Based Quantum Computation for High Thresholds with Linear Optics
• Extending Regev's factoring algorithm to compute discrete logarithms
• Realistic Cost to Execute Practical Quantum Circuits using Direct Clifford+T Lattice Surgery Compilation
• Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections
• How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates
• An Architecture for Improved Surface Code Connectivity in Neutral Atoms