3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This site may not be the best fit for this question; maybe Electrical Engineering or Computer Science would be better? $\endgroup$
    – user122423
    Commented Aug 2, 2017 at 17:19
  • $\begingroup$ 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.) $\endgroup$
    – Norbert Schuch
    Commented Aug 3, 2017 at 9:29
  • $\begingroup$ 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. $\endgroup$
    – Sam Jaques
    Commented Aug 3, 2017 at 16:57

1 Answer 1

Reset to default
5
$\begingroup$

Fredkin gates preserve the total number of ON bits. Toffoli gates don't. Because of that, it's impossible to implement Toffoli gates with Fredkin gates without some source/dump of ON bits.

See the paper 'The Classification of Reversible Bit Operations' by Scott Aaronson et al.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So if I had NOT gates that argument wouldn't hold as I could change the the hamming weight with the NOT gate. But the linked paper also says that Fredkin plus NOT still can't generate the Toffoli gate. $\endgroup$
    – Sam Jaques
    Commented Aug 2, 2017 at 19:05
  • $\begingroup$ @SamJaques Right. I gave one reason that you can't do it but there are also others reasons. $\endgroup$
    – Craig Gidney
    Commented Aug 2, 2017 at 19:57

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.