In 2001, quantum computers factored the number 15. It’s now 2025, and quantum computers haven’t yet factored the number 21. It’s sometimes claimed this is proof there’s been no progress in quantum computers. But there’s actually a much more surprising reason 21 hasn’t been factored yet, which jumps out at you when contrasting the operations used to factor 15 and to factor 21.
The circuit (the series of quantum logic gates) that was run to factor 15 can be seen in Figure 1b of “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance”:
The important cost here is the number of entangling gates. This factoring-15 circuit has 6 two-qubit entangling gates (a mix of CNOT and CPHASE gates). It also has 2 Toffoli gates, which each decompose into 6 two-qubit entangling gates. So there’s a total of 21 entangling gates in this circuit.
Now, for comparison, here is a circuit for factoring 21. Sorry for rotating it, but I couldn’t get it to fit otherwise. Try counting the Toffolis:
(Here’s an OPENQASM2 version of the circuit, so you can test it produces the right distribution if you’re inclined to do so.)
In case you lost count: this circuit has 191 cnot gates and 369 Toffoli gates, implying a total of 2405 entangling gates. That’s 115x more entangling gates than the factoring-15 circuit. The factoring-21 circuit is more than one hundred times more expensive than the factoring-15 circuit.
When I ask people to guess how many times larger the factoring-21 circuit is, compared to the factoring-15 circuit, there’s a tendency for them to assume it’s 25% larger. Or maybe twice as large. The fact that it’s two orders of magnitude more expensive is shocking. So I’ll try to explain why it happens.
(Quick aside: the amount of optimization that has gone into this factoring-21 circuit is probably unrepresentative of what would be possible when factoring big numbers. I think a more plausible amount of optimization would produce a circuit with 500x the cost of the factoring-15 circuit… but a 100x overhead is sufficient to make my point. Regardless, special thanks to Noah Shutty for running expensive computer searches to find the conditional-multiplication-by-4-mod-21 subroutine used by this circuit.)
Where does the 100x come from?
A key background fact you need to understand is that the dominant cost of a quantum factoring circuit comes from doing a series of conditional modular multiplications under superposition. To factor an $n$-bit number $N$, Shor’s algorithm will conditionally multiply an accumulator by $m_k = g^{2^k} \pmod{N}$ for each $k < 2n$ (where $g$ is a randomly chosen value coprime to $N$). Sometimes people also worry about the frequency basis measurement at the end of the algorithm, which is crucial to the algorithm’s function, but from a cost perspective it’s irrelevant. (It’s negligible due by an optimization called “qubit recycling”, which I also could have used to reduce the qubit count of the factoring-21 circuit, but in this post I’m just counting gates so meh).
... continue reading