7

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.

kludg
  • 3,204
  • 9
  • 18
Leander Behr
  • 133
  • 4
  • 3
    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 04 '20 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 04 '20 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 04 '20 at 16:44

1 Answers1

5

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:

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

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

kludg
  • 3,204
  • 9
  • 18
  • 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? – Leander Behr Jan 04 '20 at 19:29
  • Yes, you can uncompute after whole algorithm is done; I tried to be as simple as possible and uncomputed just $AND$ – kludg Jan 04 '20 at 19:35