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

Question

As a beginner in quantum computation, I noticed that all quantum algorithms take various gates followed by measuring the qubits in the last step. Is it always the case? Are there any algorithms that take measurements in an intermediate step?

Answer 1

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 $|\psi\rangle$ using quantum teleportation through a special state chosen so that teleportation output is $U|\psi\rangle$ rather than $|\psi\rangle$,
• 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,
• measurement-based quantum computing in which computation is performed by a sequence of single-qubit measurements on a specially prepared resource state and in which measurement bases are chosen based on the outcomes of previous measurements,
• measurement-based uncomputation which uses measurements followed by classically controlled quantum gates to reduce the cost of uncomputation.

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_A\rangle$, 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_A\rangle$ 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_A\rangle\langle 0_A| \otimes I_B + |1_A\rangle\langle 1_A| \otimes U_B. $$

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

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

whereas if we measure $|1_A\rangle$ the state of $B$ is

$$ \begin{align} &\langle 1_A|CU_{AB}|\psi_{AB}\rangle \\ &=\langle 1_A|\left(|0_A\rangle\langle 0_A| \otimes I_B + |1_A\rangle\langle 1_A| \otimes U_B\right)|\psi_{AB}\rangle \\ &= \langle 1_A|0_A\rangle\langle 0_A|\psi_{AB}\rangle + \langle 1_A|1_A\rangle\langle 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_B\rangle$ 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_B\rangle$ then the post-measurement state of the qubit is

$$ V_B |0_B\rangle\langle 0_B| U_B|\psi_B\rangle \tag3 $$

and if we measure $|1_B\rangle$ then it is

$$ V_B |1_B\rangle\langle 1_B| U_B|\psi_B\rangle. \tag4 $$

The corresponding circuit with terminal measurements is constructed by adding an auxiliary qubit $A$ initialized in state $|0_A\rangle$, 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_A\rangle|\psi_B\rangle \\ &= (I_A \otimes V_B) \circ \left(I_A \otimes |0_B\rangle\langle 0_B| + X_A \otimes |1_B\rangle\langle 1_B|\right) \circ (I_A \otimes U_B) |0_A\rangle|\psi_B\rangle \\ &= \left(I_A \otimes V_B|0_B\rangle\langle 0_B|U_B + X_A \otimes V_B|1_B\rangle\langle 1_B|U_B\right) |0_A\rangle|\psi_B\rangle \\ &= |0_A\rangle \otimes V_B |0_B\rangle\langle 0_B|U_B|\psi_B\rangle + |1_A\rangle \otimes V_B |1_B\rangle\langle 1_B|U_B|\psi_B\rangle \end{align} $$

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

$$ \langle 0_A|0_A\rangle \otimes V_B |0_B\rangle\langle 0_B|U_B|\psi_B\rangle + \langle 0_A|1_A\rangle \otimes V_B |1_B\rangle\langle 1_B|U_B|\psi_B\rangle = \\ V_B |0_B\rangle\langle 0_B|U_B|\psi_B\rangle \tag{3'} $$

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

$$ \langle 1_A|0_A\rangle \otimes V_B |0_B\rangle\langle 0_B|U_B|\psi_B\rangle + \langle 1_A|1_A\rangle \otimes V_B |1_B\rangle\langle 1_B|U_B|\psi_B\rangle = \\ V_B |1_B\rangle\langle 1_B|U_B|\psi_B\rangle \tag{4'} $$

once again in agreement with the original circuit.

Answer 2

Adding to the above well informed points, IBM-Q introduced new feature where we can perform the measurement,in intermediate steps of the circuit as well.