Academy K

Decomposing the Toffoli Gate

InterviewCodingToffoligate decompositionuniversal gates

Related module: Gates and circuits

Problem statement

The Toffoli (CCNOT) gate flips the third qubit if and only if the first two qubits are both ∣1⟩|1\rangle:

∣a,b,c⟩→∣a,b,c⊕(a∧b)⟩|a,b,c\rangle \to |a,b,c \oplus (a \land b)\rangle

It cannot be directly implemented on most hardware. Decompose it into single-qubit gates and CNOTs.

Write pseudocode or a circuit description for the decomposition.

Hints

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.