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 nonlocal connections between logical qubits. At 10<inline-formula><tex-math notation="LaTeX">$\%$</tex-math></inline-formula> threshold and compared to a baseline device with a 1-<inline-formula><tex-math notation="LaTeX">$\mu \text{s}$</tex-math></inline-formula> code cycle, our algorithm runs <inline-formula><tex-math notation="LaTeX">$\gtrsim$</tex-math></inline-formula> 2–20 times faster, depending on the operating regime of the hardware and over all considered field sizes, on a photonic active-volume device.