Improvements for running Shor’s Algorithm on a 256-bit Elliptic Curve

We’re sharing a new autonomous result where we further reduce the resources required for running Shor’s algorithm on secp256k1, cutting the Toffoli count by 16.5% relative to the best published construction. The secp256k1 curve is a widely deployed 256-bit elliptic curve used, for example, to generate public keys and verify transactions in the Bitcoin network.

Shor’s algorithm is one of the most famous quantum algorithms because it can be used to break widely used public-key cryptography algorithms, including RSA and Elliptic Curve Cryptography (ECC). Compromising keys of the sizes used in practice, however, requires quantum computers with capabilities significantly beyond what is available today (more qubits alongside the ability to run much longer circuits).

Since the first estimates in 2003, resource requirements for implementing Shor’s algorithm have improved considerably. Earlier this month, a paper by Häner et al. reduced the number of Toffoli gates (the dominant computational cost of the algorithm) needed to run Shor’s algorithm on 256-bit elliptic curves. We anticipate further resource efficiencies will continue to be found. Below is a table summarizing how the resource requirements have evolved so far this year.

Initio’s construction requires 32,771,245 Toffoli gates, a 16.5% improvement relative to Häner et al.’s requirement of 39,255,168 gates, while keeping the same number of logical qubits (1457). We verified the construction with simulations, and the full report is linked here.

This result has real implications for quantum computers, making it easier for hardware to run practical algorithms. This improvement highlights the capability of our autonomous research systems to accelerate technology development.