Uncomputation in quantum implementation of a classical algorithm

Question

In Nielsens and Chuangs book, they present a way to implement a reversible version of any classical algorithm (section 3.2.5).

In short, they use Fredkin and other simple reversible gates to implement a circuit doing $(x, 0, 0, y) \rightarrow (x, f(x), g(x), y)$ by first copying $x$ to the second register and then using the Fredkin gate equivalent of the classical algorithm to take the second register (now $x$) and the ancilla bits in the third register to $f(x)$ and some garbage $g(x)$.

Then they use $CNOT$ gates to add $f(x)$ to the last register, resulting in $(x, f(x), g(x), y \oplus f(x))$.

I understand that it is now important to uncompute the $g(x)$ garbage bits so that they don't mess with quantum interference that may occur later on the fourth register (the result). So they take the registers back to $(x, 0, 0, y\oplus f(x))$ using the inverse of the Fredkin gate implementation.

Now I am wondering if the following would also work: Take $(x,0,y)$ to $(f(x), g(x), y)$ using the Fredkin equivalent of the classical algorithm. Then use $CNOT$ gates to go to $(f(x),g(x),y\oplus f(x))$ and then do the uncomputation step as before to get $(x, 0, y\oplus f(x))$.

This way we save a register. I assume I am either making some mistake on the way or the authors deemed their version easier to understand.

Answer 1

Nielsen and Chuang book may be confusing; I will try to explain.

Any classical algorithm can be presented as a circuit consisting of $NOT$ and $AND$ gates; this means that if we can make quantum gates computing $NOT$ and $AND$, and make fanout, we can run any classical algorithm on quantum computer. $NOT$ is reversible and we have quantum $NOT$ gate; many quantum gates can serve as fanout; the only problem is $AND$ because it is irreversible.

Figure 3.16 in the book shows how configure Fredkin (CSWAP) gate for computing $AND$:

You can see that we have computed garbage function $g(x,y)=\bar{x}y$ and we must uncompute it. Note that $y$ here have no relation to $y$ ancilla that will be used later in the chapter; it is better to denote here $x$ as $x_1$ and $y$ as $x_2$, and think of $x$ as of 2 qubits.

To uncompute $g(x_1,x_2)=\bar{x}_1x_2$ we need one more qubit denoted by $y$ in the book; usually it is $|0\rangle$ qubit; using $CNOT$ with qubit $f(x)=x_1x_2$ as a control qubit we map $y\rightarrow y\oplus f(x)$ and apply second Fredkin gate (which is self-reversed) to obtain

• on input: $0$, $x_2$, $x_1$, $y$
• on output:$0$, $x_2$, $x_1$, $y\oplus f(x)$

and we are done, and we used $4$ qubits to do the job.

---

PS: If you want to understand things better:

https://www.youtube.com/watch?v=R2hyQhjHxrs

https://www.youtube.com/watch?v=5hLpvy6Mja0