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

Computing some f\colon\{0,1\}^3\to\{0,1\} in a quantum manner, where x\in\{0,1\}^3, y\in\{0,1\}, and \oplus denotes \texttt{XOR}, or addition modulo 2.

Figure 10.1: Computing some f\colon\{0,1\}^3\to\{0,1\} in a quantum manner, where x\in\{0,1\}^3, y\in\{0,1\}, and \oplus denotes \texttt{XOR}, or addition modulo 2.

Here we use two registers: the first162 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-flip163 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.

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


  1. Reading the circuit diagram from top to bottom.↩︎

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

  3. We always use the lexicographic order 00<01<10<11.↩︎