7

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: enter image description here

Where reference [7] is:

enter image description here

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.

vy32
  • 649
  • 3
  • 14

1 Answers1

6

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.

vy32
  • 649
  • 3
  • 14
Sam Palmer
  • 1,009
  • 5
  • 12