Quantum Circuit Model

The quantum circuit model is the lingua franca of quantum computation — the notation in which every quantum algorithm, from Shor's factoring to the latest variational chemistry routine, is written down. Its picture is deceptively simple. A computation begins with $n$ qubits in a fixed product state, almost always $\lvert 0\rangle^{\otimes n}$ . The qubits are drawn as horizontal wires; gates are boxes on those wires, read strictly from left (input) to right (output). Single-qubit gates such as the Paulis, the Hadamard, and the phase gates act on one wire; entangling gates such as CNOT straddle two. The unitary part of the whole circuit is nothing more than the ordered product of these gates, each lifted to the full $2^n$ -dimensional Hilbert space, and the computation ends with measurements that convert amplitudes into classical bits. What makes the model precise rests on three structural facts. First, between measurements the evolution is unitary — hence reversible and norm-preserving — because a closed quantum system obeys the Schrödinger equation. Second, gates on disjoint wires combine by tensor product and gates on shared wires by matrix multiplication, giving a clean algebra in which circuit identities are just operator equalities. Third, and deepest, a small finite gate set suffices to approximate any unitary to arbitrary accuracy, so a circuit need only be a finite string of standard primitives. Measurement is the bridge back to classical information: the Born rule turns the final amplitudes into a probability distribution over bit strings, and because intermediate measurements can be deferred to the end, the whole computation may be analyzed as one giant unitary followed by a terminal readout. This directness is not one formalism among many — it is provably polynomial-time equivalent to the quantum Turing machine and to the measurement-based, adiabatic, and topological models, and it is the setting in which BQP, the notion of efficient quantum computation, is defined.

Key takeaways

A quantum computation is a fixed recipe: prepare $\lvert 0\rangle^{\otimes n}$ , apply a sequence of unitary gates drawn from a universal set, then measure in the computational basis — qubits are wires, gates are boxes, time runs left to right.
A pure state of $n$ qubits lives in $\mathbb{C}^{2^n}$ ; the whole unitary block is a single product $U = U_L\cdots U_2 U_1$ , with later gates written to the left of earlier ones.
Single-qubit gates act as tensor factors and create no entanglement; a genuine two-qubit gate such as CNOT is what knits the wires together and gives the model its power.
Any unitary can be approximated to arbitrary precision by gates from a finite universal set, e.g. $\{H, T, \mathrm{CNOT}\}$ ; the Solovay–Kitaev theorem makes the cost only $\mathrm{polylog}(1/\epsilon)$ per gate.
Measurement yields classical bits with Born-rule probabilities $p(x)=\lvert\langle x\vert\psi\rangle\rvert^2$ ; the model cleanly separates reversible quantum evolution from irreversible readout, and errors accumulate only additively across the circuit.
Key idea: a quantum algorithm is a finite directed sequence — prepare $\lvert 0\rangle^{\otimes n}$ , apply a product of unitary gates from a universal set, then measure — so the whole computation is the unitary $U = U_L \cdots U_2 U_1$ acting on $\mathbb{C}^{2^n}$ followed by Born-rule sampling.

The core insight

A quantum algorithm is a finite directed sequence: prepare $\lvert 0\rangle^{\otimes n}$ , apply a product of unitary gates drawn from a universal set, then measure — the whole computation is the unitary $U = U_L \cdots U_2 U_1$ acting on $\mathbb{C}^{2^n}$ followed by Born-rule sampling.

Where this lives today

The circuit model is the working interface of every quantum computer now running. Programs in Qiskit, Cirq, and other toolkits are literal gate lists compiled to a device's native set — a fixed two-qubit entangler such as CZ or the Mølmer–Sørensen gate plus arbitrary single-qubit rotations — while the compiler inserts SWAP gates to route around limited connectivity and minimizes depth to outrun decoherence. In 2019 Google's Sycamore processor ran random-circuit-sampling across 53 superconducting qubits, and later photonic and superconducting groups pushed similar "quantum computational advantage" demonstrations — each benchmarked in the language of gate depth and circuit fidelity. On the fault-tolerant frontier, the surface code expresses error correction as circuits of stabilizer measurements with classically controlled Pauli corrections, and recent below-threshold demonstrations live or die on two-qubit gate error. Even the variational algorithms driving current chemistry and optimization work — VQE, QAOA — are parametrized circuits whose angles a classical optimizer tunes. And the model still frames the open questions: which circuit families defeat classical simulation, and how deep a circuit a noisy device can run before its output is worthless.

The physical picture

Think of a circuit as a player-piano roll read left to right: the wires are the strings (the qubits), each box is a key struck at a definite moment, and the "music" is the evolving pattern of $2^n$ amplitudes. Nothing is destroyed as the roll turns — every gate merely rotates the state vector, and because that rotation is unitary the total probability mass (the squared length of the vector) is conserved at every step. Only the final chord, the measurement, forces the superposition to collapse to one definite outcome. This is why every gate has an inverse and the unitary part of any circuit can be run backwards: reversibility is a consequence of closed-system dynamics, not a design choice. The first figure is the smallest circuit showing every ingredient at once — preparation, a single-qubit gate, an entangler, and readout — the Bell-state generator, which turns the product state $\lvert 00\rangle$ into the maximally entangled pair $(\lvert 00\rangle+\lvert 11\rangle)/\sqrt 2$ .

Figure

The smallest complete circuit — the Bell generator. A Hadamard on the top wire then a CNOT turns the product state 00 into the entangled pair, so measuring gives outcome 00 or 11 each with probability one half and never 01 or 10

Two contrasts organize everything else. Entanglement enters only through multi-qubit gates: a circuit of single-qubit gates alone keeps the state a product on each wire and is trivially simulable classically — the CNOT (or any genuine two-qubit gate) is what manufactures correlation. And two costs must be tracked: the size is the total gate count, while the depth is the number of sequential layers once gates on disjoint wires run in parallel. Depth is the wall-clock time, and on real hardware it matters most, because every layer lets a little more decoherence creep in before readout. The second figure makes this anatomy concrete on a three-qubit register, and records the most error-prone fact about the model — that the operator product is written in the reverse of circuit-reading order.

The core equations

Everything begins from a fixed, unentangled starting point: by convention the register is prepared in the all-zeros computational-basis state, a product vector whose only nonzero amplitude sits on the string $00\cdots 0$ .

\lvert \psi_{\mathrm{in}}\rangle = \lvert 0\rangle^{\otimes n} = \lvert \underbrace{0\cdots 0}_{n}\rangle \qquad (1)

where: $n$ — number of qubits (wires) in the register; $\lvert 0\rangle$ — computational-basis state of a single qubit, the column vector $(1,0)^{\mathsf T}$ ; $\otimes$ — tensor (Kronecker) product combining single-qubit spaces into $\mathbb{C}^{2^n}$ . Reading it: the machine starts in a definite, correlation-free state, so all structure is put in by the gates that follow. The heart of the model is that the unitary part of the circuit is one product of operators applied in time order. Because each new gate acts on the result of the previous ones, the latest gate ends up on the far left — the operator product runs opposite to the reading order.

\lvert \psi_{\mathrm{out}}\rangle = U_L\, U_{L-1} \cdots U_2\, U_1\, \lvert \psi_{\mathrm{in}}\rangle \qquad (2)

where: $U_k$ — the $k$ -th gate lifted to the full register, a $2^n\times 2^n$ unitary; $L$ — number of gate-application steps; the operator order is reversed relative to the circuit's left-to-right reading order. Reading it: " $A$ then $B$ " is the operator $BA$ , and the net effect of the whole circuit is the single unitary $U=U_L\cdots U_1$ . A gate drawn on one wire really acts on the whole register — it is tensored with the identity on every other wire. This lifting lets a $2\times 2$ matrix operate inside a $2^n$ -dimensional space.

G^{(j)} = I^{\otimes (j-1)} \otimes G \otimes I^{\otimes (n-j)} \qquad (3)

where: $G$ — a $2\times 2$ single-qubit unitary, e.g. $H$ or a Pauli; $j$ — index of the target wire, $1\le j\le n$ (qubit 1 is the leftmost / high-order tensor factor here); $I$ — the $2\times 2$ identity on each untouched wire. Reading it: single-qubit gates are always tensor factors, which is exactly why a circuit of them alone can never entangle the wires. The gate that does entangle is the controlled-NOT. Written as a sum of control projectors, it flips the target if and only if the control is $\lvert 1\rangle$ , giving a $4\times 4$ permutation matrix.

\mathrm{CNOT} = \lvert 0\rangle\langle 0\rvert \otimes I + \lvert 1\rangle\langle 1\rvert \otimes X = \begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix} \qquad (4)

where: $\lvert 0\rangle\langle 0\rvert,\ \lvert 1\rangle\langle 1\rvert$ — projectors onto the control-qubit states; $X$ — Pauli- $X$ (bit-flip) applied to the target when the control is $\lvert 1\rangle$ ; $I$ — identity on the target when the control is $\lvert 0\rangle$ . Reading it: the control is never changed; only the target flips, and only conditionally. Measurement closes the circuit. The Born rule turns the final amplitudes into a probability distribution over the $2^n$ bit strings, which sum to one.

p(x) = \lvert \langle x \vert \psi_{\mathrm{out}}\rangle \rvert^2,\qquad \sum_{x\in\{0,1\}^n} p(x) = 1 \qquad (5)

where: $x$ — an $n$ -bit string labeling a computational-basis outcome; $\langle x\vert\psi_{\mathrm{out}}\rangle$ — amplitude of basis state $\lvert x\rangle$ in the output state; $p(x)$ — probability of observing outcome $x$ . Reading it: a quantum computer does not output a state, it outputs a sample — one bit string drawn from this distribution per run. Finally, universality is useful only because approximation error is benign: if every ideal gate is replaced by an approximation good to $\epsilon/m$ in operator norm, the whole $m$ -gate circuit is good to $\epsilon$ . Errors add — they do not multiply or explode.

\lVert U_k - V_k\rVert < \tfrac{\epsilon}{m}\ \forall k \;\Rightarrow\; \lVert U_m\cdots U_1 - V_m\cdots V_1\rVert < \epsilon \qquad (6)

where: $U_k, V_k$ — ideal gate and its physical approximation at step $k$ ; $m$ — number of gates approximated; $\epsilon$ — total operator-norm error tolerated on the whole circuit; $\lVert\cdot\rVert$ — operator (spectral) norm. Reading it: precision compiles cheaply — to hit end-to-end accuracy $\epsilon$ you need only per-gate accuracy $\epsilon/m$ , and the Solovay–Kitaev theorem says reaching that costs only $\mathrm{polylog}(m/\epsilon)$ primitives per gate.

Derivation AWhy one net unitary describes the whole circuit

The goal is to justify, from closed-system quantum dynamics, the central structural claim of the model: that no matter how many gates are stacked on however many wires, the entire pre-measurement evolution collapses to one $2^n\times 2^n$ unitary $U=U_L\cdots U_1$ , itself unitary so probability is conserved end to end. We start from the Schrödinger propagator, discretize into gate steps, fuse them by associativity, and use closure of the unitary group — after which any irreversible action is appended.

Step 1. A closed quantum system evolving under a piecewise-constant Hamiltonian $H_k$ for a duration $t_k$ has propagator $U_k = e^{-iH_k t_k/\hbar}$ , which is unitary because $H_k$ is Hermitian. An idealized gate is exactly such a propagator, engineered so that its net action is a chosen $2\times 2$ or $4\times 4$ matrix on its target wires and the identity elsewhere. Why: this is where "a gate is a physical pulse" becomes "a gate is a unitary matrix" — the two descriptions are the same object.

Step 2. Applying the gates in time order multiplies the propagators, $\lvert\psi_{\mathrm{out}}\rangle = U_L(\cdots(U_1\lvert\psi_{\mathrm{in}}\rangle))$ , and operator multiplication is associative, so the parentheses drop: $U = U_L\cdots U_1$ is a single well-defined operator. Why: associativity lets us stop thinking of a circuit as a process and treat it as one matrix — the basis of circuit-identity algebra.

Step 3. The product of unitaries is unitary: $U^\dagger U = U_1^\dagger\cdots U_L^\dagger U_L\cdots U_1 = I$ , since each adjacent $U_k^\dagger U_k$ collapses from the inside out. Hence $\langle\psi_{\mathrm{out}}\vert\psi_{\mathrm{out}}\rangle = 1$ . Why: this is norm conservation — total probability stays exactly one at every point, which is why gates are reversible.

Step 4. Any non-unitary action — measurement, reset, a classically controlled correction — is placed after this unitary block, and deferred measurement (below) lets us always push measurements to the very end without changing the output statistics. Why: this separates the reversible quantum core from the single irreversible readout — the split that makes complexity theory and error correction statable. *Verified: matches Nielsen and Chuang, sections 4.1 to 4.4, and Preskill chapter 5; group closure and norm conservation are textbook, and $U^\dagger U = I$ can be checked directly for the five-gate example of the second figure.*

Go deeper · Derivation B · 1 minCNOT builds a Bell state from a product state

Derivation BCNOT builds a Bell state from a product state

The goal is to show explicitly how the model manufactures entanglement — the resource that separates it from any classical circuit — by tracking the two-gate Bell generator $\mathrm{CNOT}_{12}(H\otimes I)$ on $\lvert 00\rangle$ amplitude by amplitude, then proving the output cannot be written as a product of single-qubit states. It is the smallest demonstration that a two-qubit gate does what no tensor product of single-qubit gates can, and the primitive behind teleportation and superdense coding.

Step 1. The Hadamard on the control spreads it into an equal superposition while leaving the target alone: $(H\otimes I)\lvert 00\rangle = \tfrac{1}{\sqrt 2}(\lvert 00\rangle+\lvert 10\rangle)$ . Why: the state is still a product — the wires are in superposition but uncorrelated, so no entanglement exists yet.

Step 2. The CNOT flips the target exactly in the $\lvert 1\rangle$ branch of the control: it fixes $\lvert 00\rangle$ and sends $\lvert 10\rangle\to\lvert 11\rangle$ , giving $\tfrac{1}{\sqrt2}(\lvert 00\rangle+\lvert 11\rangle) = \lvert\Phi^+\rangle$ . Why: the conditional flip ties target to control, converting an uncorrelated superposition into a correlated one — the exact moment entanglement is created.

Step 3. The result cannot be factored. Suppose $\lvert\Phi^+\rangle=(a\lvert 0\rangle+b\lvert 1\rangle)\otimes(c\lvert 0\rangle+d\lvert 1\rangle)$ ; matching amplitudes forces $ac=bd=\tfrac{1}{\sqrt2}$ but $ad=bc=0$ , impossible since a zero factor cannot leave both $ac$ and $bd$ nonzero. Why: this contradiction proves entanglement — no single-qubit-only circuit can ever reach this state from $\lvert 00\rangle$ . *Verified: standard Bell-state preparation, Nielsen and Chuang section 1.3.6 and figure 1.12; multiplying the $4\times 4$ CNOT of equation (4) against the column vector $\tfrac{1}{\sqrt2}(1,0,1,0)^{\mathsf T}$ returns $\tfrac{1}{\sqrt2}(1,0,0,1)^{\mathsf T}$ .*

Go deeper · Derivation C · 1 minDeferred measurement — pushing a mid-circuit readout to the end

Derivation CDeferred measurement — pushing a mid-circuit readout to the end

The goal is to prove the principle that lets us treat any circuit, even one with mid-stream measurements and classically conditioned gates, as a single coherent unitary followed by one terminal readout. We compare two circuits — measure a control then classically apply $U$ if the outcome was one, versus apply a coherent controlled- $U$ and only then measure — and show they give identical joint statistics. This equivalence makes the "one big unitary" idealization legitimate and underlies how error correction defers syndrome-conditioned corrections.

Step 1. In the coherent circuit the controlled- $U$ applies $U$ to the target only in the $\lvert 1\rangle$ branch of the control: $\mathrm{c\text{-}}U\,(\alpha\lvert 0\rangle+\beta\lvert 1\rangle)\otimes\lvert\phi\rangle = \alpha\lvert 0\rangle\lvert\phi\rangle + \beta\lvert 1\rangle\,U\lvert\phi\rangle$ . Why: entangling the control's value with whether $U$ has fired is the coherent stand-in for "decide later from the measurement".

Step 2. Now measure the control in the computational basis: outcome $0$ occurs with probability $\lvert\alpha\rvert^2$ leaving the target in $\lvert\phi\rangle$ , outcome $1$ with probability $\lvert\beta\rvert^2$ leaving it in $U\lvert\phi\rangle$ . Why: reading the control selects one entangled branch, with exactly the Born-rule weights the coherent state assigned.

Step 3. These are precisely the outcomes of the other circuit — measure the control first, obtaining $0$ (do nothing) or $1$ (then classically apply $U$ ). The joint distribution is identical, so the circuits are interchangeable and measurements may always be deferred. Why: because only end-of-circuit statistics matter, every circuit may be analyzed as one unitary plus a terminal measurement. *Verified: principle of deferred measurement, Nielsen and Chuang section 4.4, figure 4.13; the two branch weights and conditional target states agree term by term.*

Limiting cases

Restricting which gates are allowed carves the model down to familiar, sometimes classically tractable, regimes — a map of where quantum power comes from.

Case	Result	Meaning
Single-qubit gates only	$U = U_1 \otimes U_2 \otimes \cdots \otimes U_n$	No entanglement is ever created; the state stays a product on each wire and the circuit is trivially classically simulable.
Clifford gates only	$\{H, S, \mathrm{CNOT}\}$	By the Gottesman–Knill theorem these are efficiently classically simulable despite producing entanglement; a non-Clifford gate such as $T$ is needed for any quantum advantage.
Permutation (reversible classical) gates	$\mathrm{NOT},\ \mathrm{CNOT},\ \mathrm{Toffoli}$	Basis-permuting gates on basis-state inputs reproduce ordinary reversible classical computation — no superposition is exploited.
One layer, then measure	$\text{depth}=1$	Even constant-depth circuits (IQP, the $p{=}1$ QAOA) exhibit correlations believed hard to sample classically — depth alone does not bound the model's power.

Common trapThe circuit reads left to right but the operators multiply right to left

The most common source of a wrong matrix is confusing circuit order with operator order. A circuit that applies gate $A$ first and then $B$ is the operator $BA$ , not $AB$ , because $B$ acts on the result of $A$ — the later gate stands to the left. Two traps compound it: gates do not commute in general ( $HX \ne XH$ ), so order matters; and you must fix which qubit is the high-order tensor factor and hold it constant, or $\mathrm{CNOT}_{12}$ versus $\mathrm{CNOT}_{21}$ comes out transposed. Always read a diagram into operators right to left, writing $\lvert\psi_{\mathrm{out}}\rangle = U_L\cdots U_1\lvert\psi_{\mathrm{in}}\rangle$ with the last-applied gate leftmost.

Worked examples

1 · A three-qubit GHZ state, fully worked (confidence builder)

Run the circuit " $H$ on qubit 1, then $\mathrm{CNOT}_{12}$ , then $\mathrm{CNOT}_{23}$ " on $\lvert 000\rangle$ . Find the output state and the probability of every measurement outcome.

Step 1. Apply the Hadamard to the first wire: $H\lvert 0\rangle = \tfrac{1}{\sqrt2}(\lvert 0\rangle+\lvert 1\rangle)$ , so the register becomes $\tfrac{1}{\sqrt2}(\lvert 000\rangle+\lvert 100\rangle)$ . The other two wires are untouched, and the state is still a product.

Step 2. Apply $\mathrm{CNOT}_{12}$ (control 1, target 2), which flips wire 2 wherever wire 1 is $1$ : $\lvert 000\rangle$ is fixed and $\lvert 100\rangle\to\lvert 110\rangle$ , giving $\tfrac{1}{\sqrt2}(\lvert 000\rangle+\lvert 110\rangle)$ .

Step 3. Apply $\mathrm{CNOT}_{23}$ (control 2, target 3), which flips wire 3 wherever wire 2 is $1$ : $\lvert 000\rangle$ is fixed and $\lvert 110\rangle\to\lvert 111\rangle$ , giving the Greenberger–Horne–Zeilinger state $\lvert\mathrm{GHZ}\rangle = \tfrac{1}{\sqrt2}(\lvert 000\rangle+\lvert 111\rangle)$ .

Step 4. Born rule: only two strings have nonzero amplitude, each $1/\sqrt2$ , so $p(000)=\lvert 1/\sqrt2\rvert^2 = \mathbf{0.50}$ and $p(111)=\mathbf{0.50}$ , while $p(x)=0$ for the other six; they sum to $1$ . Measuring any one qubit gives $0$ or $1$ with equal odds and instantly fixes the other two to match — perfect three-way correlation from a two-gate chain. Output $\tfrac{1}{\sqrt2}(\lvert 000\rangle+\lvert 111\rangle)$ ; only 000 and 111 appear, each with probability 0.50.

2 · The Bell generator as an explicit 4×4 matrix

Compute the net operator $U=\mathrm{CNOT}\,(H\otimes I)$ of the Bell circuit as a single matrix, apply it to $\lvert 00\rangle$ , and confirm it is unitary — a drill in operator ordering.

Step 1. With $H=\tfrac{1}{\sqrt2}\big(\begin{smallmatrix}1&1\\1&-1\end{smallmatrix}\big)$ the lift is $H\otimes I = \tfrac{1}{\sqrt2}\big(\begin{smallmatrix}1&0&1&0\\0&1&0&1\\1&0&-1&0\\0&1&0&-1\end{smallmatrix}\big)$ , and CNOT is the permutation of equation (4). Because the Hadamard is applied first, it stands on the right of the product.

Step 2. Multiply $U=\mathrm{CNOT}\,(H\otimes I)$ : CNOT swaps its last two rows, so $U$ keeps rows $0,1$ of $H\otimes I$ and swaps rows $2,3$ , giving $U = \tfrac{1}{\sqrt2}\big(\begin{smallmatrix}1&0&1&0\\0&1&0&1\\0&1&0&-1\\1&0&-1&0\end{smallmatrix}\big)$ .

Step 3. Apply it to $\lvert 00\rangle = (1,0,0,0)^{\mathsf T}$ : only the first column survives, giving $\tfrac{1}{\sqrt2}(1,0,0,1)^{\mathsf T} = \tfrac{1}{\sqrt2}(\lvert 00\rangle+\lvert 11\rangle)=\lvert\Phi^+\rangle$ , matching the derivation.

Step 4. Check unitarity by column norms and orthogonality: each column has squared norm $\tfrac12(1+1)=1$ , and any two distinct columns are orthogonal (columns $0$ and $2$ give $\tfrac12(1-1)=0$ ). Hence $U^\dagger U = I$ . $U=\tfrac{1}{\sqrt2}\big(\begin{smallmatrix}1&0&1&0\\0&1&0&1\\0&1&0&-1\\1&0&-1&0\end{smallmatrix}\big)$ is unitary and sends $\lvert 00\rangle\to\lvert\Phi^+\rangle$ .

3 · A precision budget for gate approximation

A quantum algorithm compiles to $m=1000$ ideal gates, but the hardware realizes each only approximately. What per-gate accuracy keeps the whole circuit within total operator-norm error $\epsilon=0.01$ ?

Step 1. Use the additive bound of equation (6): the total error is at most the sum of per-gate errors, $\lVert U_m\cdots U_1 - V_m\cdots V_1\rVert \le \sum_{k}\lVert U_k-V_k\rVert$ , so it suffices that each gate obey $\lVert U_k-V_k\rVert < \epsilon/m$ .

Step 2. Plug in: $\epsilon/m = 0.01/1000 = \mathbf{10^{-5}}$ . Compiling each gate to accuracy $10^{-5}$ keeps the end-to-end error below $0.01$ , and by Solovay–Kitaev that costs only $O(\log^{c}(1/\delta))$ primitives per gate ( $c$ between about $1.4$ and $4$ ) — polylogarithmic overhead. Per-gate accuracy $10^{-5}$ suffices at $\mathrm{polylog}(1/\epsilon)$ cost per gate; precision is cheap, which is why a finite gate set is enough.

Physics of the portrait

The circuit model did not fall out of engineering; it was invented as a piece of theoretical physics, by asking what a computer built from the actual laws of quantum mechanics could do that a classical one could not.

Origins · 1 minDavid Deutsch and how this was discovered

David Deutsch

b. 1953 · founder of the universal quantum computer and the quantum-network model

David Deutsch, at Oxford in the early 1980s, took a question that had floated at the edges of physics — is computation constrained by physical law? — and answered it by building the first genuinely quantum model of a computer. Where Benioff had shown in 1980 that a Turing machine could run reversibly on quantum parts, and Feynman had argued in 1981 that simulating quantum systems seemed to demand a quantum machine, Deutsch's 1985 paper defined the universal quantum computer: a quantum Turing machine whose tape and head obey the Schrödinger equation and which can simulate any physical process to arbitrary accuracy. He grounded it in a sharpened Church–Turing thesis — every finitely realizable physical system can be simulated by a universal machine — so computability became a statement about physics. In 1989 he recast that cumbersome tape machine into the far more usable quantum computational network: qubits on wires, transformed by a discrete gate set, read out at the end — the circuit model of every laboratory and textbook today. He proved a small gate set universal and exhibited the first algorithm (the Deutsch problem, later Deutsch–Jozsa) with a provable speedup over any classical method, turning "quantum computer" from curiosity into concrete object. Yao's 1993 proof that quantum circuits and quantum Turing machines are polynomially equivalent then made Deutsch's network the standard definition of quantum computation — the frame in which Shor and Grover would soon write their algorithms.

History

1980

— Benioff describes a quantum-mechanical Hamiltonian model of a reversible Turing machine

1985

— Deutsch defines the universal quantum computer and the quantum Turing machine

1989

— Deutsch introduces quantum computational networks, the circuit model itself

1993

— Yao proves quantum circuits and quantum Turing machines are polynomially equivalent

1995

— Barenco and coworkers show CNOT plus single-qubit gates are universal

Going further

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information, ch. 4 (quantum circuits) · Preskill, Lecture Notes on Quantum Computation, ch. 5–6 · Watrous, The Theory of Quantum Information, ch. 1–2 · Kitaev, Shen and Vyalyi, Classical and Quantum Computation, ch. 8 · Mermin, Quantum Computer Science, ch. 2 · Wilde, Quantum Information Theory, ch. 3–4.

Provenance. Every equation here is standard and independently checkable. The net-unitary product and the additive error bound are Nielsen and Chuang sections 4.1 to 4.5 and Preskill chapter 5; the CNOT matrix and Bell-state preparation are Nielsen and Chuang sections 1.3.6 and 4.3; the Born rule and projective readout are Nielsen and Chuang section 2.2 and Wilde chapter 4; deferred measurement is Nielsen and Chuang section 4.4; the Gottesman–Knill result on Clifford circuits is Nielsen and Chuang section 10.5.4; the Solovay–Kitaev theorem is Nielsen and Chuang appendix 3 and Dawson–Nielsen (2006). A verifier should multiply the $4\times 4$ CNOT against $(H\otimes I)\lvert 00\rangle$ to confirm $\lvert\Phi^+\rangle$ , check $U^\dagger U = I$ for a gate product, evaluate the GHZ amplitudes, and confirm the $\epsilon/m$ budget arithmetic.

Prerequisites. Qubit and State Vectors · Tensor Product of Hilbert Spaces · Unitary Operators · Measurement and the Born Rule. Leads to. Universal Gate Sets · CNOT Gate · Circuit Identities and Equivalences · Single-Qubit Rotation Gates.

Ask the tutor: ask me to hand-trace any small circuit gate by gate — Bell, GHZ, teleportation, or your own — and I will show the state after every layer and the final measurement probabilities.

Why is the operator product written in the reverse order of the circuit diagram?

Because operators act on what is to their right. If you apply gate $A$ first and gate $B$ second, then $B$ acts on the state $A$ already produced, so the composite is $B(A\lvert\psi\rangle)=(BA)\lvert\psi\rangle$ — the later-applied gate ends up on the left. Diagrams run left-to-right in time because that reads naturally, but algebra composes right-to-left, so a circuit " $A$ then $B$ then $C$ " is the operator $CBA$ . The reliable habit is to translate a diagram into operators by scanning right to left, writing $U_L\cdots U_1\lvert\psi_{\mathrm{in}}\rangle$ with the last gate leftmost. Getting this backwards is the most common bookkeeping error in the subject.

What is the difference between a circuit's depth and its size, and why does depth matter more on hardware?

Size is the total gate count; depth is the number of sequential time-steps once gates on disjoint qubits are packed into the same layer and run in parallel. A thousand single-qubit gates spread over a thousand separate wires has size $1000$ but depth $1$ . Depth matters more on real machines because it is the wall-clock duration, and every extra layer gives the qubits more time to decohere before the answer is read out. Compilers therefore work to minimize depth, trading a few extra gates for fewer layers whenever coherence time is the binding constraint.

If a finite gate set can only approximate an arbitrary unitary, how can quantum computation be exact?

It cannot be perfectly exact, and it need not be. A universal finite set such as $\{H, T, \mathrm{CNOT}\}$ can bring the circuit's unitary within any operator-norm distance $\epsilon$ of the target, and errors add only additively: to hit total error $\epsilon$ across $m$ gates you compile each to accuracy $\epsilon/m$ . The Solovay–Kitaev theorem then guarantees reaching per-gate accuracy $\delta$ costs only $\mathrm{polylog}(1/\delta)$ primitives — a mild overhead, not an exponential blowup. Since the final step of any algorithm is a probabilistic measurement read out over many repetitions anyway, a sufficiently small $\epsilon$ is operationally indistinguishable from exact.

Does measurement have to happen only at the end of a circuit?

No — real devices do measure mid-circuit, for error-correction syndromes and measurement-based feed-forward — but the principle of deferred measurement guarantees you may always analyze a circuit as if every measurement were at the end. Any measurement followed by a classically controlled gate can be replaced by a coherent controlled gate followed by a terminal measurement, with identical statistics. This lets theory treat the whole computation as one big unitary plus a final readout, which is what makes the clean "prepare, evolve unitarily, measure" picture legitimate even for circuits that physically interleave gates and measurements.

Is the quantum circuit model more or less powerful than other models like adiabatic or measurement-based computing?

Exactly as powerful, up to polynomial overhead. The circuit model, the quantum Turing machine, the measurement-based (one-way) model, the adiabatic model, and the topological model are all polynomial-time equivalent: any computation efficient in one is efficient in all, so they define the same class BQP. They differ only in what they make natural — measurement-based computing consumes a pre-made cluster state by single-qubit measurements, adiabatic computing encodes the answer in a Hamiltonian's ground state — but none is fundamentally stronger. The circuit model is simply the most direct to reason about and the closest match to gate-based hardware, which is why it is the field's default language.

Why is CNOT singled out as the entangling gate — are there others?

CNOT is not unique; it is representative. Almost any genuine two-qubit gate that is not merely a product of single-qubit gates can serve as the entangler — CZ, iSWAP, the Mølmer–Sørensen gate, a generic controlled- $U$ all work — and a foundational result (Barenco and coworkers, 1995) shows CNOT plus arbitrary single-qubit gates is universal. CNOT gets top billing because it is the simplest to write, a clean permutation of basis states, and it makes the mechanism transparent: it flips the target conditioned on the control, exactly the correlation-creating step. Different hardware implements different native two-qubit gates, and the compiler converts between them using circuit identities.