Optimal simulation of three-qubit gates

Understand

In this paper, we study the optimal simulation of three-qubit unitary by using two-qubit gates.

• First, we give a lower bound on the two-qubit gates cost of simulating a multi-qubit gate.
• Secondly, we completely characterize the two-qubit gate cost of simulating a three-qubit controlled controlled gate by generalizing our result on the cost of Toffoli gate.
• The function of controlled controlled gate is simply a three-qubit controlled unitary gate and can be intuitively explained as follows: the gate will output the states of the two control qubit directly, and apply the given one-qubit unitary $u$ on the target qubit only if both the states of the control are $\ket{1}$.