In both cases the answer is 4 gates.

A solution for this problem can be found in Andrew Landahl's notes for the course *Physics 452/581: Introduction to Quantum Information*, University of New Mexico. I quote the author's original solution (with some minor corrections).

In both cases, the minimum number of gates required to simulate the other is 4. A
proof of such a minimum requires exhaustively demonstrating that 1, 2 or 3 gates
is insufficient to achieve the simulation. Such a proof is omitted here and was not
required for credit. Unfortunately, intuition seems to be the best alternative to finding
the minimum number of gates and the related circuit.

By ``exhaustively demonstrating'' the author means that you can just write a computer program that lists all possible gates that you can obtain by combining 1, 2 and 3 Toffoli/Fredkin gates, and carefully check that none of them corresponds to the gate that you want to synthesize.

## **Fredkin simulates Toffoli**

We first explore some of the features of the Fredkin
gate. Generally, we write the gate as

For particular choices of ancilla, we find

FANOUT/NOT

AND

In terms of our desired output, we see that the first two inputs are trivially
mapped (aside from any possibly FANOUTs needed). The third output requires combining xy with z:

Combining these steps gives the following circuit, (with relevant intermediary outputs labeled):

## **Toffoli simulates Fredkin**

We write the Toffoli gate as

Relevant properties of the Toffoli gate are

FANOUT

XOR/CNOT

We also need to recognize that the Fredkin map can be equivalently written as

$$\mathrm{Fred}(x,y,z)= (x, x(y\oplus z)\oplus y, x(y\oplus z)\oplus z)$$

This can be intuitively seen by noticing that if the control bit x is not set, the outputs are unchanged. If x is set, the outputs are swapped using the fabled
XOR swap trick. Combining these results, we write the complete circuit (with relevant intermediary ouputs labeled):

This post imported from StackExchange Physics at 2014-06-11 15:04 (UCT), posted by SE-user Juan Bermejo Vega