10.3 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,165 \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.

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

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

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.


  1. We make two notational simplifications: we usually don’t worry about normalisation factors, and we often just write \sum_x to mean \sum_{x\in\{0,1\}^n}.↩︎