# What are the differences between the Toffoli and Fredkin gates (historical, practical, etc.)

I'm trying to understand the historical ordering and the practical differences between the Toffoli Gate and the Fredkin Gate.

Toffoli's February 1980 tech report MIT/LCS/TM-151 states:

Where reference [7] is:

Conservative Logic is then published in 1982 in at least different guises: an article in International Journal of Theoretical Physics and a chapter in Collision-Based Computing.

So the implication to me is that the Fredkin gate precedes the Toffoli Gate.

Given that both gates are universal, what is the purpose of trying to simulate Fredkin gates with Toffoli gates, or vice-versa?

Also, Which gate is more commonly used, and why? A recent Google search finds 84 results for "Fredkin gate" in the Google index, and 86 results for "Toffoli gate." Both of those seem to be dramatic undercounts.

• Note that you mis-spell Toffoli about every second time, maybe this explains the low hits? (I get 47.000 and 34.000 with quotes.) Commented May 8, 2020 at 13:52
• Thanks, @NorbertSchuch. I corrected the spelling; I get 72 results for "Toffoli Gate" for a Google search with quotes; you get 47,000?
– vy32
Commented May 9, 2020 at 12:14
• 39.900 __________ Commented May 9, 2020 at 22:24
• You can see from here, nmr.physics.ox.ac.uk/oxonly/C2/QIP2answers.pdf, that Toffoli can't be constructed from Fredkin without the use of ancilla qubits (which in practice qubits are a valuable resource), whilst Fredkin from Toffili doesn't require the use an additional ancilla qubit. Simulating gates with Toffoli is just a more compact way of constructing a circuit with cnots and single qubit controlled unitaries, as nqubit controlled gates can be decomposed as such. Commented May 11, 2020 at 16:38
• @SamPalmer, that's the answer. Can you make it an answer so that I can accept it?
– vy32
Commented May 11, 2020 at 18:11