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.

  • 3
    $\begingroup$ 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$? $\endgroup$ Commented Jan 4, 2020 at 15:48
  • $\begingroup$ 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. $\endgroup$ Commented Jan 4, 2020 at 15:56
  • $\begingroup$ 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. $\endgroup$
    – Danylo Y
    Commented Jan 4, 2020 at 16:44

1 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$: 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:



  • $\begingroup$ But we are not doing the following step then right? "We could also have added gates to the beginning of the circuit, in order to create a copy of x which is not changed during the subsequent computation." Also you are talking about uncomputing directly after each Fredkin gate while in the book they talk about uncomputing after the whole algorithm is done? $\endgroup$ Commented Jan 4, 2020 at 19:29
  • $\begingroup$ Yes, you can uncompute after whole algorithm is done; I tried to be as simple as possible and uncomputed just $AND$ $\endgroup$
    – kludg
    Commented Jan 4, 2020 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.