10.1 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.

Computing some f\colon\{0,1\}^3\to\{0,1\} in a quantum manner.

Figure 10.1: Computing some f\colon\{0,1\}^3\to\{0,1\} in a quantum manner.

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-flip128 X (when f(x)=1). We may also write this as \sum_x |x\rangle\langle x|\otimes X^{f(x)}.

10.1.1 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.


  1. Do not confuse the capital X, which is the Pauli flip operator \sigma_x, with the small x, which is a binary string stored in the first register and the argument of our Boolean function f.↩︎