# Minimum number of 2-qubit gates required to implement a Toffoli gate

I'm trying to design a quantum circuit that has an output that is closest to a CCNOT gate with no more than four 2-qubit gates (but I can use additional single qubit gates).

A lot of resources/papers I have read have claimed that five is the minimum number of 2-qubit gates necessary to implement a Toffoli gate.

Any clever insight?

• If you do not care about phase, you can really implement Toffoli with four CNOTs: quantumcomputing.stackexchange.com/questions/9842/… Feb 20 at 9:42
• Why not show us where it said that 5 is the minimum number? Also you might be interested in this and this. Feb 21 at 4:21
• @user1271772, Five 2-qubit gates are sufficient according to e.g., Quantum Gates and Circuits by DiVincenzo and necessary according to [Five Two-Qubit Gates Are Necessary for Implementing Toffoli Gate]( doi.org/10.1103/PhysRevA.88.010304) by Yu, Duan & Ying. Feb 21 at 4:39

## 1 Answer

There are some techniques to decompose Toffoli gate. Here I mention two useful techniques. Toffoli gate can be decomposed into six CNOTs (two qubit gate) gates with transpile technique of Qiskit and three CNOTs with Margolus technique. It seems that Margolus technique is the optimal way for decomposing Toffoli gate [1].

[1] G. Song and A. Klappenecker, “The simplified toffoli gate implementation by margolus is optimal,” (2003).

With Margolus technique, Fredkin gate(controlled-swap gate) can be decomposed with only 5 qubit gates [2].

[2] J. A. Smolin and D. P. DiVincenzo, Phys. Rev. A 53, 2855 (1996).

Here is a simple code that you can use it for decomposing of Toffoli gate with transpile function qiskit

from qiskit.quantum_info import Operator

from qiskit.compiler import transpile

from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

qc = QuantumCircuit(3)

qc.ccx(0,1,2) # Toffoli gate

qc.draw('latex')

result = transpile(qc, basis_gates=['cx','u3','tdg', 'h', 't'], optimization_level=3)

result.draw('mpl')