Quantum Circuit
A quantum circuit is a recipe for a quantum computation: take a set of qubits, apply an ordered sequence of quantum gates that steer their states, then measure the result to read out a classical answer. It’s the dominant model for how quantum computers actually run algorithms, and it’s the quantum cousin of the logic-gate diagrams that describe an ordinary chip. The gates are reversible operations that nudge qubits in and out of superposition and entanglement, arranged so the answer you want is the one most likely to appear when you measure. For cryptography, the circuit is where an abstract threat like Shor’s algorithm becomes a concrete engineering bill, and one property of the circuit, its depth, is a big part of why no machine can run that attack against real keys yet.
The short version:
- A quantum circuit is qubits, plus an ordered list of quantum gates, plus a measurement at the end. That’s the whole model.
- Quantum gates are reversible operations on qubits. A Hadamard gate creates superposition, a CNOT gate entangles two qubits, and a Toffoli gate does reversible arithmetic. You don’t need the matrices to grasp what each one does.
- Algorithms like Shor’s and Grover’s are written as circuits. Publishing one is how researchers turn “this attack exists in theory” into “here is exactly how many qubits and gates it takes.”
- Circuit depth is the length of the longest chain of gates any single qubit has to pass through. Deep circuits are hard because qubits decohere, meaning they hold their fragile state for only a short time before noise corrupts them.
- Breaking RSA-2048 with Shor’s takes a circuit billions of gates deep that would run for hours, far longer than any physical qubit stays coherent, which is why a real attack needs full quantum error correction and why it doesn’t exist today.
What is a quantum circuit?
A quantum circuit is the standard way to describe a quantum computation, drawn as a set of horizontal lines, one per qubit, with gates placed along them from left to right in the order they run. You read it like sheet music: time flows left to right, each qubit is a staff, and each gate is a note that changes the qubits it touches. At the far right, some or all of the qubits are measured, which is the step that produces the ordinary bits you actually get to see.
The model was introduced by David Deutsch in 1989 under the name quantum computational networks, as the quantum generalization of the classical logic circuit. The parallel to a normal chip is close and useful. A classical circuit wires up gates like AND, OR, and NOT to transform bits. A quantum circuit wires up quantum gates to transform qubits. The difference is what the wires carry. Classical wires carry a definite 0 or 1; quantum “wires” carry qubits that can be in superposition and can be entangled with one another, which is the whole source of a quantum computer’s power.
Source: David Deutsch, “Quantum computational networks,” Proceedings of the Royal Society A 425(1868), 1989, royalsocietypublishing.org.
Three things make up every circuit:
- The qubits. The register the circuit operates on, prepared in a known starting state (usually all zeros).
- The gates. An ordered sequence of operations that transform the qubits. This is the program.
- The measurement. The final step that collapses the qubits back into ordinary bits you can read. Quantum algorithms are designed so that when you measure, the answer you want is the outcome most likely to appear.
What are quantum gates?
A quantum gate is a reversible operation applied to one or more qubits, the basic instruction a quantum program is built from. Reversible is the key word: every quantum gate can be undone, because it just rotates the qubits’ state rather than erasing any information. That’s a real departure from classical logic, where a gate like AND throws information away (knowing the output is 0 doesn’t tell you which inputs produced it). A small handful of gate types, combined in the right order, can express any quantum computation, the same way NAND gates alone can build any classical circuit.
You can understand what each common gate does without ever seeing a matrix:
| Gate | What it does, in plain terms | Why it matters |
|---|---|---|
| Hadamard (H) | Puts one qubit into an even superposition of 0 and 1 | Creates the “hold every possibility at once” state that quantum algorithms start from |
| CNOT (controlled-NOT) | Flips one qubit’s value depending on another qubit’s value | The workhorse that entangles two qubits so their outcomes are linked |
| Toffoli (CCNOT) | Flips a qubit only when two control qubits are both 1 | A reversible version of classical AND; lets a circuit do ordinary arithmetic, the guts of Shor’s |
| Pauli-X (NOT) | Flips a single qubit between 0 and 1 | The straightforward quantum bit-flip |
| Phase and T gates | Nudge a qubit’s phase by a fixed angle | The “expensive” gates on an error-corrected machine; they dominate the cost of a real cryptographic attack |
| Measurement | Collapses a qubit’s blended state back to a definite 0 or 1 | Turns the quantum computation into a classical answer you can read |
The two gates worth remembering are Hadamard and CNOT. Hadamard is how a quantum computer sets up superposition, so that a later step can act on many inputs in a single pass. CNOT is how it creates entanglement, wiring qubits together so the machine can compute on the whole linked system rather than one qubit at a time. Nearly every quantum algorithm is some choreography of “spread into superposition, entangle and compute, then concentrate the answer so measurement reveals it.”
Source: Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, 2010, cambridge.org.
How do algorithms like Shor’s and Grover’s become circuits?
A quantum algorithm becomes real by being expressed as a specific circuit: a named list of gates in a named order that a machine could, in principle, execute. “Shor’s algorithm” isn’t a vague capability. It’s a concrete circuit that prepares a superposition, runs a chunk of modular arithmetic built out of Toffoli gates, applies a quantum Fourier transform, and measures. Grover’s algorithm is a different circuit: a Hadamard layer to spread into superposition, then a block of gates repeated many times that slowly tilts the odds toward the target, then a measurement.
This is why the circuit view matters so much for security. Writing an attack as a circuit is what converts “quantum computers threaten RSA” into an exact engineering estimate: this many qubits, this many gates, this much depth, on hardware with this error rate. Every serious resource estimate for breaking real cryptography, meaning the numbers behind the whole post-quantum migration, is really a statement about the size and depth of a circuit.
There’s a scale gap between the two kinds of circuit that’s easy to miss. Small versions of these algorithms, running against toy inputs, are shallow enough to run on today’s noisy machines and have been demonstrated. The circuits that attack real, deployed key sizes are astronomically larger. The gap between a classroom demonstration and a genuine attack is the gap between a circuit a few dozen gates deep and one billions of gates deep, and that difference is measured in decades of hardware progress.
What is circuit depth, and why are deep circuits hard?
Circuit depth is the length of the longest chain of gates that any single qubit has to pass through from start to finish. If width (the qubit count) is how wide the circuit is, depth is how tall it is in time. Depth matters more than almost any other metric for one physical reason: every gate takes time to run, so a deep circuit takes a long time to finish, and qubits can’t hold their state for very long.
That fragility is decoherence. A physical qubit is an exquisitely delicate object, and the faintest disturbance from its environment (stray heat, vibration, electromagnetic noise) knocks it out of the precise state the computation depends on. Left alone, a qubit holds its quantum state for only a brief moment before decoherence scrambles it. A circuit that needs to run longer than that window will be corrupted partway through, and the answer comes out as noise.
This is the wall that limits today’s machines, and it splits quantum computing into two eras:
- Shallow circuits on noisy hardware. Today’s processors can run circuits only a modest number of gates deep before decoherence and gate errors overwhelm the result. That’s enough for demonstrations and for algorithms tolerant of a little noise, and it’s nowhere near enough to run a deep cryptographic attack.
- Deep circuits with error correction. To run a circuit deeper than a qubit’s natural lifetime, you need quantum error correction: many noisy physical qubits woven together to act as one much more reliable logical qubit, with errors caught and fixed continuously while the computation runs. This is what lets a computation outlast any single qubit’s coherence, and building it at cryptographic scale is the central unsolved engineering problem.
So “deep circuits are hard” comes down to a race between how long a computation needs to run and how long a qubit can survive. Deeper circuits demand either longer coherence or, realistically, full error correction underneath the whole thing.
Source: Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, 2010, cambridge.org.
The metrics that decide whether a circuit can run on a given machine:
| Metric | What it measures | Why it’s a binding constraint |
|---|---|---|
| Width | How many qubits the circuit uses | Sets the raw size of machine you need |
| Depth | The longest chain of gates any one qubit passes through | Sets how long the qubits must survive, capped by decoherence |
| Gate count | The total number of operations | Every gate carries a small error chance, so more gates means more accumulated error |
How does circuit depth connect to breaking RSA-2048?
The circuit that runs Shor’s algorithm against RSA-2048 is both very wide and staggeringly deep, and its depth is exactly why the attack is hard rather than impossible. The most-cited peer-reviewed resource estimate puts the attack at roughly 2.6 billion Toffoli gates running on about 20 million noisy physical qubits, with a total runtime on the order of 8 hours. Read that again: the machine has to run one continuous computation, billions of operations deep, for hours.
Source: Craig Gidney and Martin Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, arXiv:1905.09749.
Now put that next to a physical qubit’s coherence window, which lasts a tiny fraction of a second. A raw qubit can’t stay alive for eight hours; it can’t stay alive for eight seconds. There’s no way to run a circuit that deep on bare hardware. The only path is error correction: spend most of your physical qubits on continuously repairing the computation so a handful of reliable logical qubits can carry it all the way through. That single requirement, running a billions-deep circuit under error correction for hours, is what a cryptographically relevant quantum computer has to deliver, and no machine is remotely close.
It also explains why headline qubit-count records don’t move cryptographic risk. Announcing more physical qubits addresses width. The binding constraint for a Shor’s attack is depth run under error correction, which is a different and much harder axis. A processor with thousands of noisy qubits and shallow usable depth is not partway to breaking RSA; it’s on the wrong side of the wall entirely.
The one encouraging thing for defenders and the sobering thing for the timeline is that the estimated cost keeps dropping as the circuit design improves. A 2025 optimization brought the physical-qubit estimate for the same RSA-2048 attack down from 20 million to under 1 million, by making the circuit more efficient rather than by waiting for better hardware. The threshold is a moving research target, which is one more reason the honest answer to “when?” is a range, and the honest response is to migrate on your own schedule rather than the attacker’s.
Source: Craig Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025, arXiv:2505.15917.
How does a circuit get onto real hardware?
A circuit written in a high-level toolkit rarely matches the machine it runs on, so it gets translated in a step called transpilation. Real processors only support a small menu of native gates and only allow certain qubits to interact directly, based on the physical layout of the chip. Transpilation rewrites the ideal circuit into that native menu, adds extra gates to shuffle qubits next to the ones they need to interact with, and tries to keep the total depth as low as possible so the result finishes before decoherence sets in.
The catch is that this translation almost always makes a circuit deeper, because it inserts routing operations the original didn’t have. For a cryptographic attack, where depth is already the limiting factor, this overhead is one more reason the real-hardware cost is higher than the clean theoretical circuit suggests. Keeping transpiled depth manageable is part of what the resource-estimate research works so hard to optimize.
Common misconceptions
- “A quantum circuit is just a faster version of a classical logic circuit.” They share the gate-and-wire picture, but the wires carry qubits that can be in superposition and entangled, and every gate is reversible. That’s a genuinely different machine, not a quicker chip.
- “If a computer has enough qubits, it can run any circuit.” Qubit count is only the width. A circuit also has depth, and running a deep circuit takes longer than a qubit stays coherent. Width without depth-under-error-correction gets you nowhere near a real attack.
- “Deeper circuits just need a bit more time.” The problem is coherence, not patience. A qubit’s state decays in a fraction of a second, so a circuit that would run for hours has to be protected by error correction the entire way, which is the hard part.
- “Measurement is just reading the answer off the qubits.” Measuring collapses a qubit’s blended state to a single definite outcome, so you get one result, not the whole superposition. Algorithms are built so that the outcome you want is the one most likely to appear when you measure.
- “A record-breaking qubit count means RSA is about to fall.” Qubit-count records are about width on noisy hardware. A Shor’s attack is gated by circuit depth run under full error correction, an entirely different axis where progress is far slower.
Questions people ask
Do I need to understand the math to get how a quantum circuit works? No. The model is qubits, a sequence of gates, and a measurement, and you can understand what each common gate does (Hadamard makes superposition, CNOT entangles, Toffoli does reversible arithmetic) at the level of what it accomplishes without touching the linear algebra. The math matters for building circuits, not for understanding why depth is the constraint that keeps a cryptographic attack out of reach.
What’s the difference between a quantum gate and a quantum circuit? A gate is a single reversible operation on one or a few qubits, like Hadamard or CNOT. A circuit is an ordered sequence of those gates applied to a register of qubits, followed by measurement. The gate is the instruction; the circuit is the whole program.
Why can’t a quantum computer with lots of qubits just run a deeper circuit? Because depth costs time, and qubits decohere. A deep circuit takes long enough that a physical qubit loses its state partway through, corrupting the result. Running a genuinely deep circuit requires quantum error correction to keep the computation alive longer than any single qubit survives, and building that at scale is the unsolved problem.
How deep is the circuit that breaks RSA-2048? Very deep. The most-cited estimate involves roughly 2.6 billion Toffoli gates and a runtime on the order of 8 hours on about 20 million noisy physical qubits, all of it running under error correction (arXiv:1905.09749). A 2025 optimization cut the physical-qubit figure to under a million by improving the circuit, though the depth stays enormous (arXiv:2505.15917).
Has anyone run a real Shor’s circuit against a real key? No. Genuine quantum factoring results are on tiny, specially chosen numbers whose circuits are shallow enough to run on current hardware. Nothing close to the depth and width needed for RSA-2048 has run, because the error-corrected machine it would require doesn’t exist.
Why are some gates called “expensive”? On an error-corrected machine, some gates (the phase and T gates) are far costlier to perform reliably than others, so they dominate the resource budget of a big computation. When researchers estimate the cost of a cryptographic attack, the count of these expensive gates is often the number that drives the total, which is why circuit design focuses on minimizing them.
Is measurement part of the circuit? Yes. Measurement is the final stage of almost every quantum circuit, and it’s what turns the qubits’ quantum state into the classical bits you read out. Because measuring collapses superposition to one outcome, algorithms are designed so the desired answer is the most probable measurement result.
Does the circuit view change how I should think about the quantum threat? It sharpens it. Seeing the attack as a specific, billions-deep circuit makes clear that the threat is a concrete engineering target with named requirements, not a vague someday. It’s also why qubit-count press releases and a real CRQC are different things, and why the sane response is to migrate to post-quantum cryptography on your own timeline rather than betting on when the circuit becomes runnable.
Everything here is the map, given freely. When your team needs the quantum threat translated into what it actually means for your systems and your timeline, that’s the work I do. Request an alignment briefing.
Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.