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.


1 Answer 1


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.

  • $\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$ Dec 27, 2019 at 20:08
  • $\begingroup$ @DanyloY Why not measure and discard these ancillas? Measurement always takes part in quantum computation anyway, right? $\endgroup$
    – swish
    Oct 19, 2023 at 1:38
  • $\begingroup$ Never mind, I keep forgetting that classical discarding is not realizable physically. $\endgroup$
    – swish
    Oct 19, 2023 at 1:55

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.