Are there any algorithms that take measurements in an intermediate step?

It is not always the case that measurements are at the end of a quantum circuit. Indeed, there are many ideas and techniques that use the classical bits that result from intermediate measurements to control subsequent quantum gates.

Here are a few prominent examples:

• quantum teleportation in which one party uses measurements to identify the quantum gates that another party needs to apply to their half of an entangled Bell pair in order to recover an arbitrary input quantum state,
• gate teleportation technique for applying a gate $U$ to a quantum state $|psirangle$ using quantum teleportation where the recovery step is modified to obtain $U|psirangle$ rather than the original state $|psirangle$,
• KLM protocol which uses measurements to perform two-qubit gates in linear optical quantum computing thus overcoming the challenges inherent in making photons interact and enabling universal quantum computation in this model,
• quantum error correction using stabilizer codes where measurements are used to detect and identify errors as they are occurring during quantum computation,
• fault-tolerant constructions that use magic states to perform gates that do not admit a transversal implementation in a given quantum error correcting code.

Nevertheless, in many cases the assumption that all measurements are performed at the end of a circuit enables simplified analysis. This assumption is significantly less restrictive than it may first appear due to a powerful principle called the principle of deferred measurement. It is described on p.186 in section 4.4 in Nielsen & Chuang as follows:

Principle of deferred measurement: Measurements can always be moved from an intermediate stage of a quantum circuit to the end of the circuit; if the measurement results are used at any stage of the circuit then the classically controlled operations can be replaced by conditional quantum operations.

The specific circuit transformation necessary to move an intermediate measurement towards the end of a circuit depends on the surrounding gates. It is informative to consider concrete examples.

Example 1 (replacing classical control with quantum control): A simple, but very useful case occurs when the measurement result is immediately used to control a unitary gate. Consider two qubits $A$ and $B$ in a state $|psi_{AB}rangle$. Suppose we measure $A$ in the computational basis and then apply a unitary $U_B$ to $B$ conditioned on the result of the measurement. Neglecting normalization, if we measure $|0_Arangle$, the state of $B$ is

$$ U_B^0 langle 0_A|psi_{AB}rangle = I_B langle 0_A|psi_{AB}rangle = langle 0_A|psi_{AB}rangle tag1 $$

and if we measure $|1_Arangle$ the state of $B$ is

$$ U_B^1 langle 1_A|psi_{AB}rangle = langle 1_A |U_B|psi_{AB}rangle. tag2 $$

Now suppose we instead apply controlled-$U$ to both qubits with $A$ as control and $B$ as target and then measure $A$ as the final step in the circuit. First note that the unitary of controlled-$U$ with $A$ as control and $B$ as target is

$$ CU_{AB} = |0_Aranglelangle 0_A| otimes I_B + |1_Aranglelangle 1_A| otimes U_B. $$

Once again, neglecting normalization, if we measure $|0_Arangle$ the state of $B$ is

$$ begin{align} &langle 0_A|CU_{AB}|psi_{AB}rangle &=langle 0_A|left(|0_Aranglelangle 0_A| otimes I_B + |1_Aranglelangle 1_A| otimes U_Bright)|psi_{AB}rangle &=langle 0_A|0_Aranglelangle 0_A|psi_{AB}rangle + langle 0_A|1_Aranglelangle 1_A|U_B|psi_{AB}rangle &=langle 0_A|psi_{AB}rangle end{align}tag{1'} $$

whereas if we measure $|1_Arangle$ the state of $B$ is

$$ begin{align} &langle 1_A|CU_{AB}|psi_{AB}rangle &=langle 1_A|left(|0_Aranglelangle 0_A| otimes I_B + |1_Aranglelangle 1_A| otimes U_Bright)|psi_{AB}rangle &= langle 1_A|0_Aranglelangle 0_A|psi_{AB}rangle + langle 1_A|1_Aranglelangle 1_A|U_B|psi_{AB}rangle &= langle 1_A|U_B|psi_{AB}rangle. end{align}tag{2'} $$

Thus, we see that the post-measurement state of $B$ is the same for each outcome of measurement on $A$. We also need to check that the probability of each outcome is the same, but since we neglected normalization the probability is the norm of the corresponding vector and therefore the equality of outcome probabilities follows from the equality of the unnormalized states.

Example 2 (replacing measurement with CNOT gate and auxiliary qubit): Another interesting case occurs when an intermediate measurement is sandwiched between two unitary gates. Here, the required circuit transformation involves an auxiliary qubit. Suppose for concreteness that a qubit $B$ starts in $|psi_Brangle$ and the original circuit applies a gate $U_B$, followed by a measurement in the computational basis, followed by a gate $V_B$. As before, we neglect normalization. If we measure $|0_Brangle$ then the post-measurement state of the qubit is

$$ V_B |0_Branglelangle 0_B| U_B|psi_Brangle tag3 $$

and if we measure $|1_Brangle$ then it is

$$ V_B |1_Branglelangle 1_B| U_B|psi_Brangle. tag4 $$

The corresponding circuit with terminal measurements is constructed by adding an auxiliary qubit $A$ initialized in state $|0_Arangle$, replacing the measurement with a CNOT with $B$ as control and $A$ as the target and finally measuring $A$ in the computational basis. The unitary part of the circuit computes

$$ begin{align} &(I_A otimes V_B) circ CNOT_{BA} circ (I_A otimes U_B) |0_Arangle|psi_Brangle &= (I_A otimes V_B) circ left(I_A otimes |0_Branglelangle 0_B| + X_A otimes |1_Branglelangle 1_B|right) circ (I_A otimes U_B) |0_Arangle|psi_Brangle &= left(I_A otimes V_B|0_Branglelangle 0_B|U_B + X_A otimes V_B|1_Branglelangle 1_B|U_Bright) |0_Arangle|psi_Brangle &= |0_Arangle otimes V_B |0_Branglelangle 0_B|U_B|psi_Brangle + |1_Arangle otimes V_B |1_Branglelangle 1_B|U_B|psi_Brangle end{align} $$

so if we measure $|0_Arangle$ then the post-measurement state of $B$ is

$$ langle 0_A|0_Arangle otimes V_B |0_Branglelangle 0_B|U_B|psi_Brangle + langle 0_A|1_Arangle otimes V_B |1_Branglelangle 1_B|U_B|psi_Brangle = V_B |0_Branglelangle 0_B|U_B|psi_Brangle tag{3'} $$

and if we measure $|1_Arangle$ then the post-measurement state of $B$ is

$$ langle 1_A|0_Arangle otimes V_B |0_Branglelangle 0_B|U_B|psi_Brangle + langle 1_A|1_Arangle otimes V_B |1_Branglelangle 1_B|U_B|psi_Brangle = V_B |1_Branglelangle 1_B|U_B|psi_Brangle tag{4'} $$

once again in agreement with the original circuit.