The Quantum Circuit Model

A quantum circuit on $n$ qubits is specified by three ingredients: a register of $n$ wires, each initialized to a fixed basis state (conventionally $|0\rangle$); a finite ordered list of gates, each a unitary operator acting on one or a few designated wires; and a specification of which wires are measured, and when. The state of the whole register at any moment is a vector in the $2^n$-dimensional Hilbert space $(\mathbb{C}^2)^{\otimes n}$, and a gate acting on a subset $S$ of wires is really the operator $U_S \otimes I_{\bar S}$ acting on the full space, where $I_{\bar S}$ is the identity on the untouched wires. The crucial conceptual point — and the one that most needs care — is time-ordering. A circuit diagram is read left to right as time, not as an algebraic expression. If gate $A$ is drawn before gate $B$ on overlapping wires, the state after both gates is $B \cdot A \cdot |\psi\rangle$ as a matrix product, i.e. gates compose in reverse textual order, exactly as function composition $(g \circ f)(x) = g(f(x))$ reads $f$ first even though $g$ is written first. This convention is a common source of sign and ordering errors and deserves to be stated as a theorem-like fact: if a circuit consists of gates $G_1, G_2, \dots, G_m$ applied in that temporal order, the resulting unitary is

Two gates that act on disjoint sets of wires automatically commute, since $(A\otimes I)(I\otimes B) = (I \otimes B)(A \otimes I) = A \otimes B$. This is why circuit diagrams may legitimately draw gates on different wires "at the same horizontal position" without ambiguity — their relative order genuinely does not matter, and a circuit can be organized into layers (or time steps) of mutually commuting, wire-disjoint gates. The number of layers needed is the circuit's depth, distinguished from its size, the total gate count; depth models parallel execution time on hardware that can apply many gates simultaneously, while size models total physical resource cost.

Measurement breaks unitarity by design. A measurement of a qubit in the computational basis is described by two projectors $\Pi_0 = |0\rangle\langle 0|$ and $\Pi_1 = |1\rangle\langle 1|$; outcome $b$ occurs with probability $\langle\psi|\Pi_b|\psi\rangle$, and the post-measurement state collapses to $\Pi_b|\psi\rangle / \sqrt{\langle\psi|\Pi_b|\psi\rangle}$. Measurement can be placed at the very end of a circuit (the default, "measure-at-the-end" convention used to define quantum complexity classes), or mid-circuit, in which case the classical outcome bit may be fed forward to control later gates — a classically-controlled gate. The principle of deferred measurement (a foundational fact developed alongside Reversibility of Quantum Computation) states that any mid-circuit measurement followed by classically-controlled unitaries can be replaced by controlled quantum gates and a single measurement at the end, without changing the output distribution; this justifies treating "measure-at-the-end" circuits as the canonical, fully general model.

Building and simulating a circuit mechanically proceeds by tracking the full state vector (for small $n$) or, for reasoning about correctness, by symbolic composition of unitaries. The general recipe: 1. Initialize the register: $|\psi_0\rangle = |0\rangle^{\otimes n}$ (or another fixed product state). 2. Apply gates in temporal order. For each gate $G$ acting on wire subset $S$, update $|\psi_i\rangle = (G_{S} \otimes I_{\bar S})\,|\psi_{i-1}\rangle$, where the tensor factors are arranged according to which physical wires $S$ picks out (not necessarily contiguous). 3. Handle classical controls. If a gate is controlled on a previously measured classical bit $c$, apply $G$ iff $c=1$, else apply identity. 4. Measure the designated wires (possibly all, possibly a subset) at the end (or, under deferred measurement, replace mid-circuit measurements with controlled unitaries and measure everything at the end). 5. Output the classical bit string of measurement outcomes; this is the actual "answer" of the computation, and for probabilistic algorithms the circuit may be run many times to estimate a distribution. The pseudocode below makes explicit how a classical simulator executes an arbitrary circuit — this is exactly the semantics that any physical implementation must reproduce, up to the state being a genuine quantum amplitude vector rather than an explicitly stored classical array (a distinction developed further under Quantum vs Classical Parallelism). ``` function SIMULATE_CIRCUIT(n, ops):

# n: number of qubits

# ops: ordered list of operations, each one of:

# ("gate", U, wires) -- unitary U applied to given wires

# ("measure", wire, classical_reg) -- projective measurement, outcome stored

# ("cgate", U, wires, classical_reg, bit) -- apply U to wires iff classical_reg == bit state = KRON(|0>, |0>, ..., |0>) # length-2^n amplitude vector classical = {} # map: register name -> measured bit for op in ops: if op.type == "gate": state = APPLY_UNITARY(state, op.U, op.wires, n) elif op.type == "cgate": if classical[op.classical_reg] == op.bit: state = APPLY_UNITARY(state, op.U, op.wires, n)

# else: identity, do nothing elif op.type == "measure": p1 = SUM_OF_SQUARED_AMPLITUDES(state, op.wire, outcome=1) outcome = SAMPLE_BERNOULLI(p1) state = PROJECT_AND_RENORMALIZE(state, op.wire, outcome) classical[op.classical_reg] = outcome return classical, state function APPLY_UNITARY(state, U, wires, n):

# Conceptually build U ⊗ I on the full 2^n-dim space, respecting wire order,

# then left-multiply. Efficient implementations act only on the amplitudes

# indexed by the chosen wires, in O(2^n · |U|) time, never forming the full matrix. return FullOperator(U, wires, n) * state ``` Note the deliberate separation: `"gate"` steps are always applied regardless of any classical data (pure unitary evolution), while `"cgate"` steps model the classically-controlled operations that arise from mid-circuit measurement and feedback — precisely the two building blocks the deferred-measurement principle shows are interchangeable with a measure-at-the-end-only circuit. The figure below shows a small but genuinely structural circuit — three qubits, a mix of single- and two-qubit gates arranged in layers, and a terminal measurement — annotated with wire indices and time steps to make the temporal-order convention concrete.

Reading the diagram: at $t=1$, $H$ on $q_0$ and $X$ on $q_2$ act on disjoint wires and commute — this is one layer. At $t=2$, a CNOT entangles $q_0$ (control) and $q_1$ (target). At $t=3$, an $R_z(\theta)$ on $q_1$ and a $T$ gate on $q_2$ again share a layer since their wires are disjoint. At $t=4$, a CNOT entangles $q_1$ and $q_2$. The overall unitary before measurement is

each factor implicitly tensored with identity on the untouched wire — read right to left, matching the left-to-right diagram.

Size and depth as complexity measures. The size of a circuit is the number of gates it contains; the depth is the number of layers of mutually commuting, wire-disjoint gates needed, i.e. the length of the longest chain of gates that must be applied in strict sequence because they share a wire. Formally, build a dependency graph where gates are nodes and an edge $G_i \to G_j$ ($i<j$) exists if they act on a common wire and no gate between them on that wire separates them; depth is the longest path in this DAG. Depth lower-bounds the circuit's running time on any hardware model that can execute non-overlapping gates in parallel, while size lower-bounds the total number of physical operations (relevant when gates, not time, are the scarce resource, e.g. due to decoherence-limited gate budgets).

Why time-ordering composition is correct. This is not a convention chosen for convenience — it is forced by the axioms of quantum mechanics. Time evolution under a sequence of instantaneous unitary "kicks" $G_1$ then $G_2$ obeys the Schrödinger-equation limit in which each kick multiplies the current state vector on the left: $|\psi_1\rangle = G_1|\psi_0\rangle$, then $|\psi_2\rangle = G_2|\psi_1\rangle = G_2 G_1 |\psi_0\rangle$. Induction on the number of gates gives the general claim: for a circuit with gates $G_1,\dots,G_m$ applied in that order,

so the circuit implements the unitary $U = G_m \cdots G_1$, matrix multiplication composed in reverse diagrammatic order. This is exactly the same logic as composing functions $f_1$ then $f_2$: you write $f_2(f_1(x))$, not $f_1(f_2(x))$.

Why the layering (commutation) claim is correct. If gates $A$ (on wire set $S_A$) and $B$ (on $S_B$) have $S_A \cap S_B = \varnothing$, then as operators on the full $n$-qubit space, $A$ really means $A \otimes I_{\bar{S_A}}$ and $B$ means $I_{\bar{S_B}} \otimes B$ (with tensor factors reordered to match wire positions). Since $A$ acts only on the $S_A$ factors and $B$ acts only on the (disjoint) $S_B$ factors, and every operator commutes with the identity on any wire it doesn't touch, $AB = BA$ as full operators. This is precisely why depth can be smaller than size: independent gates collapse into shared layers, and the DAG longest-path computation runs in $O(\text{size})$ time via a topological scan tracking, for each wire, the depth of the last gate seen on it.

Correctness of the deferred-measurement replacement. Suppose a circuit measures wire $w$ mid-computation, obtaining outcome $b$ with probability $p_b = \langle\psi|\Pi_b|\psi\rangle$, and later applies gate $G$ conditioned on $b$. Replace this by: do not measure yet; instead apply a controlled-$G$ gate using $w$ itself as the control qubit, then measure $w$ at the end (after everything else). Because controlled-$G$ acts as $I \otimes I$ on the $b=0$ branch and $I\otimes G$ on the $b=1$ branch, and because the reduced statistics of any later measurement on the other wires are computed by summing over the (now-deferred) outcome of $w$ exactly as the Born rule would have summed over the earlier measurement outcome, the two circuits induce identical output distributions on all other measured wires. This holds because tracing out (ignoring) a qubit gives the same reduced density matrix whether you measure it early or defer the measurement to the end — a fact usually proved formally via the partial trace and the no-signaling structure of quantum channels. The upshot: circuits with mid-circuit measurement and classical feedback have exactly the same computational power as unitary-only circuits followed by a single terminal measurement, which is why textbooks can define quantum complexity classes using the simpler measure-at-the-end model without loss of generality.

Honest tradeoffs. The circuit model assumes gates are exact, wires are noiseless, and any two-qubit gate can be applied between any pair of wires regardless of physical distance — none of which literally holds on real hardware. Real devices have restricted connectivity (requiring extra SWAP gates that inflate size and depth), noisy gates (requiring Universal Gate Sets with fault-tolerant encodings), and finite coherence time (making depth, not just size, the binding constraint). The abstract circuit model is nonetheless the right level of idealization for algorithm design and asymptotic complexity, in the same way the classical RAM model abstracts away cache hierarchies.

Trace the 3-qubit circuit from the diagram on a concrete input, choosing $\theta = \pi/2$ so $R_z(\pi/2) = \text{diag}(1, i)$ up to the usual phase convention, i.e. $R_z(\theta)|0\rangle = |0\rangle$, $R_z(\theta)|1\rangle = e^{i\theta}|1\rangle$. Start from $|\psi_0\rangle = |000\rangle$ (writing kets as $|q_0 q_1 q_2\rangle$).

Working through the middle steps explicitly:

• Step 1: $H|0\rangle_0 = \tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)$ on $q_0$; $X|0\rangle_2 = |1\rangle$ on $q_2$; $q_1$ untouched at $|0\rangle$. Product state: $\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)_0 \otimes |0\rangle_1 \otimes |1\rangle_2 = \tfrac{1}{\sqrt2}(|001\rangle+|101\rangle)$.
• Step 2: CNOT flips $q_1$ whenever $q_0=1$: the $|001\rangle$ term ($q_0=0$) is untouched; the $|101\rangle$ term ($q_0=1$) becomes $|111\rangle$. Result $\tfrac{1}{\sqrt2}(|001\rangle+|111\rangle)$.
• Step 3: apply $R_z(\pi/2)$ to $q_1$ and $T=\text{diag}(1,e^{i\pi/4})$ to $q_2$, term by term. For $|001\rangle$ ($q_1=0,q_2=1$): $R_z$ leaves the $q_1=0$ amplitude unchanged, $T$ multiplies the $q_2=1$ amplitude by $e^{i\pi/4}$. For $|111\rangle$ ($q_1=1,q_2=1$): $R_z$ multiplies by $e^{i\pi/2}=i$, $T$ multiplies by $e^{i\pi/4}$. Result: $\tfrac{1}{\sqrt2}\big(e^{i\pi/4}|001\rangle + i\,e^{i\pi/4}|111\rangle\big)$.
• Step 4: CNOT flips $q_2$ whenever $q_1=1$: $|001\rangle$ ($q_1=0$) is untouched; $|111\rangle$ ($q_1=1$) becomes $|100\rangle$. Result: $\tfrac{e^{i\pi/4}}{\sqrt2}\big(|001\rangle + i|100\rangle\big)$.
• Step 5: since $|001\rangle$ and $|100\rangle$ are orthonormal basis states with equal magnitude amplitudes $\tfrac{1}{\sqrt2}$ (the global phase $e^{i\pi/4}$ and the phase $i$ on the second term don't affect measurement probabilities), the Born rule gives outcome $001$ with probability $\left|\tfrac{1}{\sqrt2}\right|^2 = 1/2$ and outcome $100$ with probability $1/2$.

This traces both the entanglement structure (the two CNOTs correlate all three qubits, so no single-qubit description survives past step 2) and the role of relative phase (the $i$ factor from $R_z$ is invisible in the final measurement statistics here, but would matter if a further interfering gate were applied before measurement) — illustrating precisely why circuit semantics must track full complex amplitudes, not just probabilities, until the terminal measurement.

The circuit model crystallized the idea that quantum computation could be described with the same clean, composable, resource-counting formalism that made classical circuit complexity tractable, translating decades of circuit-complexity intuition into the quantum setting.

Every quantum programming framework in production use — Qiskit, Cirq, Q#, PennyLane, Braket — represents programs internally as quantum circuits: lists of gates on named qubit registers with explicit measurement operations, precisely the object formalized here. Hardware vendors (superconducting-qubit systems, trapped-ion systems, photonic systems) all expose their machines through a circuit-level interface, and their compilers perform exactly the kind of layering, depth-minimization, and wire-routing analysis described above to fit an abstract circuit onto physically constrained connectivity. Quantum error-correcting codes are themselves described as circuits (encoding, syndrome-extraction, and correction gates interleaved with measurement), and estimates of "how many physical qubits and how much time" a fault-tolerant algorithm needs are literally circuit-size and circuit-depth calculations. The formal notion of quantum polynomial time (the class BQP) is defined as the set of problems solvable by a family of circuits, one per input length, whose size grows polynomially — making the circuit model not just an implementation detail but the very object complexity theorists use to define what "efficient quantum computation" means.

Ask the tutor: How does the choice of mid-circuit versus deferred measurement affect qubit-count and depth tradeoffs in real quantum error-correction circuits?