Quantum Circuits for Classical Functions

In classical computing, we often use functions that aren't reversible. For example, the $\text{AND}$ gate takes two inputs and produces one output: $\text{AND}(0,0)=0$, $\text{AND}(0,1)=0$, $\text{AND}(1,0)=0$, $\text{AND}(1,1)=1$.

Given the output $0$, we can't determine which of the three possible inputs produced it. It could have been $(0,0)$, $(0,1)$, or $(1,0)$. Information has been lost.

Quantum computing, however, requires all operations to be reversible. This is because, as we know, quantum operations must be unitary, and unitary matrices are always invertible.

If we tried to implement a non-reversible function like $f(0)=0$, $f(1)=0$ directly as a quantum gate $|x\rangle \rightarrow |f(x)\rangle$, we would map both $|0\rangle$ and $|1\rangle$ to $|0\rangle$, i.e.

$$\begin{align*} \ket{0}&\rightarrow \ket{f(0)} = \ket{0}, \\ \ket{1}&\rightarrow\ket{f(1)} = \ket{0}. \end{align*}$$

But clearly, this operation is not reversible. From $\ket{0}$, we have no idea whether we started with $\ket{0}$ or $\ket{1}$ before applying the function. Thus, this isn't a unitary operation (since all unitary operations are reversible), and therefore this is not a valid quantum operation.

The solution is to use an ancilla (also known as auxiliary) qubit and implement the function as:

$$|x\rangle|y\rangle \rightarrow |x\rangle|y \oplus f(x)\rangle.$$

Here, $\oplus$ denotes addition modulo 2 ($\text{XOR}$). In addition modulo 2, $0\oplus 0 = 0$, $0\oplus 1 = 1$, $1\oplus 0 = 1$, and $1\oplus 1 = 0$. This is also referred to as the classical $\text{XOR}$ gate, shorthand for "exclusive or".

This transformation is reversible because applying it twice returns the original state:

$$|x\rangle|y\rangle \rightarrow |x\rangle|y \oplus f(x)\rangle \rightarrow |x\rangle|(y \oplus f(x)) \oplus f(x)\rangle = |x\rangle|y\rangle$$

And, indeed, it can be shown that this transformation is unitary.

To see why it is unitary, note that it acts as a permutation on the computational basis states—each basis state $|x\rangle|y\rangle$ maps to exactly one other basis state $|x\rangle|y \oplus f(x)\rangle$, and different inputs map to different outputs.

...