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
  • 641
  • 3
  • 13
  • 2
    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.) – Norbert Schuch May 08 '20 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 May 09 '20 at 12:14
  • 39.900 __________ – Norbert Schuch May 09 '20 at 22:24
  • I wouldn't rely on "number of search results" as a consistent number, but I also don't see how you can get such low numbers. I get ~47k for "toffoli gate" (with quotes) and ~200k without quotes. 39.9k for "fredkin gate". You might have some weird region or other setting enabled. Regardless, I don't think the chronological order in which they were presented matters in any way here. I personally saw the Toffoli more used as part of an elementary gate set, so it might just be easier to work with, or people are more used to it. – glS May 10 '20 at 08:01
  • 2
    You can see from here, https://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. – Sam Palmer May 11 '20 at 16:38
  • 1
    @SamPalmer, that's the answer. Can you make it an answer so that I can accept it? – vy32 May 11 '20 at 18:11

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
  • 641
  • 3
  • 13
Sam Palmer
  • 949
  • 4
  • 11