Simple Algorithm
Quantum Computing · Rydberg State · 24 min

Deferred & Implicit Measurement

Moving measurements to the end, and ignoring qubits safely.

"Move every measurement to the end" is a one-line principle with an exact operator identity behind it, a hidden bill in qubits and depth, and a surprising converse: sometimes measuring early is strictly better.

What you’ll learn

  • State and prove the deferred measurement theorem as an equality of quantum instruments, with explicit width and size accounting.
  • Prove the principle of implicit measurement from trace preservation, and model a measurement as a CNOT into an unread record.
  • Prove the Ω(log⁡n)\Omega(\log n) light-cone bound for unitary GHZ preparation, and contrast it with constant-depth preparation using feed-forward.
  • Use measurement-based uncomputation, and explain why feed-forward keeps fault-tolerant circuits Clifford.

The theorem as an operator identity

Model a circuit with intermediate measurements as a quantum instrument: a family of completely positive maps {Em}\{\mathcal{E}_{\mathbf{m}}\} indexed by the outcome record m\mathbf{m}, whose sum is trace preserving. Record m\mathbf{m} occurs with probability Tr⁡ Em(ρ)\Tr\,\mathcal{E}_{\mathbf{m}}(\rho) and leaves the state Em(ρ)/Tr⁡ Em(ρ)\mathcal{E}_{\mathbf{m}}(\rho)/\Tr\,\mathcal{E}_{\mathbf{m}}(\rho). Two circuits are equivalent if they implement the same instrument.

Check your understanding

A repetition-code memory runs 1000 rounds. Each round measures 2 syndrome ancillas, then resets and reuses them; decoding happens classically at the end. How many syndrome qubits does the deferred version, with no mid-circuit measurement, need?

  1. 2
  2. 1000
  3. 2000
  4. 210002^{1000}
Show the answer

C. 2000

Every reset becomes a fresh wire, and every record must survive to the end: 2×1000=20002\times1000 = 2000 syndrome qubits. Deferral preserves size and statistics, but not width.

Implicit measurement and the record picture

DerivationA measurement is an unread CNOT record
  1. CNOTq→r(ρq⊗∣0⟩ ⁣⟨0∣r)CNOTq→r†=∑m,m′ρmm′ ∣m⟩ ⁣⟨m′∣q⊗∣m⟩ ⁣⟨m′∣r\mathrm{CNOT}_{q\to r}\big(\rho_q\otimes\dyad{0}_r\big)\mathrm{CNOT}_{q\to r}^\dagger = \sum_{m,m'}\rho_{mm'}\,\ketbra{m}{m'}_q\otimes\ketbra{m}{m'}_r

    The record copies the computational-basis label.

  2. Tr⁡r[ ⋯ ]=∑mρmm ∣m⟩ ⁣⟨m∣q=∑m∣m⟩ ⁣⟨m∣ ρ ∣m⟩ ⁣⟨m∣\Tr_r[\,\cdots] = \sum_m\rho_{mm}\,\dyad{m}_q = \sum_m\dyad{m}\,\rho\,\dyad{m}

    Tracing out the record kills the off-diagonal terms: exactly the state after a non-selective ZZ measurement.

  3. So a "measurement" is entanglement with a record that is never brought back. An environment that picks up the computational-basis value does the same thing: that is decoherence, here pure dephasing.

Check your understanding

In the record version, which operation on qubit 1 alone, applied at the end, would make qubit 0's histogram deterministic again?

  1. Measure qubit 1 in the XX basis
  2. Apply HH to qubit 1
  3. Reset qubit 1 to ∣0⟩\ket0
  4. None: by implicit measurement, nothing done to qubit 1 alone changes qubit 0's statistics
Show the answer

D. None: by implicit measurement, nothing done to qubit 1 alone changes qubit 0's statistics

Qubit 0's reduced state is fixed by Tr⁡1\Tr_1, which no channel on qubit 1 can change. A quantum eraser recovers interference only conditionally: measuring qubit 1 in the XX basis and sorting qubit 0's results by that outcome gives two deterministic sub-ensembles (00 for ++, 11 for −-) that average back to 50/50.

What deferral does not preserve: depth

Deferral keeps the size polynomial but can cost depth: classical feed-forward hides arbitrary classical processing, which a unitary circuit must perform coherently. The cleanest example is the GHZ state.

DerivationConstant depth with measurement and feed-forward
  1. ∣+⟩⊗n on the data;measure si=ZiZi+1 via ancillas(i=1,…,n−1)\ket{+}^{\otimes n}\ \text{on the data};\qquad\text{measure } s_i = Z_iZ_{i+1}\ \text{via ancillas}\quad(i=1,\dots,n-1)

    Two layers of CNOTs into n−1n-1 ancillas (first data i→aii\to a_i for all ii, then data i+1→aii+1\to a_i), then measure the ancillas: constant depth.

  2. ∣+⟩⊗n ⟼ 12(∣x⟩+∣xˉ⟩),x1=0,xj=s1⊕⋯⊕sj−1\ket{+}^{\otimes n}\ \longmapsto\ \tfrac{1}{\sqrt2}\big(\ket{x}+\ket{\bar x}\big),\qquad x_1 = 0,\quad x_j = s_1\oplus\cdots\oplus s_{j-1}

    Exactly two strings, xx and its complement xˉ\bar x, have the observed parities, and all 2n−12^{n-1} syndromes are equally likely.

  3. ⨂jXj xj:12(∣x⟩+∣xˉ⟩) ⟼ 12(∣0⋯0⟩+∣1⋯1⟩)\bigotimes_j X_j^{\,x_j}:\qquad\tfrac{1}{\sqrt2}\big(\ket{x}+\ket{\bar x}\big)\ \longmapsto\ \tfrac{1}{\sqrt2}\big(\ket{0\cdots0}+\ket{1\cdots1}\big)

    One layer of classically controlled XX gates finishes the job. The prefix parities xjx_j are computed classically; deferring them would require the coherent parity computation that the light-cone bound forbids in constant depth.

When measuring early is better

DerivationMeasurement-based uncomputation of an AND
  1. ∑a,bαab∣a⟩∣b⟩∣a∧b⟩\sum_{a,b}\alpha_{ab}\ket{a}\ket{b}\ket{a\wedge b}

    An ancilla holding the AND of two qubits, for example a carry bit in an adder.

  2. measure the ancilla in X, outcome m:∑a,bαab (−1)m ab ∣a⟩∣b⟩\text{measure the ancilla in } X\text{, outcome } m:\qquad\sum_{a,b}\alpha_{ab}\,(-1)^{m\,ab}\,\ket{a}\ket{b}

    Since ⟨±∣c⟩=(±1)c/2\braket{\pm|c} = (\pm1)^c/\sqrt2, each outcome (m=0m=0 for ∣+⟩\ket+, m=1m=1 for ∣−⟩\ket-) occurs with probability 12\tfrac12 and leaves the ancilla disentangled, at the price of a phase (−1)m ab(-1)^{m\,ab}.

  3. m=1:CZab removes (−1)abm=1:\qquad\mathrm{CZ}_{ab}\ \text{removes}\ (-1)^{ab}

    A Clifford fix-up. Uncomputing the AND coherently costs TT gates; measuring makes it TT-free. This trick is behind Gidney's 2018 adder, which halves the TT-count of quantum addition.

Key takeaways

  • Deferred measurement is an exact identity: computational-basis projectors on a control commute with the gates it controls, so measurement records can be read at the end.
  • It preserves the instrument and polynomial size, but costs width (one fresh qubit per reset) and can cost depth (GHZ states: constant with feed-forward, Ω(log⁡n)\Omega(\log n) without).
  • Implicit measurement is trace preservation: nothing done to a discarded system changes the rest; a measurement is an unread CNOT record.
  • Measuring early can be strictly better: feed-forward keeps fault-tolerant circuits Clifford and makes uncomputing ANDs TT-free.

Check yourself

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

Question 1

Which identity is the heart of the deferred-measurement proof?

  1. (∣m⟩ ⁣⟨m∣⊗I) Λ(U)=Λ(U) (∣m⟩ ⁣⟨m∣⊗I)(\dyad{m}\otimes\id)\,\Lambda(U) = \Lambda(U)\,(\dyad{m}\otimes\id) for a gate controlled by the measured qubit
  2. H∣0⟩ ⁣⟨0∣H=∣+⟩ ⁣⟨+∣H\dyad{0}H = \dyad{+}
  3. Tr⁡B(ρA⊗ρB)=ρA\Tr_B(\rho_A\otimes\rho_B) = \rho_A
  4. CNOT2=I\mathrm{CNOT}^2 = \id
Show the answer

A. (∣m⟩ ⁣⟨m∣⊗I) Λ(U)=Λ(U) (∣m⟩ ⁣⟨m∣⊗I)(\dyad{m}\otimes\id)\,\Lambda(U) = \Lambda(U)\,(\dyad{m}\otimes\id) for a gate controlled by the measured qubit

Computational-basis projectors on a control commute with any gate it controls, so the measurement can slide past all later gates that use it only as a control.

Question 2

The principle of implicit measurement follows most directly from:

  1. the no-cloning theorem
  2. trace preservation of channels acting on the discarded system
  3. unitarity of the gates acting on AA
  4. the Born rule applied to AA
Show the answer

B. trace preservation of channels acting on the discarded system

Tr⁡B∘(idA⊗NB)=Tr⁡B\Tr_B\circ(\mathrm{id}_A\otimes\mathcal{N}_B) = \Tr_B is exactly the statement that NB\mathcal{N}_B preserves trace, applied factor by factor.

Question 3

Which statement about preparing an nn-qubit GHZ state is correct?

  1. Constant depth suffices without measurement, given all-to-all connectivity
  2. Measurement cannot help, because deferred measurement shows it adds no power
  3. Unitary circuits of two-qubit gates need depth Ω(log⁡n)\Omega(\log n), but constant quantum depth suffices with mid-circuit measurement and classical feed-forward
  4. Depth Ω(n)\Omega(n) is needed even with measurement and feed-forward
Show the answer

C. Unitary circuits of two-qubit gates need depth Ω(log⁡n)\Omega(\log n), but constant quantum depth suffices with mid-circuit measurement and classical feed-forward

The light-cone argument gives d≥12log⁡2nd\ge\frac12\log_2 n for unitary circuits; measuring the parities ZiZi+1Z_iZ_{i+1} and applying classically computed XX corrections takes constant quantum depth.

Question 4

In measurement-based uncomputation of an AND ancilla, what do you do when the XX-basis outcome is −- (that is, m=1m=1)?

  1. Nothing
  2. Apply CZ between the two input qubits
  3. Apply a Toffoli to recompute the AND
  4. Apply XX to the ancilla and measure again
Show the answer

B. Apply CZ between the two input qubits

Outcome m=1m=1 leaves the phase (−1)ab(-1)^{ab} on the inputs, which a CZ removes exactly. No TT gates are needed.

Further reading

  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §4.4 (Cambridge, 10th anniv. ed., 2010).
  • S. Bravyi, M. B. Hastings & F. Verstraete, "Lieb–Robinson bounds and the generation of correlations and topological quantum order", Phys. Rev. Lett. 97, 050401 (2006).
  • C. Gidney, "Halving the cost of quantum addition", Quantum 2, 74 (2018).
  • B. Skinner, J. Ruhman & A. Nahum, "Measurement-induced phase transitions in the dynamics of entanglement", Phys. Rev. X 9, 031009 (2019).
  • B. Fefferman & Z. Remscrim, "Eliminating intermediate measurements in space-bounded quantum computation", Proc. STOC (2021).