5.1.1 Reversible computation

Before we get carried away with trying to find exciting new quantum algorithms, let us first make sure that we can still compute on a quantum computer everything that we can compute on an ordinary computer. In other words, let us first make sure that quantum computers are actually not less powerful than ordinary (classical) computers! This is not entirely obvious, since the way that quantum computers work is very different. In particular, all operations on a quantum computer are reversible or invertible, as we already mentioned in Section 2.4.2 and Section 4.1.3, but this is normally not the case on an ordinary computer. Who has never erased a file by accident or forgotten to save the changes in their document and lost all their work? If all operations would be reversible, you would never have to worry about such trivial matters.

This raises the following question: how can we see that quantum computers can compute everything that ordinary computers can compute? One way to address this is to show that reversibility does not in fact restrict what an ordinary computer can compute, and hence it is also not a restriction for quantum computers. In other words, we will show that any computation can be made reversible and hence run on a quantum computer.

To get an idea of how this can be done, let us consider the simple example of computing the logical AND function of two bits. If both bits are 1, AND evaluates to 1, otherwise it evaluates to 0. Thus, we can represent the AND function by the following function table:

Using the notation from Section 3.1, we can write this down mathematically as the following operation on two bits:

Clearly this operation is not reversible because it does not have the same number of output bits as input bits. Indeed, if you only know that the AND of two bits is $0$ then you cannot infer the precise state of the two bits – as the function table shows, there are three possible options.

How can we fix this problem? Let’s try to keep the first bit around and introduce a second output bit in which we store the answer:

This is better, since now we are mapping two bits to two bits. But is it reversible? That is, given the output, can we always reconstruct the input? Well, we can surely reconstruct the first bit of the input, $x_{1}$, since we also have it in the output. How about $x_{2}$ then? If $x_{1}=0$ then according to Eq. 5.1 the output is $[00]$ – irrespective of the value of $x_{2}$. This means that, again, we cannot always reconstruct the input and hence this approach also sadly does not work.

This starts to look hopeless. Is it even possible at all to implement the AND function in a reversible fashion? When you get stuck, you have to think outside the box! In this case, who said that we should limit ourselves to two bits only? If we keep both input bits around and introduce a third bit to store the answer, this should surely make the operation reversible:

Now there is no problem to invert the operation – given any output bitstring, we can simply forget what the last bit contains and replace it by $[0]$ to recover the input bitstring. For example, if the output is $[111]$ then the input must have been $[110]$.

So are we done? Not so fast! Note that Eq. 5.2 only specifies the operation partially – if the input is $[111]$, or any other bitstring that ends with $1$, then Eq. 5.2 does not say how the operation should act on this input. Since the four input strings that end with $0$ are mapped to four distinct output strings, it is clear that we can extend Eq. 5.2 in some arbitrary fashion to a reversible operation of three bits. But is there some systematic way of going about this?

For this, note that Eq. 5.2 flips the last bit from $[0]$ to $[1]$ if $\operatorname{AND}(x_{1},x_{2})=1$. Similarly, if the last bit instead happens to be $[1]$, we could simply define our operation to flip it back to $[0]$ whenever $\operatorname{AND}(x_{1},x_{2})=1$. In other words, we can extend Eq. 5.2 to all possible input strings as follows:

for all $x_{1},x_{2},y\in\{0,1\}$, where ‘$\oplus$’ denotes addition modulo 2.

The operation in Eq. 5.3 is now defined on all possible inputs. But is it finally reversible? Yes, it is! In fact, this operation is its own inverse! That is, if we do the operation twice, we get the original input back:

In the third step we used that $a\oplus a=0$ for any $a\in\{0,1\}$, see Eq. 3.21. Thus we have successfully found a way to compute the AND function in a reversible way.