5
$\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.

$\endgroup$
7
$\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.

$\endgroup$
  • $\begingroup$ should I add "with ancilla allowed" or is that understood? $\endgroup$ – lineage Dec 27 '19 at 17:54
  • 1
    $\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 '19 at 18:55
  • $\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 '19 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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