Phase kick-back
Before moving on, we first describe a simple yet omnipresent “trick” — an unusual way of introducing phase shifts that will be essential for our analysis of quantum algorithms.
Consider the following circuit.
(Controlled-U interference).
where |u\rangle is an eigenstate of U, so that U|u\rangle = e^{i\varphi}|u\rangle for some \varphi.
This should look familiar: it is the usual interference circuit, but with the phase gate replaced by a controlled-U gate, which will mimic the phase gate, as we shall soon see.
Note that the second qubit is prepared in state |u\rangle, which is required to be an eigenstate of U.
The circuit effects the following sequence of transformations:
\begin{aligned}
|0\rangle|u\rangle
&\overset{H}{\longmapsto}
(|0\rangle+|1\rangle)|u\rangle
\\&\quad = |0\rangle|u\rangle + |1\rangle|u\rangle
\\&\overset{\texttt{c-}U}{\longmapsto}
|0\rangle|u\rangle + |1\rangle U|u\rangle
\\&\quad = |0\rangle|u\rangle + e^{i\varphi}|1\rangle|u\rangle
\\&\quad = (|0\rangle + e^{i\varphi}|1\rangle) |u\rangle
\\&\overset{H}{\longmapsto}
\left(
\cos\frac{\varphi}{2}|0\rangle
- i\sin\frac{\varphi}{2}|1\rangle
\right) |u\rangle.
\end{aligned}
Note that the second qubit does not get entangled with the first one: it remains in its original state |u\rangle.
However, the interaction between the two qubits introduces a phase shift on the first qubit.
This may look like an unnecessarily complicated way of introducing phase shifts, but, as we shall soon see, this is how quantum computers do it.
Here is a preview of things to come.
Consider the following x-controlled-U operation:
\left[
\begin{array}{cccc}
\mathbf{1}& 0 & 0 & 0
\\0 & \mathbf{1}& 0 & 0
\\0 & 0 & \mathbf{1}& 0
\\0 & 0 & 0 & X
\end{array}
\right]
= \begin{aligned}
|00\rangle\langle 00|&\otimes\mathbf{1}
\\+\,\,|01\rangle\langle 01|&\otimes\mathbf{1}
\\+\,\,|10\rangle\langle 10|&\otimes\mathbf{1}
\\+\,\,|11\rangle\langle 11|&\otimes X.
\end{aligned}
The first register is of size 2 (corresponding to the top-left 2\times 2 block, which is simply the identity matrix), and the second register is of size 1 (corresponding to the two bottom-right 1\times1 blocks, namely an identity matrix and X).
If the first register is prepared in state |11\rangle, then the qubit in the second register is flipped (by the Pauli bit-flip X); otherwise, nothing happens.
This unitary operation is a quantum version of the Boolean function evaluation: it corresponds to the Boolean function
\begin{aligned}
f\colon\{0,1\}^2 &\longrightarrow \{0,1\}
\\00&\longmapsto0
\\01&\longmapsto0
\\10&\longmapsto0
\\11&\longmapsto1.
\end{aligned}
If f(x)=1, then we flip the bit value in the second register (with operation X); if f(x)=0, then we do nothing.
Now, prepare the qubit in the second register in state |0\rangle-|1\rangle, which is an eigenstate of X with eigenvalue e^{\pi i}=-1.
So whenever X is applied to the second register, the phase factor -1 appears in front of the corresponding term in the first register.
If we prepare the first register in the superposition |00\rangle+|01\rangle+|10\rangle+|11\rangle then the result of applying the above x-controlled-U operation is the entangled state |00\rangle+|01\rangle+|10\rangle-|11\rangle.
That is, the phase kick-back mechanism introduces a relative phase in the equally-weighted superposition of all binary strings of length two.
Phase kick-back is how we control quantum interference in quantum computation.
We will return to this topic later on in Section 10.2, when we discuss quantum evaluation of Boolean functions and quantum algorithms.