Simple Algorithm
Quantum Computing · Excited State · 20 min

The Circuit Model

Reading circuits, depth and width, measurement and classical control.

A quantum program is a picture: wires for qubits, boxes for gates, meters for measurements. Learn to read that picture as linear algebra, to price it in size, depth and width, and to see why every measurement can be postponed to the very end.

What you’ll learn

  • Translate a circuit diagram into a product of tensor-product unitaries, in the correct order.
  • Compute the size, depth and width of a circuit, and explain uniform circuit families and the definition of BQP.
  • Measure in any Pauli basis with basis changes, and prove the principle of deferred measurement.
  • Explain the principle of implicit measurement, and why scratch qubits must be uncomputed before interference.

Reading a circuit

A circuit is read left to right in time. Each horizontal wire carries one qubit (top wire = qubit 0 = leftmost bit of a ket), each box is a gate, and gates in the same time slice act on different qubits, so they combine by the tensor product.

The catch: operators act on kets from the left, so the matrix of a circuit is written in the reverse of reading order.

gates G1,G2,…,Gm (left to right)⟹U=Gm⋯G2 G1\text{gates } G_1, G_2, \dots, G_m\ \text{(left to right)}\quad\Longrightarrow\quad U = G_m\cdots G_2\,G_1
The first gate in time is the rightmost factor. A time slice with AA on qubit 0 and BB on qubit 1 contributes A⊗BA\otimes B.
DerivationExample: the Bell circuit as a matrix
  1. U=CNOT0→1 (H⊗I)U = \mathrm{CNOT}_{0\to1}\,(H\otimes\id)

    HH on qubit 0 comes first in time, so it is the right factor.

  2. (H⊗I)∣00⟩=12(∣00⟩+∣10⟩)(H\otimes\id)\ket{00} = \tfrac{1}{\sqrt2}\big(\ket{00}+\ket{10}\big)

    HH acts on the left tensor factor only.

  3. CNOT0→1 12(∣00⟩+∣10⟩)=12(∣00⟩+∣11⟩)=∣Φ+⟩\mathrm{CNOT}_{0\to1}\,\tfrac{1}{\sqrt2}\big(\ket{00}+\ket{10}\big) = \tfrac{1}{\sqrt2}\big(\ket{00}+\ket{11}\big) = \ket{\Phi^+}

    The control (qubit 0) is 11 in the second term, so the target flips: a Bell state.

  4. U=12(10100101010−110−10)U = \frac{1}{\sqrt2}\begin{pmatrix}1&0&1&0\\0&1&0&1\\0&1&0&-1\\1&0&-1&0\end{pmatrix}

    Column jj is the image of the jj-th basis state ∣00⟩,∣01⟩,∣10⟩,∣11⟩\ket{00},\ket{01},\ket{10},\ket{11}.

Check your understanding

A one-qubit circuit applies XX, then HH. Which matrix does it implement, and what does it do to ∣0⟩\ket0?

  1. XHXH, giving ∣+⟩\ket{+}
  2. HXHX, giving ∣−⟩\ket{-}
  3. HXHX, giving ∣+⟩\ket{+}
  4. X⊗HX\otimes H, giving ∣1⟩∣+⟩\ket{1}\ket{+}
Show the answer

B. HXHX, giving ∣−⟩\ket{-}

The first gate is the rightmost factor: U=HXU=HX, and HX∣0⟩=H∣1⟩=∣−⟩HX\ket0 = H\ket1 = \ket-. Reading order would give XH∣0⟩=X∣+⟩=∣+⟩XH\ket0 = X\ket+ = \ket+, a different state.

Size, depth and width

Depth matters because idle qubits keep decohering. Take the nn-qubit GHZ state 12(∣0⋯0⟩+∣1⋯1⟩)\tfrac{1}{\sqrt2}(\ket{0\cdots0}+\ket{1\cdots1}). The chain H0H_0, CNOT0→1\mathrm{CNOT}_{0\to1}, CNOT1→2\mathrm{CNOT}_{1\to2}, … has depth nn. Doubling is better: after H0H_0, copy qubit 0 into qubit 1; then 0→20\to2 and 1→31\to3 in parallel; then four CNOTs in parallel; and so on. Each layer doubles the size of the GHZ block.

Predict before you look

With the doubling strategy and any-to-any connectivity, what is the depth of a 16-qubit GHZ preparation, counting the initial HH as one layer?

Show the answer

5 layers

One HH layer, then CNOT layers growing the GHZ block 1→2→4→8→161\to2\to4\to8\to16: four layers. The total is 1+log⁡216=51+\log_2 16 = 5, versus 1616 for the chain. Without measurements, depth Ω(log⁡n)\Omega(\log n) is in fact unavoidable, by a light-cone argument (see the deferred-measurement deep dive).

Circuit families and BQP

An algorithm is not one circuit but a family {Cn}\{C_n\}, one circuit for each input length nn. The family must be uniform: a classical algorithm, given nn, prints a description of CnC_n in time poly⁡(n)\poly(n). Without uniformity the family could smuggle uncomputable advice into its gate choices (say, circuits that "know" whether the nn-th Turing machine halts), just as non-uniform classical circuit families can.

Think first The definition only asks for polynomial size. Why is it fine to ignore depth and width there?

Both are controlled by the size: a circuit with ss gates has depth at most ss, and since each gate touches a bounded number of qubits, at most O(s)\order{s} wires beyond the input do anything (untouched ancillas are irrelevant). So "polynomial size" already means polynomial time and polynomial memory. Depth and width become important for finer questions, such as what shallow circuits can do, or how many physical qubits an algorithm needs.

Measurement and classical control

A meter on a wire is a measurement in the computational basis; afterwards the wire carries a classical bit, drawn as a double line. To measure anything else, rotate first:

To measureCircuitWhy it works
ZZ (computational basis)meterOutcomes ∣0⟩\ket0, ∣1⟩\ket1.
XXHH, then meterHH maps ∣±⟩→∣0⟩,∣1⟩\ket\pm\to\ket0,\ket1.
YYS†S^\dagger, HH, then meterS†S^\dagger maps ∣±i⟩→∣±⟩\ket{\pm i}\to\ket\pm.
Z⊗ZZ\otimes Z (parity)CNOTs from both qubits into an ancilla ∣0⟩\ket0, then meter the ancillaThe ancilla ends in ∣x1⊕x2⟩\ket{x_1\oplus x_2}; superpositions within each parity class survive.
Check your understanding

Your device only measures in the computational basis. Which circuit sends ∣+i⟩\ket{+i} to outcome 00 and ∣−i⟩\ket{-i} to outcome 11 with certainty?

  1. HH, then measure
  2. S†S^\dagger, then HH, then measure
  3. SS, then HH, then measure
  4. HH, then S†S^\dagger, then measure
Show the answer

B. S†S^\dagger, then HH, then measure

S†∣±i⟩=∣±⟩S^\dagger\ket{\pm i} = \ket{\pm} and then H∣±⟩=∣0⟩,∣1⟩H\ket\pm = \ket0,\ket1. Basis change first, then the ZZ measurement.

A classically controlled gate acts only if a measured bit is 11. In teleportation, Bob applies Xm1X^{m_1} and then Zm0Z^{m_0} after receiving Alice's outcomes m0,m1m_0,m_1. Hardware that measures mid-circuit and reacts in real time ("dynamic circuits") is essential for error correction. Yet, in principle, a quantum computer never needs it.

Deferred measurement

DerivationProof for one measurement and one controlled gate
  1. ∣Ψ⟩=∣0⟩A∣ϕ0⟩B+∣1⟩A∣ϕ1⟩B\ket\Psi = \ket{0}_A\ket{\phi_0}_B + \ket{1}_A\ket{\phi_1}_B

    Any state, split by the value of the qubit AA that will be measured; the ∣ϕm⟩\ket{\phi_m} are unnormalized.

  2. measure A, then apply Um to B:Pr⁡(m)=∥ϕm∥2,∣m⟩⊗Um∣ϕm⟩∥ϕm∥\text{measure }A\text{, then apply }U^{m}\text{ to }B:\qquad\Pr(m) = \norm{\phi_m}^2,\qquad\ket{m}\otimes\frac{U^m\ket{\phi_m}}{\norm{\phi_m}}

    Classical control: UU acts only on outcome 11.

  3. controlled-U, then measure A:∣0⟩∣ϕ0⟩+∣1⟩U∣ϕ1⟩ ⇒ Pr⁡(m)=∥Umϕm∥2=∥ϕm∥2\text{controlled-}U\text{, then measure }A:\qquad\ket0\ket{\phi_0}+\ket1U\ket{\phi_1}\ \Rightarrow\ \Pr(m) = \norm{U^m\phi_m}^2 = \norm{\phi_m}^2

    The same probabilities, because UU is unitary…

  4. post-measurement state:∣m⟩⊗Um∣ϕm⟩∥ϕm∥\text{post-measurement state:}\qquad\ket{m}\otimes\frac{U^m\ket{\phi_m}}{\norm{\phi_m}}

    …and the same post-measurement states. In operator form, (∣m⟩ ⁣⟨m∣⊗I) Λ(U)=∣m⟩ ⁣⟨m∣⊗Um=Λ(U) (∣m⟩ ⁣⟨m∣⊗I)(\dyad{m}\otimes\id)\,\Lambda(U) = \dyad{m}\otimes U^m = \Lambda(U)\,(\dyad{m}\otimes\id), where Λ(U)\Lambda(U) is controlled-UU: a computational-basis measurement of the control commutes with the controlled gate.

Think first Why does the order of the two corrections matter here, when it does not in ordinary teleportation?

Classically, Zm0Xm1Z^{m_0}X^{m_1} and Xm1Zm0X^{m_1}Z^{m_0} differ by (−1)m0m1(-1)^{m_0m_1}, a global phase on each outcome branch, invisible after measurement. Deferred, the branches stay in superposition, so that sign becomes a relative phase between them. Bob still ends with ∣+i⟩\ket{+i}, but Alice's two qubits end in the entangled state 12(∣00⟩+∣01⟩+∣10⟩−∣11⟩)\tfrac12(\ket{00}+\ket{01}+\ket{10}-\ket{11}) instead of ∣+⟩∣+⟩\ket{+}\ket{+}.

Ignoring qubits, and cleaning up

DerivationMeasuring B leaves A alone
  1. ρA=Tr⁡B ρAB=∑b(I⊗⟨b∣) ρAB (I⊗∣b⟩)\rho_A = \Tr_B\,\rho_{AB} = \sum_b(\id\otimes\bra{b})\,\rho_{AB}\,(\id\otimes\ket{b})

    The partial trace, written in the computational basis of BB.

  2. ρAB′=∑b(I⊗∣b⟩ ⁣⟨b∣) ρAB (I⊗∣b⟩ ⁣⟨b∣)\rho'_{AB} = \sum_b(\id\otimes\dyad{b})\,\rho_{AB}\,(\id\otimes\dyad{b})

    Measure BB and forget the result: the blocks of ρAB\rho_{AB} that are off-diagonal in bb vanish.

  3. Tr⁡B ρAB′=∑b(I⊗⟨b∣) ρAB (I⊗∣b⟩)=ρA\Tr_B\,\rho'_{AB} = \sum_b(\id\otimes\bra{b})\,\rho_{AB}\,(\id\otimes\ket{b}) = \rho_A

    The diagonal blocks are exactly what the partial trace keeps. This is also why measuring your half of an entangled pair cannot send a signal to the other half.

Ignoring a qubit is safe for statistics. It is not harmless for interference. Suppose a subroutine computes f(x)f(x) into an ancilla and you use it to imprint a phase: ∑xαx(−1)f(x)∣x⟩∣f(x)⟩\sum_x\alpha_x(-1)^{f(x)}\ket{x}\ket{f(x)}. The ancilla now records f(x)f(x). It is a which-path marker, and branches with different f(x)f(x) can no longer interfere. The cure is uncomputation: run the computation backward to reset the ancilla to ∣0⟩\ket0 before the interference step.

Key takeaways

  • A circuit's matrix is the product of its time slices in reverse reading order; gates in parallel combine by tensor product.
  • Size counts gates, depth counts parallel layers, width counts qubits; algorithms are uniform circuit families, and BQP is defined with them.
  • Measure other bases by rotating first; classically controlled gates can always become quantum-controlled ones, with all measurements moved to the end.
  • Discarding or measuring a qubit never changes the others' statistics, but scratch qubits that are not uncomputed destroy interference.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A 4-qubit circuit applies HH to all four qubits, then CNOT0→1\mathrm{CNOT}_{0\to1} and CNOT2→3\mathrm{CNOT}_{2\to3} in parallel, then CNOT1→2\mathrm{CNOT}_{1\to2}. What are its size, depth and width?

  1. Size 7, depth 3, width 4
  2. Size 7, depth 7, width 4
  3. Size 3, depth 3, width 4
  4. Size 4, depth 3, width 7
Show the answer

A. Size 7, depth 3, width 4

Seven gates, arranged in three layers (the HHs; two parallel CNOTs; one CNOT), on four wires.

Question 2

Which circuit is equivalent to "measure qubit 0; if the result is 1, apply XX to qubit 1"?

  1. CNOT0→1\mathrm{CNOT}_{0\to1}, then measure qubit 0
  2. CNOT1→0\mathrm{CNOT}_{1\to0}, then measure qubit 0
  3. XX on qubit 1, then measure qubit 0
  4. HH on qubit 0, then CNOT0→1\mathrm{CNOT}_{0\to1}, then measure qubit 0
Show the answer

A. CNOT0→1\mathrm{CNOT}_{0\to1}, then measure qubit 0

Deferred measurement: the classically controlled XX becomes a quantum-controlled XX from qubit 0 to qubit 1, and qubit 0 is measured afterwards. Since the CNOT is diagonal on its control, measuring before or after gives identical statistics and post-measurement states.

Question 3

Alice and Bob share ∣Φ+⟩\ket{\Phi^+}. Bob measures his qubit and tells no one. What happens to Alice's statistics for an XX-basis measurement?

  1. They become deterministic
  2. They are unchanged: 50/50
  3. They now depend on Bob's outcome, so Alice can learn it
  4. They become 75/25
Show the answer

B. They are unchanged: 50/50

Alice's reduced state is I/2\id/2 before and after: the partial trace over Bob's qubit is unchanged by anything Bob does locally. His outcome is correlated with Alice's ZZ results, but without his message she sees pure noise in every basis.

Question 4

A subroutine maps ∣x⟩∣0⟩∣0⟩↦∣x⟩∣f(x)⟩∣g(x)⟩\ket{x}\ket0\ket0\mapsto\ket{x}\ket{f(x)}\ket{g(x)} and leaves the garbage g(x)=xg(x)=x. You imprint a phase from ff and then try to interfere the xx register. Why does it fail?

  1. The phase (−1)f(x)(-1)^{f(x)} is lost
  2. Garbage qubits add noise to the gates
  3. The garbage states for different xx are orthogonal, so the xx register's reduced state is diagonal: no coherence is left to interfere
  4. The subroutine is not unitary
Show the answer

C. The garbage states for different xx are orthogonal, so the xx register's reduced state is diagonal: no coherence is left to interfere

Tracing out the garbage multiplies each coherence ∣x⟩ ⁣⟨x′∣\ketbra{x}{x'} by ⟨g(x′)∣g(x)⟩\braket{g(x')|g(x)}, which is 00 for x≠x′x\ne x' here. The phases are still there, but on a classical mixture they have no effect: the garbage acted as a measurement of xx.

Question 5

Why does the definition of BQP insist that circuit families be uniform?

  1. Because quantum gates must be reversible
  2. To keep the circuit depth logarithmic
  3. Because measurements may only happen at the end
  4. Otherwise the circuits themselves could encode the answers, even to undecidable problems
Show the answer

D. Otherwise the circuits themselves could encode the answers, even to undecidable problems

A non-uniform family can hard-wire one bit of advice per input length, such as whether the nn-th Turing machine halts. Requiring a polynomial-time classical generator for CnC_n rules this out.

Go deeper

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §4.4 and §4.6 (Cambridge, 10th anniv. ed., 2010).
  • E. Bernstein & U. Vazirani, "Quantum complexity theory", SIAM J. Comput. 26, 1411 (1997).
  • R. de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415.