10.3 More phase kick-back

What makes the quantum evaluation of Boolean functions really interesting is its action on a superposition of different inputs x. For example, \sum_{x}|x\rangle|0\rangle \longmapsto \sum_{x}|x\rangle|f(x)\rangle produces f(x) for all x in a single run (note that we have dropped the normalisation factor). It is more instructive to see the effect of the function evaluation when the qubit in the second register is prepared in the state |-\rangle = \frac{1}{\sqrt 2}(|0\rangle - |1\rangle, since then \sum_x|x\rangle|-\rangle \longmapsto \sum_x (-1)^{f(x)}|x\rangle|-\rangle (as shown in Figure 10.2). Whenever f(x)=1, the bit flip X is applied to the qubit in the second register.

Computing some f\colon\{0,1\}^3\to\{0,1\} with the second-register qubit in state |-\rangle.

Figure 10.2: Computing some f\colon\{0,1\}^3\to\{0,1\} with the second-register qubit in state |-\rangle.

The reason for defining the state |-\rangle as we do is that it is the eigenstate of X with eigenvalue -1. So, due the phase kick-back, whenever f(x)=1, the phase factor -1 appears in front of the corresponding term |x\rangle. As you can see, the second register stays in state |-\rangle all the way through the computation — it is the first register where things happen. Let us now see how quantum Boolean function evaluation introduces phase shifts in quantum interference experiments, and how such experiments can be viewed as computations.