Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# CCX (Toffoli) gate
**CCX gate** (doubly-controlled X, also called Toffoli gate or CCNOT) is a three-qubit gate that flips the target qubit if and only if both control qubits are $\lvert 1\rangle$. It was introduced by Tommaso Toffoli in 1980 and is the key building block for reversible classical computation inside a quantum circuit.

The gate implements the reversible Boolean operation $\lvert a, b, c\rangle \mapsto \lvert a, b, c \oplus (a \wedge b)\rangle$, where $\oplus$ is XOR and $\wedge$ is AND. Its matrix is the $8 \times 8$ identity with the last two rows swapped (basis ordered $\lvert 000\rangle$ through $\lvert 111\rangle$):

$$\text{CCX} = \begin{pmatrix}
1&0&0&0&0&0&0&0\\
0&1&0&0&0&0&0&0\\
0&0&1&0&0&0&0&0\\
0&0&0&1&0&0&0&0\\
0&0&0&0&1&0&0&0\\
0&0&0&0&0&1&0&0\\
0&0&0&0&0&0&0&1\\
0&0&0&0&0&0&1&0
\end{pmatrix}$$

## Classical universality

The CCX gate alone is classically universal — any Boolean function can be computed reversibly using only CCX gates. Setting $c = 0$ gives AND: $\lvert a, b, 0\rangle \to \lvert a, b, a \wedge b\rangle$. Setting $a = b = 1$ gives NOT: $\lvert 1, 1, c\rangle \to \lvert 1, 1, \lnot c\rangle$. AND and NOT are a complete classical gate set.

## Circuit decomposition

The CCX gate can be decomposed into six [[cx-gate|CX gates]] and several single-qubit gates. It is its own inverse: $\text{CCX}^2 = I$. CCX gates appear in reversible arithmetic circuits (adders, multipliers) embedded inside quantum algorithms, and in quantum error correction as controlled-controlled operations.

## List of code implementations

- [[toffoli-gate-qiskit|CCX gate (Qiskit)]]
- [[toffoli-gate-custatevec|CCX gate (cuStateVec)]]
- [[toffoli-gate-cudaq|CCX gate (CUDA-Q)]]