Quantum Boolean function evaluation
In quantum computation, all elementary operations are reversible (unitary), so we compute Boolean functions in a reversible fashion as
|x\rangle|y\rangle \mapsto |x\rangle|y\oplus f(x)\rangle.
The corresponding circuit diagram (for n=3) is shown in Figure 10.1.
Here we use two registers: the first one (counting from the top to the bottom of the circuit diagram) stores the arguments x, and the second one the values 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 \mapsto |x\rangle|f(x)\rangle.
Quantum Boolean function evaluation is a special case of the generalised x-controlled-U on two registers:
\sum_x |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 may also write this as
\sum_x |x\rangle\langle x|\otimes X^{f(x)}.
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}
The evaluation |x\rangle|y\rangle \mapsto |x\rangle|y\oplus f(x)\rangle can be tabulated explicitly as
\begin{array}{cc}
|00\rangle|0\rangle \mapsto |00\rangle|0\rangle
& |00\rangle|1\rangle \mapsto |00\rangle|1\rangle
\\|01\rangle|0\rangle \mapsto |01\rangle|1\rangle
& |01\rangle|1\rangle \mapsto |01\rangle|0\rangle
\\|10\rangle|0\rangle \mapsto |10\rangle|0\rangle
& |10\rangle|1\rangle \mapsto |10\rangle|1\rangle
\\|11\rangle|0\rangle \mapsto |11\rangle|0\rangle
& |11\rangle|1\rangle \mapsto |11\rangle|1\rangle
\end{array}
and the expression \sum_x |x\rangle\langle x|\otimes X^{f(x)} becomes
\begin{aligned}
&|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 like
\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 them are the identity \mathbf{1} except the (01, 01) entry, which represents the bit-flip X.
This is because f(01)=1, and f(x)=0 for all other binary strings x.
