While the Quantum Hardware has been developed and progressing at the predicted rate, the Quantum Algorithms and manufacturing have improved far in excess of expectations. In June 2023, Litinski released a draft of his paper, “How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates.” The paper was a surprise for several reasons, including the acceleration of quantum attacks against blockchain cryptography by 3-5 years. This blog post will explore the draft version of this paper which may change during the editorial process.
First of all, the paper encapsulates a lot of the innovations in quantum algorithms that have been contributed by others. Through reduced computational requirements for Shor’s algorithm on Discrete Logs, several lower cost circuits are implemented from a variety of sources. The available literature on other algorithms is referenced for the reader to explore. The compounding effect of several innovations from different sources is significant. Charts are provided to the reader for the computational cost on a per calculation basis with resource estimates for different quantum architectures.
Secondly, as described in the quantum circuit has removed an expensive operation of setting a value to zero then writing additional information to load the circuit. This was simplified by calculating the inverse of the current value and applying it to the next value, allowing for substitution in place. Figure 14 explains how to do this operation on 4 values in parallel, then made available sequentially to further save qubits.
Thirdly, the use of "Active Volume" no longer requires local connections where every qubit is directly connected to every other qubit. The connections scale with the number of logical operations creating much simpler wiring diagrams. The shift in wiring forges a new standard for a different kind of quantum computing: smaller networked quantum computers that can solve larger problems.
The algorithms predicted around 100 million qubits for calculating the discrete log of a 256-bit elliptic curve. In the older architecture before Active Volume, that needed to be a 100 million qubit super computer, and no one was capable of building a machine of that magnitude. The state of the art needed to increase 100,000 fold before these calculations would become possible. With the shift to Active Volume, now 6000 quantum machines at 1152 qubits each could be networked together and perform the calculation. This is especially notable since 2023 also introduced IBM’s 1152 qubit machine, and Atom Computing’s 1255 qubit machine.
Now we are entering an era of mass production of quantum computers and their components. The three notable companies in the space are PSIQuantum, Intel and Oxford Ionics. PSIQuantum is the current leader with a complete modular component that scales horizontally by adding more pieces. Intel has focused on their strength in manufacturing to create a fully automated wafer production and testing process. Oxford Ionics is producing machines operating at room temperature. Of these, only PSIQuantum where Litinski also works is currently capable of producing functional systems at scale and they contracted GlobalFoundry to produce their components.
The year that people were commonly predicting for 256 bit ECC being at risk was 2030-2031, with increasing risk per year. The estimates among experts familiar with the papers described here are now estimating 2026-2027, with a slim possibility of 2025.