Optimizing Quantum Circuits to do Better Arithmetic
Craig Gidney on the Hidden Cost of Computation
This week on the 632nm podcast, we speak with Craig Gidney about what actually makes quantum algorithms expensive, and why the hardest part often isn’t the “quantum” part at all.
Gidney’s work spans quantum algorithms, error correction, and implementation. Across that stack, his core insight is consistent: once you try to build these systems, the bottlenecks shift from elegant theory to very concrete questions about circuits, gates, and arithmetic.
The 632nm podcast features in-depth conversations with the world’s leading scientists and engineers.
If you haven’t already, subscribe to 632nm wherever you get your podcasts.
I. The Problem with “Factoring 21”
Small-scale demonstrations of Shor’s algorithm often claim to factor numbers like 21. But these experiments can be misleading about what’s actually difficult.
Gidney points out that the key test isn’t whether a period is found, but whether the algorithm is implemented faithfully:
“If there are papers that claim they factor 21 with the quantum computer… did they do the multiplication under superposition?”
In many cases, they don’t. Instead, they replace modular multiplication—the core subroutine—with something easier that reproduces the same periodic structure.
“They’ve done things that are sort of inspired by Shor’s algorithm… replaced the expensive part… with something that happens to have the same period.”
This shortcut preserves the appearance of the algorithm while avoiding the part that actually scales poorly. The result is that these demonstrations say very little about how hard factoring really is on a quantum computer.
II. Why Factoring 15 Is Unusually Easy
The prevalence of factoring 15 isn’t just historical—it’s structural. That specific case is dramatically simpler than almost any other.
“Multiplication mod 15 is really cheap… but multiplication mod 21 and most other numbers… the number of gates you need goes up by like a factor of a hundred.”
The reason is subtle but important. Modulo 15, many operations reduce to simple permutations of bits, rather than conditional logic between them.
“They don’t actually interact with each other. They just move.”
This means the circuit avoids the entangling operations that dominate cost in general cases. As soon as you move to numbers like 21, that simplification disappears, and the true scaling behavior emerges.
This gap—between toy demonstrations and real instances—is one of the central challenges in communicating progress in quantum computing.
III. Arithmetic Is the Real Work
At a conceptual level, quantum algorithms are framed in terms of interference and superposition. But when implemented, they are dominated by something far more classical: arithmetic.
“They come up in… a lot of algorithms… additions and like table lookups and little subroutines like this.”
These operations appear everywhere, from factoring to chemistry simulation, and they must be implemented reversibly and fault-tolerantly.
“Most of the stuff I’ve worked on has been arithmetic dominated.”
This creates a disconnect between how algorithms are taught and how they behave in practice. The “quantum” part provides the speedup, but the bulk of the circuit is spent managing data: moving, adding, and transforming it in ways that preserve coherence.
IV. The True Cost: Fault-Tolerant Gates
Once error correction is introduced, the cost model becomes highly uneven. Some operations are trivial, while others are extremely expensive.
“It’s very common for error correcting codes to implement the Clifford set… but… the T gate… not really clear how to do… other than via… magic state injection and distillation.”
Because of this, entire optimization strategies have historically focused on minimizing T gates.
“If a T gate is a hundred times more expensive… you can basically just count the T gates… to estimate the cost.”
Even as implementations improve and that ratio shrinks, the asymmetry remains. Certain gates fundamentally require more overhead, and that shapes everything from circuit design to architecture.
Attempts to bypass this cost have largely struggled in practice:
“I’ve generally been kind of skeptical… they tend not to end with numbers.”
What survives are methods that work under realistic noise and scaling assumptions—most notably magic state distillation, which leverages the ability to discard faulty states:
“Being allowed to throw things away… is a major advantage.”
V. Building Intuition with Tools
As circuits become more complex, reasoning about them by hand quickly becomes infeasible. Gidney’s response has been to build tools that make these systems visible and testable.
STIM, for example, emerged from frustration with overly idealized simulations:
“No one was doing circuit noise simulations… they were mostly doing… code capacity simulations.”
But these simplified models can lead to large errors in understanding real performance:
“The threshold of the surface code is 10 times lower under circuit noise.”
Crumble tackles a different problem—understanding how information and errors move through a circuit:
“What Crumble does is… show you how Pauli errors would propagate through the circuit.”
This kind of visibility fundamentally changes how circuits are designed. Instead of reasoning abstractly, you can experiment, test, and iterate:
“It would’ve been impossible without that tool, at least for me.”
The same philosophy extends to learning. Gidney’s own entry into quantum computing came from building simple simulations and gradually refining them:
“You have to be able to know if the output is correct.”
That ability—to construct, test, and verify—is what ultimately bridges the gap between theory and working systems.
The Bigger Picture
Quantum computing progress is often described in terms of breakthroughs. But in practice, it’s the accumulation of many small, precise improvements that drives the field forward.
“They all kind of stack up… and then… they can make a big difference.”
From arithmetic optimizations to better error correction schemes, each layer contributes to reducing the cost of real algorithms.
What emerges is a clearer picture: quantum computing isn’t just about exploiting physics. It’s about engineering—where the details of circuits, gates, and implementations determine what’s actually possible.
🎧 Full episode available now on YouTube and all podcast platforms.
Listen to our full conversation with Craig Gidney on your favorite podcast platform:
Or search for “632nm” on your preferred podcast player
If you know someone who would enjoy this, please share it with them!