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?


1 Answer 1


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.