Optimal simulation of Deutsch gates and the Fredkin gate

In this paper, we study the optimal simulation of the three-qubit unitary using two-qubit gates. First, we completely characterize the two-qubit gate cost of simulating the Deutsch gate (controlled-controlled gate) by generalizing our result on the two-qubit cost of the Toffoli gate. The function of any Deutsch gate is simply a three-qubit controlled-unitary gate and can be intuitively explained as follows: The gate outputs the states of the two control qubits directly, and applies the given one-qubit unitary u on the target qubit only if both the states of the control qubits are |1. Previously, it was only known that five two-qubit gates are sufficient for implementing such a gate Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995). We show that if the determinant of u is 1, four two-qubit gates are optimal. Otherwise, five two-qubit gates are required. For the Fredkin gate (the controlled-swap gate), we prove that five two-qubit gates are necessary and sufficient, which settles the open problem introduced in Smolin and DiVincenzo Phys. Rev. A 53, 2855 (1996).