7
$\begingroup$

Even though this seems to be a much asked basic question, I couldn't find a reputed answer to this:

  • Implement a 3-qubit Toffoli gate using 3-qubit Fredkin gates.

The best I could do was using 4 gates to give

enter image description here

  1. Can we use less than 4 gates?
  2. In the above circuit how to get rid of the garbage values?(I have heard they are bad for interference)

I am new to quantum computing so please correct me if I am asking something that doesn't make sense.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

It's not possible to implement a Toffoli using only Fredkin gates, because Fredkin gates preserve the number of 1s in the state while Toffolis do not.

Improve this answer
$\endgroup$
3
  • $\begingroup$ should I add "with ancilla allowed" or is that understood? $\endgroup$
    – lineage
    Dec 27, 2019 at 17:54
  • 3
    $\begingroup$ @lineage in quantum computing you should always 'uncompute' ancillas, i.e. they always must be in the same state after the computation. So even if you will use ancillas the number of 1s will be the same on the 3 qubits of interest. $\endgroup$
    – Danylo Y
    Dec 27, 2019 at 18:55
  • 1
    $\begingroup$ Even if ancillae are allowed, it won't work because you need to uncompute any changes to the ancillae. That being said, if you path encode your qubits (i.e. decide physical |01> is logical |0> and physical |10> is logical |1>) then Fredkin gates can perform the equivalent of a Toffoli on the logical qubits (but not the physical qubits). $\endgroup$
    – Craig Gidney
    Dec 27, 2019 at 20:08

Your Answer

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

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