# Uncomputation in quantum implementation of a classical algorithm

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.

• How are you performing the $x \rightarrow f(x)$ step, if you don't have a reversible circuit for $f$? What if $f(x) = 0$? – Craig Gidney Jan 4 at 15:48
• I (or rather the authors) use fredkin gates to simulate classical and, copy (fanout) and crossover gates. For that they also need prepared ancilla bits (register three with value 0) and produce some garbage output (g(x)). They also use not gates to prepare the ancilla bits to 0 or 1 as needed. – Leander Behr Jan 4 at 15:56
• if $f(x)=0$ then we can put $g(x)=x$ and $(x,0) \rightarrow (f(x),g(x)) = (0,x)$ will be just swap (though if we want to implement it with Fredkin gates we have to take $g(x)=x1$). I believe there is no need to use 2 additional ancilla registers. – Danylo Y Jan 4 at 16:44

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:

• Yes, you can uncompute after whole algorithm is done; I tried to be as simple as possible and uncomputed just $AND$ – kludg Jan 4 at 19:35