← Research

Oct 16, 2026/Result/Quantum computing

Building the resource frontier for Shor’s algorithm on Elliptic Curves

We continued running autonomous research to further reduce the resources required to run Shor’s algorithm on secp256k1 and P-256. With the same 1,457 logical qubits, our shortest circuit now requires 27.5M Toffoli gates, while simultaneously increasing the success probability (at least 74.7%) of the algorithm under the same assumptions for classical post-processing1. A second circuit with the same qubit count further increases the success probability to at least 78.9%, reducing the number of Toffoli gates per recovered key to 35.5M. This is almost 50% lower than the Häner et al. estimate published in September.

Table comparing Shor's algorithm on secp256k1 at 1,457 logical qubits: Häner et al. 39,255,168 Toffolis per run, at least 55.3% success, 71.0M per recovered key; Initio earlier result 32,771,245, at least 60.0%, 54.6M; Initio gate-optimized 27,519,242, at least 74.7%, 36.8M; Initio cost-optimized 28,047,551, at least 78.9%, 35.5M per recovered key (−49.9%)

Using our system, we can map the tradeoff between qubit number and gate count and build a resource frontier that relies on the collection of techniques discovered to date. It ranges from 28.25M Toffoli gates at 1,380 qubits down to 24.9M at 2,014 qubits. Note that we did not use the same amount of compute to optimize across different qubit counts, and further reductions are very likely.

secp256k1 quantum resource frontier: Toffolis per run fall from 28.25M at about 1,380 peak logical qubits to 24.87M at about 2,014, and Toffolis per certified success fall from 37.96M to 32.00M

We also applied similar techniques for P-256, a NIST-standard elliptic curve for digital signatures (ECDSA) and key exchange (ECDH). The resulting graph is below.

P-256 quantum resource frontier: Toffolis per run fall from 52.07M at about 1,210 peak logical qubits to 28.75M at about 2,300

A new paper describing the constructions and their resource counts is available here.

Footnotes

  1. By allowing more classical post-processing per run, the success probabilities rise further. Section 9 of the paper describes this. ↑