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\ensuremath{\rangle}$. 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)].
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
∣1⟩. Previously, it is only known that five two-qubit gates is sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. Our result shows that if the determinant of
u is 1, four two-qubit gates is achievable optimal. Otherwise, five is optimal. Thirdly, we show that five two-qubit gates are necessary and sufficient for implementing the Fredkin gate(the controlled swap gate), which settles the open problem introduced in [Smolin and DiVincenzo, Phys. Rev. A, 53, 2855 (1996)]. The Fredkin gate is one of the most important quantum logic gates because it is universal alone for classical reversible computation, and thus with little help, universal for quantum computation. Before our work, a five two-qubit gates decomposition of the Fredkin gate was already known, and numerical evidence of showing five is optimal is found.
Toffoli gates are key building blocks in quantum programs, and on most current quantum computers, they must be implemented with smaller gates. Such an implementation requires five 2-qubit gates if we assume that each gate can operate on any two qubits. However, many current quantum computers have only 2-qubit gates that operate on neighboring qubits; we call them neighbor gates. How many neighbor gates are required to implement a Toffoli gate? In this article, we show that six neighbor gates are necessary and sufficient, and we generalize to a characterization of all 3-qubit diagonal gates.
Unitary operations are expressed in the quantum circuit model as a finite sequence of elementary gates, such as controlled-not gates and single qubit gates. We prove that the simplified Toffoli gate by Margolus, which coincides with the Toffoli gate up to a single change of sign, cannot be realized with less than three controlled-not gates. If the circuit is implemented with three controlled-not gates, then at least four additional single qubit gates are necessary. This proves that the implementation suggested by Margolus is optimal.