Why haven't quantum computers factored 21 yet?

> So how many gates are we talking to factor some "cryptographically useful" number?

Table 5 of [1] estimates 7 billion Toffoli gates to factor 2048 bit RSA integers.

> Is there some pathway that makes quantum computers useful this century?

The pathway to doing billions of gates is quantum error correction. [1] estimates distance 25 surface codes would be sufficient for those 7 billion gates (given the physical assumptions it lists). This amplifies the qubit count from 1400 logical qubits to a million physical noisy qubits.

Samuel Jacques had a pretty good talk at PQCrypto this year, and he speculates about timelines in it [2].

(I'm the author of this blog post and of [1].)

[1]: https://arxiv.org/pdf/2505.15917

[2]: https://www.youtube.com/watch?v=nJxENYdsB6c

It's not just quantum error correction that is required, it's also hard to make devices small enough due to cooling, to allow thousands of qubits let alone billions.

From the talk of Samuel Jacques: Timeline for RSA-2048 at about 2088 (conservative extrapolation) or ~2052 (Moore’s‑law‑style growth)

How do you go from 7 billion Toffoli gates (which consist of 42 billion "two-qubit entangling gates", per the blog post) to merely 1400 logical qubits?

Same way you go from 2 billion CPU operations per second to only ~4000 register bits (not counting ZMM SIMD registers) on a conventional CPU.

The operations all consist of saying, connect these 3 bits and do a reversible operation on them all together. Same as assembly, "add these two registers and store the sum in the first one..." You didn't need to introduce any new bits.

You only need to introduce new bits for steps that cannot be reversibly done, in assembly you get around this by being able to overwrite a register: in quantum, that requires an explicit measurement in the computational basis to figure out how you want to do stuff to zero it; zeroing a bit is not a unitary operation. But if you can encode the circuit in Toffoli gates which are perfectly reversible, you don't have to delete any bits after that encoding (but you may have to introduce extra bits to get to that encoding, like using Toffoli to build “x AND y” requires an extra z bit that effectively gets discarded at the end of the computation when everything is done and nobody cares what that bit holds, but it holds the information you would need to reverse that logical AND).

But yeah it's just number of operations that you need to run the algorithm, versus the number of registers that you need to run the algorithm, they're just two different numbers.

not all implementations of QC require cryogenic cooling

Is there a qubit-speed tradeoff, where you could factor 2048 bit RSA integers with fewer qubits but it would take more time? Or is it all or nothing?

A gate isn't a qubit, it's an operation applied to qubits. You can do more than one operation per qubit.

it will be done much faster than that, guessing 2035

Any insight as to why you think that?

Their company loses funding if it’s not done by 2036

I had a really deep and thoughtful discussion with ChatGPT /s

there is a trade-off, but it doesn't help too much because of you take more time, you need more error correction which takes more qbits. the best trade-off probably comes from dropping the error correction to the point where you go from 99% reliability to 1% reliability. doing so will increase your rsa factor time from ~1 week to ~1 year and probably saves you ~an order of magnitude in qbits

The big thing that could change the numbers is more reliable qbits. Most of the calculations so far are done with qbits right at the edge of where error correction works (about 5x better than current qbits). if you get another 10x in qbit quality you probably drop the required qbits by ~100-1000x.

it probably should be called a qop (like a flop) rather than a gate which sounds like a measure of space.

It comes from circuit depth

Since most QC researchers are saying that the real use cases are not Shor's or Grover's but rather molecular simulation (calculating ground state energies), do we have a timeline for doing anything useful in this space with quantum computers? A quick Googling indicates it take about 12 logical qubits to simulate extremely simple molecules like LiH and H4. Does the qubit requirement just scale linearly with the total number of electrons or is there an exponential function in there somewhere? I'm trying to get a sense of whetherf material science and biological applications are similarly 30+ years out or might come substantially sooner.

That is true but all will have components that require some cooling and scaling to billions of qubits will require cooling on a larger scale for said components.

Realistic Shor circuits have depth polynomial in n, but you can easily construct ones whose depth is polylogarithmic in n. Just do the multiplications as a binary tree instead of in a linear order, using log depth multiplication circuits, and then do the frequency basis measurement using a low depth QFT [1]. The only part that isn't known to be doable in polylog depth is the classical GCD computation hiding in the classical postprocessing, to find the closest fraction to get the period.

The result is that, if you keep adding qubits that can be operated on in parallel, Shor's algorithm basically just keeps getting faster and faster and faster. The energy cost doesn't go down, and the number of qubits required becomes frankly absurd, but the time can go really really low.

1: https://arxiv.org/abs/quant-ph/0006004

The real limit for quantum chemistry in NISQ is the circuit volume, since it requires O(N^4) gates.