Adaptive Measurement

What does measuring part of a register in the middle of a circuit do to the rest? A mid-circuit measurement splits the computation into branches, one per outcome. For a computational-basis measurement of one qubit, the branch operators are the projectors \(M_0=\ket0\bra0\otimes I\) and \(M_1=\ket1\bra1\otimes I\). Outcome \(b\) occurs with probability

\[p_b=\|M_b\ket\psi\|^2,\]

and leaves the normalized state \(M_b\ket\psi/\sqrt{p_b}\). The outcome is stored as a classical record, a bit that later operations can read. Using it to choose a later gate \(V_b\) is feedforward: the branch with outcome \(b\) continues as \(V_bM_b\ket\psi/\sqrt{p_b}\).

Two features distinguish this from coherent computation. First, branches with different records never interfere again: the record is a which-path record held in a classical register, and classical registers do not go into superposition. Probabilities of branches add; their amplitudes do not. Second, if we ignore the record, the state is the mixture of branches, each with its probability. A mixture can be written as a single matrix, the density operator \(\sum_bV_bM_b\ket\psi\bra\psi M_b^\dagger V_b^\dagger\): each unnormalized branch \(\ket{\chi_b}=V_bM_b\ket\psi\) contributes \(\ket{\chi_b}\bra{\chi_b}\), whose trace is the branch probability \(p_b\).

Example: prepare \(\frac{1}{\sqrt2}(\ket{00}+\ket{11})\), measure the first qubit, and if the outcome is \(1\) apply \(X\) to the second. Both branches end with the second qubit in \(\ket0\). Feedforward has turned a random outcome into a deterministic state, which is the essential trick of teleportation and of every measurement-based method.

Can a measurement and the classically controlled gate after it be replaced by something coherent? Yes: by a quantum-controlled gate, with the measurement moved to the end. If a qubit is measured in the computational basis and the outcome controls \(V\) on other qubits, then using that qubit as the control of a controlled-\(V\), and measuring it afterwards, gives the same joint distribution of all final outcomes. This is the deferred measurement principle.

Why does it hold? The controlled gate acts as \(\ket0\bra0\otimes I+\ket1\bra1\otimes V\). It never changes the control qubit’s computational-basis value, so the final measurement of that qubit returns the same statistics it would have earlier, and on each value the target receives exactly the same operation as under feedforward. Since nothing afterwards acts on the control qubit, the two procedures cannot be distinguished by their outputs.

The principle is a statement about output statistics, not about resources. The deferred version keeps the measured qubit alive until the end, so it cannot be reset and reused; it needs a controlled gate, which may be more expensive than a classically controlled one; and it must remain coherent longer. The measured version can recycle the qubit immediately but requires fast classical feedback during the computation. Which is cheaper depends on the hardware. The principle can also be used in reverse, starting from a coherent circuit and replacing quantum controls by measurements and classical control, which saves qubits.

Feedforward is most useful when every outcome leads to the intended result after a cheap fix. Here is a small example. In the Hadamard test, take the controlled unitary to be \(U=e^{i\theta X}\). The two outcomes apply

\[\text{outcome }0:\ \frac{I+U}{2}=\cos\tfrac\theta2\,e^{i\theta X/2},\qquad\text{outcome }1:\ \frac{I-U}{2}=-i\sin\tfrac\theta2\,e^{i\theta X/2}X.\]

Both branches apply the half-angle rotation \(e^{i\theta X/2}\), with an extra \(X\) on outcome \(1\). Since \(X\) commutes with \(e^{i\theta X/2}\), applying \(X\) again after outcome \(1\) gives \(e^{i\theta X/2}\) deterministically, for every input. The outcome probabilities are \(\cos^2\frac\theta2\) and \(\sin^2\frac\theta2\), independent of the input, so the measurement reveals nothing about the data. A fix that is a Pauli gate is a Pauli correction, and Pauli corrections are cheap in nearly every hardware and error-correction scheme.

A related pattern is repeat-until-success. Some circuits apply the desired gate on one outcome and, on the other, a known unitary that can be undone cheaply. On failure, undo and try again. The number of attempts is random, but the final result is exact, and the expected cost can be lower than a deterministic decomposition. For single-qubit rotations in Clifford+\(T\) circuits, repeat-until-success constructions reduce the expected \(T\) count below that of the best deterministic synthesis by a constant factor (Paetznick and Svore, 2014). Postselection on a block encoding, with no way to undo failures, is not of this kind: there a failure destroys the input.

How can one control qubit read all the digits? Let \(U\ket u=e^{2\pi i\phi}\ket u\), with \(\phi=0.b_1b_2\cdots b_m\) exactly in binary. We learn the bits one at a time, from the last to the first, with one control qubit that is measured and reused.

At stage \(k\) (running from \(m\) down to \(1\)), prepare the control in \(\ket+\) and apply controlled-\(U^{2^{k-1}}\). The kicked-back phase is \(2\pi\cdot2^{k-1}\phi\) modulo \(2\pi\), which is \(2\pi\,(0.b_kb_{k+1}\cdots b_m)\): multiplying by \(2^{k-1}\) shifts the binary point past the first \(k-1\) digits, which contribute whole turns. The bits after \(b_k\) are already known from earlier stages. Remove their contribution with a phase gate on the control,

\[P(-\omega_k),\qquad\omega_k=2\pi\,(0.0\,b_{k+1}\cdots b_m),\]

leaving phase \(2\pi\,(0.b_k)=\pi b_k\): the control is \(\ket+\) if \(b_k=0\) and \(\ket-\) if \(b_k=1\). A Hadamard and measurement return \(b_k\) with certainty. This is iterative phase estimation, the textbook circuit with deferred measurement run in reverse.

The resources compare as follows. Qubits: one control instead of \(m\). Controlled-\(U\) uses: \(2^m-1\) in total, exactly as before, since stage \(k\) still needs \(U^{2^{k-1}}\). Coherence: each stage needs coherence only for its own controlled power, not for the whole computation. Classical feedback: the correction angle \(\omega_k\) depends on earlier outcomes, so the controller must compute it between stages. Iterative estimation saves width, not total evolution.

What does the feedback look like in practice? Take \(\phi=3/8=0.011_2\), so \(b_1=0\), \(b_2=1\), \(b_3=1\), and \(m=3\).

Stage 3 uses \(U^4\), which kicks back phase \(2\pi\cdot4\cdot\frac38=2\pi\cdot\frac32\equiv\pi\). No bits are known yet, so no correction is applied. The control is \(\ket-\), and the outcome is \(b_3=1\).

Stage 2 uses \(U^2\), with phase \(2\pi\cdot\frac34\). Knowing \(b_3=1\), we subtract \(\omega_2=2\pi\cdot(0.01)=2\pi\cdot\frac14\), leaving \(\pi\). The outcome is \(b_2=1\).

Stage 1 uses \(U\), with phase \(2\pi\cdot\frac38\). Knowing \(b_2b_3=11\), we subtract \(\omega_1=2\pi\cdot(0.011)=2\pi\cdot\frac38\), leaving \(0\). The outcome is \(b_1=0\).

The acquisition order is \(b_3,b_2,b_1\), but the phase is \(0.b_1b_2b_3=0.011\). Recording bits in the wrong order is an easy implementation error that the problems explore.

The same structure appears inside the textbook circuit. The inverse QFT’s controlled phase gates subtract the contributions of bits already determined, then a Hadamard reads the next bit. If each qubit of the QFT output is measured as soon as it is final, and the measured value classically controls the remaining phase gates, the output statistics are unchanged, by deferred measurement. This is the semiclassical Fourier transform of Griffiths and Niu (1996). It needs only single-qubit gates, measurements, and classical control, no two-qubit gates at all, and it is how Shor’s algorithm can run its \(2n\)-qubit control register on a single recycled qubit.

What happens when the phase has no finite binary expansion? The exact examples assumed \(\phi\) has \(m\) binary digits. A general phase does not, so each stage’s outcome is probabilistic, and a wrong early bit corrupts the correction for every later one. Practical adaptive schemes therefore repeat stages, use the outcomes as statistical evidence about \(\phi\), and choose later experiments to be informative given what is already known. Bayesian methods keep a probability distribution over \(\phi\) and update it after each outcome; robust phase estimation (Kimmel, Low, and Yoder, 2015) uses a fixed schedule of powers with enough repetitions per power to bound the error even with noise.

How precise can any such scheme be? Count resources as total uses of \(U\), \(N\). Repeating a single Hadamard test \(N\) times estimates \(\phi\) with error of order \(1/\sqrt N\): the standard quantum limit, the same \(1/\sqrt N\) as classical sampling. Using powers \(U^{2^j}\) and adaptive or Fourier processing reaches error of order \(1/N\): the Heisenberg limit. That no strategy does better is a quoted theorem of quantum metrology (Giovannetti, Lloyd, and Maccone, 2006). It is consistent with the search lower bound. An amplitude estimator with error much smaller than \(1/\sqrt N\) after far fewer than \(\sqrt N\) uses could tell a list with one marked item among \(N\) from a list with none, since their amplitudes are \(1/\sqrt N\) and \(0\), and that would beat the \(\Omega(\sqrt N)\) bound. The improvement comes from coherence across many uses of \(U\), concentrated in long controlled powers.

In the presence of noise that limits how long a controlled power can stay coherent, the Heisenberg scaling holds only up to that coherence time; beyond it, repetition returns to standard scaling. Adaptive estimation is the setting in which this trade-off is managed: use the longest powers that remain reliable, and repeat them.

Can a measurement move a state onto another qubit and apply a gate on the way? Take an input \(\ket\psi=a\ket0+b\ket1\) and an auxiliary qubit in \(\ket+\). Apply a controlled-\(Z\) between them, giving \(a\ket0\ket++b\ket1\ket-\). Now measure the input qubit in the basis

\[\ket{\pm_\alpha}=\tfrac{1}{\sqrt2}\big(\ket0\pm e^{i\alpha}\ket1\big).\]

Projecting onto \(\ket{\pm_\alpha}\) gives, for outcome \(m\in\{0,1\}\) (\(m=0\) for \(+\)), the unnormalized auxiliary state

\[\tfrac{1}{\sqrt2}\big(a\ket++(-1)^me^{-i\alpha}b\ket-\big)=\tfrac{1}{\sqrt2}\,X^mHP(-\alpha)\ket\psi,\qquad P(\beta)=\mathrm{diag}(1,e^{i\beta}).\]

Each outcome has probability \(\frac12\), whatever \(\ket\psi\) is. The state has moved to the auxiliary qubit, and on the way the gate \(HP(-\alpha)\) has been applied, followed by a known Pauli \(X^m\) that depends on the outcome. This is one-bit teleportation, and the general idea of applying a gate by teleporting through a suitably prepared resource is gate teleportation.

The measurement basis chooses the gate: different \(\alpha\) give different rotations. The Pauli byproduct can be corrected immediately, or tracked classically and accounted for later. Nothing is cloned, since the input qubit is consumed by the measurement, and nothing is sent faster than light, since the byproduct cannot be interpreted without the outcome bit.

What if we repeat the step? Chain the construction. Prepare a line of qubits in \(\ket+\), apply controlled-\(Z\) between neighbours, and place the input at one end. Measuring the first qubit with angle \(\alpha_1\) teleports \(HP(-\alpha_1)\ket\psi\) onto the second; measuring the second with \(\alpha_2\) teleports \(HP(-\alpha_2)HP(-\alpha_1)\ket\psi\) onto the third; and so on. Can such products reach every single-qubit gate? Every single-qubit unitary is, up to a global phase, a product \(R_z(\gamma)R_x(\beta)R_z(\alpha)\) of rotations, the Euler decomposition. Here \(P(\beta)\) equals \(R_z(\beta)\) up to a global phase, and \(R_x(\beta)=HR_z(\beta)H\), so products of the steps \(HP(-\alpha_k)\) reach every single-qubit unitary: a few steps suffice for any one of them. On a two-dimensional grid of such entangled qubits, a cluster state, measurements can also apply entangling gates. This is measurement-based quantum computation (Raussendorf and Briegel, 2001): all entanglement is prepared in advance, and the computation consists of single-qubit measurements in adaptively chosen bases.

Adaptivity is essential. A byproduct \(X\) from one step does not commute with the next step’s phase gate; instead \(P(\beta)X=e^{i\beta}XP(-\beta)\), so pushing the \(X\) through flips the sign of the next angle. The classical controller therefore chooses each measurement basis using earlier outcomes, flipping signs as needed, and keeps track of the remaining Pauli byproducts, a record called the Pauli frame, to reinterpret the final outcomes. Measurements whose bases do not depend on others can be done simultaneously, so the depth of the computation is set by the chain of classical dependencies.

The model is equivalent in power to the circuit model, not more powerful. Its appeal is architectural: photonic platforms, where two-qubit gates are probabilistic but entangled resource states can be built and checked in advance, use it naturally. Its costs are the size of the resource state, the precision of measurement angles, and fast classical feedforward.

Why do error-corrected computers need anything beyond Clifford gates? Error-correcting codes make Clifford gates (\(H\), \(S\), CNOT) comparatively easy to apply fault-tolerantly, but Clifford gates alone are not universal. A quoted theorem, the Gottesman–Knill theorem (Gottesman, 1998), shows that circuits of Clifford gates on computational-basis inputs, with computational-basis measurements, can be simulated efficiently classically. The \(T\) gate supplies the missing power, and in many codes it cannot be applied directly. Gate teleportation solves this by moving the difficulty into a state.

Prepare the magic state \(\ket A=T\ket+=\frac{1}{\sqrt2}(\ket0+e^{i\pi/4}\ket1)\). With data \(\ket\psi=a\ket0+b\ket1\), apply a CNOT from the data to the magic qubit, and measure the magic qubit:

\[\text{outcome }0:\ a\ket0+e^{i\pi/4}b\ket1=T\ket\psi,\qquad\text{outcome }1:\ e^{i\pi/4}\big(a\ket0+e^{-i\pi/4}b\ket1\big)\propto T^\dagger\ket\psi.\]

On outcome \(1\), apply \(S=T^2\): \(ST^\dagger=T\). Either way the data ends in \(T\ket\psi\), using only a CNOT, a measurement, and a classically controlled \(S\), all Clifford operations. This is state injection.

The non-Clifford difficulty has moved into preparing \(\ket A\) with very high fidelity. Magic-state distillation (Bravyi and Kitaev, 2005) takes many noisy copies of \(\ket A\) and, using only Clifford operations and measurements, outputs fewer copies with much lower error; for example, one standard protocol turns 15 copies with error \(p\) into one with error about \(35p^3\). Distillation dominates the cost of many fault-tolerant resource estimates, which is why algorithms are often costed in \(T\) gates or Toffolis, and why the synthesis costs of small rotations, in phase gates, Fourier transforms and simulation, matter.

This closes the technique sequence. Algorithm design, as the design process we began with laid out, has meant choosing compatible access, encoding the property that matters, engineering interference, constructing a readout, proving correctness, and counting every resource. Measurement and feedback, introduced here last, turn out to touch every stage: they shorten circuits, recycle qubits, and even supply the gates. The next course, Quantum Programming, turns these contracts and calculations into executable, tested circuits.