More phase kick-back
What makes quantum evaluation of Boolean functions really interesting — and what truly sets it apart from classical evaluation — is its action on a superposition of different inputs.
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.
However, it is more instructive to see the effect of quantum function evaluation when the qubit in the second register is prepared in the state |-\rangle\coloneqq\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)=H|1\rangle, since then
\sum_x|x\rangle|-\rangle
\longmapsto
\sum_x (-1)^{f(x)}|x\rangle|-\rangle
(as shown in Figure 10.2).
In words, whenever f(x)=1, the bit-flip X is applied to the qubit in the second register.
The reason for defining the state |-\rangle as we do is that it is the eigenstate of X with eigenvalue -1, i.e. X|-\rangle=-|-\rangle.
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.
