3
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ 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.) $\endgroup$ – Norbert Schuch May 8 '20 at 13:52
  • $\begingroup$ Thanks, @NorbertSchuch. I corrected the spelling; I get 72 results for "Toffoli Gate" for a Google search with quotes; you get 47,000? $\endgroup$ – vy32 May 9 '20 at 12:14
  • $\begingroup$ 39.900 __________ $\endgroup$ – Norbert Schuch May 9 '20 at 22:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Sam Palmer May 11 '20 at 16:38
  • 1
    $\begingroup$ @SamPalmer, that's the answer. Can you make it an answer so that I can accept it? $\endgroup$ – vy32 May 11 '20 at 18:11
3
$\begingroup$

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.

$\endgroup$

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.