Quantum Boolean function evaluation
In quantum computation, all elementary operations are reversible (i.e. unitary), so we need to compute Boolean functions in a reversible fashion — we can do so as follows:
|x\rangle|y\rangle \mapsto |x\rangle|y\oplus f(x)\rangle.
The corresponding circuit diagram (for an input register of n=3 qubits) is shown in Figure 10.1.
Here we use two registers: the first one stores the arguments |x\rangle (where x\in\{0,1\}^n is our binary string input), and the second one the value f(x).
More precisely, the value f(x) is added bit-wise to the pre-existing binary value y of the second register.
We usually set y=0 to get
|x\rangle|0\rangle \longmapsto |x\rangle|f(x)\rangle.
Quantum Boolean function evaluation is a special case of the generalised x-controlled-U on two registers:
\sum_{x\in\{0,1\}^n} |x\rangle\langle x|\otimes U_x
where U_x is either the identity \mathbf{1} (when f(x)=0) or the bit-flip X (when f(x)=1).
We can write this very succinctly as
\sum_{x\in\{0,1\}^n} |x\rangle\langle x|\otimes X^{f(x)}.
Because of this, we sometimes denote the quantum evaluation of the function f by U_f, which is a gate on the (n+1) qubits |x\rangle|y\rangle.
A worked example
Consider the Boolean function f\colon\{0,1\}^2\to\{0,1\} given by
f(x)
= \begin{cases}
1 &\text{if $x=01$;}
\\0 &\text{otherwise}
\end{cases}
which we might call the indicator (or characteristic) function for the binary string 01, sometimes denoted \chi_{01}.
The evaluation |x\rangle|y\rangle \mapsto |x\rangle|y\oplus f(x)\rangle can be tabulated explicitly:
\begin{array}{cc}
|00\rangle|0\rangle \longmapsto |00\rangle|0\rangle
& |00\rangle|1\rangle \longmapsto |00\rangle|1\rangle
\\|01\rangle|0\rangle \longmapsto |01\rangle|1\rangle
& |01\rangle|1\rangle \longmapsto |01\rangle|0\rangle
\\|10\rangle|0\rangle \longmapsto |10\rangle|0\rangle
& |10\rangle|1\rangle \longmapsto |10\rangle|1\rangle
\\|11\rangle|0\rangle \longmapsto |11\rangle|0\rangle
& |11\rangle|1\rangle \longmapsto |11\rangle|1\rangle
\end{array}
and then
\begin{aligned}
\sum_{x\in\{0,1\}^2} |x\rangle\langle x|\otimes X^{f(x)}
= &|00\rangle\langle 00| \otimes \mathbf{1}
+ |01\rangle\langle 01| \otimes X
\\+ &|10\rangle\langle 10| \otimes \mathbf{1}
+ |11\rangle\langle 11| \otimes \mathbf{1}.
\end{aligned}
Finally, the matrix form looks as follows:
\left[
\,
\begin{array}{c|c|c|c}
\begin{matrix}1&0\\0&1\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
\\\hline
\begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}0&1\\1&0\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
\\\hline
\begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}1&0\\0&1\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
\\\hline
\begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}0&0\\0&0\end{matrix}
& \begin{matrix}1&0\\0&1\end{matrix}
\end{array}
\,
\right]
As you can see, this is a diagonal block matrix: a (4\times 4) matrix with (2\times 2) matrices as entries.
The rows and the columns of the (4\times 4) matrix are labelled by the binary strings 00, 01, 10, 11, and the (2\times 2) matrices on the diagonal represent operations applied to the qubit in the second register.
Here, all of these matrices on the diagonal are the identity \mathbf{1} except for the (01,01) entry (i.e. the second one), which is the bit-flip X.
This is because f(01)=1 (and so we want to turn the control value y=0 into y=1, which is achieved by applying the bit-flip operator), but f(x)=0 for all other binary strings x (and so we want to leave the control value y=0 as it is).
