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.
on qubit 0 comes first in time, so it is the right factor.
acts on the left tensor factor only.
The control (qubit 0) is in the second term, so the target flips: a Bell state.
Column is the image of the -th basis state .
A one-qubit circuit applies , then . Which matrix does it implement, and what does it do to ?
- , giving
- , giving
- , giving
- , giving
Show the answer
B. , giving
The first gate is the rightmost factor: , and . Reading order would give , a different state.
Size, depth and width
Depth matters because idle qubits keep decohering. Take the -qubit GHZ state . The chain , , , … has depth . Doubling is better: after , copy qubit 0 into qubit 1; then and in parallel; then four CNOTs in parallel; and so on. Each layer doubles the size of the GHZ block.
With the doubling strategy and any-to-any connectivity, what is the depth of a 16-qubit GHZ preparation, counting the initial as one layer?
Show the answer
5 layers
One layer, then CNOT layers growing the GHZ block : four layers. The total is , versus for the chain. Without measurements, depth 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 , one circuit for each input length . The family must be uniform: a classical algorithm, given , prints a description of in time . Without uniformity the family could smuggle uncomputable advice into its gate choices (say, circuits that "know" whether the -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 gates has depth at most , and since each gate touches a bounded number of qubits, at most 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 measure | Circuit | Why it works |
|---|---|---|
| (computational basis) | meter | Outcomes , . |
| , then meter | maps . | |
| , , then meter | maps . | |
| (parity) | CNOTs from both qubits into an ancilla , then meter the ancilla | The ancilla ends in ; superpositions within each parity class survive. |
Your device only measures in the computational basis. Which circuit sends to outcome and to outcome with certainty?
- , then measure
- , then , then measure
- , then , then measure
- , then , then measure
Show the answer
B. , then , then measure
and then . Basis change first, then the measurement.
A classically controlled gate acts only if a measured bit is . In teleportation, Bob applies and then after receiving Alice's outcomes . 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
Any state, split by the value of the qubit that will be measured; the are unnormalized.
Classical control: acts only on outcome .
The same probabilities, because is unitary…
…and the same post-measurement states. In operator form, , where is controlled-: 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, and differ by , 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 , but Alice's two qubits end in the entangled state instead of .
Ignoring qubits, and cleaning up
The partial trace, written in the computational basis of .
Measure and forget the result: the blocks of that are off-diagonal in vanish.
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 into an ancilla and you use it to imprint a phase: . The ancilla now records . It is a which-path marker, and branches with different can no longer interfere. The cure is uncomputation: run the computation backward to reset the ancilla to 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.
A 4-qubit circuit applies to all four qubits, then and in parallel, then . What are its size, depth and width?
- Size 7, depth 3, width 4
- Size 7, depth 7, width 4
- Size 3, depth 3, width 4
- Size 4, depth 3, width 7
Show the answer
A. Size 7, depth 3, width 4
Seven gates, arranged in three layers (the s; two parallel CNOTs; one CNOT), on four wires.
Which circuit is equivalent to "measure qubit 0; if the result is 1, apply to qubit 1"?
- , then measure qubit 0
- , then measure qubit 0
- on qubit 1, then measure qubit 0
- on qubit 0, then , then measure qubit 0
Show the answer
A. , then measure qubit 0
Deferred measurement: the classically controlled becomes a quantum-controlled 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.
Alice and Bob share . Bob measures his qubit and tells no one. What happens to Alice's statistics for an -basis measurement?
- They become deterministic
- They are unchanged: 50/50
- They now depend on Bob's outcome, so Alice can learn it
- They become 75/25
Show the answer
B. They are unchanged: 50/50
Alice's reduced state is before and after: the partial trace over Bob's qubit is unchanged by anything Bob does locally. His outcome is correlated with Alice's results, but without his message she sees pure noise in every basis.
A subroutine maps and leaves the garbage . You imprint a phase from and then try to interfere the register. Why does it fail?
- The phase is lost
- Garbage qubits add noise to the gates
- The garbage states for different are orthogonal, so the register's reduced state is diagonal: no coherence is left to interfere
- The subroutine is not unitary
Show the answer
C. The garbage states for different are orthogonal, so the register's reduced state is diagonal: no coherence is left to interfere
Tracing out the garbage multiplies each coherence by , which is for here. The phases are still there, but on a classical mixture they have no effect: the garbage acted as a measurement of .
Why does the definition of BQP insist that circuit families be uniform?
- Because quantum gates must be reversible
- To keep the circuit depth logarithmic
- Because measurements may only happen at the end
- 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 -th Turing machine halts. Requiring a polynomial-time classical generator for rules this out.
Go deeper
- Deferred & Implicit Measurement · Moving measurements to the end, and ignoring qubits safely.
- Reversible Computing & Uncomputation · Bennett’s trick and why garbage destroys interference.
- Measurement-Based Quantum Computing · Computing by measuring a cluster state.
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.