Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition

As quantum computers move toward fault-tolerant scales, reducing the resource requirements for Shor's algorithm—specifically for the Elliptic Curve Discrete Logarithm Problem (ECDLP)—is critical. This paper addresses the challenge of minimizing the number of logical qubits required for ECDLP, focusing on the modular inversion subroutine, which is the primary bottleneck in affine-coordinate point addition.

The authors refine the register-sharing strategy originally proposed by Proos and Zalka. They introduce length registers and location-controlled arithmetic to create a more compact, reversible modular inversion circuit based on the Extended Euclidean Algorithm (EEA). By integrating this circuit with mid-circuit measurements and classical feed-forward operations, they enable an in-place affine point-addition circuit that recycles workspace registers, thereby lowering the overall qubit count.

The proposed construction achieves a space complexity of 3n + 6 log2 n + O(1) logical qubits for ECDLP. For a standard 256-bit prime-field curve (secp256k1), this results in a requirement of 835 logical qubits, which is a notable improvement over previous estimates of 1098 and 1175 qubits. Additionally, the authors provide explicit circuit constructions and detailed gate-count estimates, showing a Toffoli-gate complexity of 919n^3 / log2 n + O(n^2).

This work provides a concrete, reproducible path toward more efficient quantum cryptanalysis. By reducing the number of logical qubits needed to break ECC, the authors provide a more accurate assessment of the security landscape for existing cryptographic standards, helping researchers understand the practical requirements for future fault-tolerant quantum hardware.