# Simulating Toffoli Gates with Fredkin Gates with no garbage bits

I found this answer for how to simulate a Toffoli gate with a Fredkin gate; however, it leaves a bunch of garbage bits. Is there some way to do this without garbage bits (i.e., at the end of the computation, the only outputs are $a,b,c\oplus ab$ and a bunch of 1s and 0s that do not depend on the inputs)?

The simple answer would be to fan-out the result - $c\oplus ab$ - and then reverse the computation on one of the duplicates of this. However, this leaves an extra bit of $\overline{c\oplus ab}$ that I don't know how to remove.

No matter how hard I try, I can't seem to find an arrangement of Fredkin gates and not gates that will turn $(x,x)$ into $(x,0)$, but I don't know if this is provably impossible or just something I can't figure out.

• This site may not be the best fit for this question; maybe Electrical Engineering or Computer Science would be better? – user122423 Aug 2 '17 at 17:19
• What else do you allow for? Only classical gates, or are quantum gates allowed as well? What about 2-(qu)bit-gates, e.g. CNOT? (Since you are talking about fan-outs, CNOTs don't seem so far-fetched.) – Norbert Schuch Aug 3 '17 at 9:29
• The idea was that you have only Fredkin and NOT gates, plus as many ancilla bits as necessary, but at the end of the computation all ancilla bits must return to their original values. – Sam Jaques Aug 3 '17 at 16:57