Three-qubit gates act on three qubits, typically as controlled versions of single-qubit or two-qubit gates. The most common are Toffoli (CCX) and Fredkin (CSWAP), which are universal for classical reversible computation and form building blocks for larger controlled operations.

CCX (also Toffoli or Controlled-Controlled-X) is the three-qubit version of CX: it flips the target if both controls are $|1\rangle$. The quantum AND gate and universal for classical reversible computation, it can be decomposed into single-qubit and CX gates but requires many gates (~6 CXs); native implementations reduce this overhead.

Action: $|a\rangle|b\rangle|c\rangle \to |a\rangle|b\rangle|c \oplus (a \wedge b)\rangle$

$$\text{Toffoli} = \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}$$

Basis action: flips target qubit only for $|11c\rangle$ states. Basis mapping: $|110\rangle \to |111\rangle$ and $|111\rangle \to |110\rangle$.

CCY (Controlled-Controlled-Y) applies Y to the target qubit if both control qubits are $|1\rangle$. Like CCX, it is an asymmetric doubly-controlled gate but less commonly native. It can be decomposed into CCX plus phase gates on the target.

$$\text{CCY} = \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 & -i \\ 0 & 0 & 0 & 0 & 0 & 0 & i & 0 \end{pmatrix}$$

Basis action: applies Y to target only for $|11c\rangle$ states. Basis mapping: $|110\rangle \to i|111\rangle$ and $|111\rangle \to -i|110\rangle$.

CCZ (Controlled-Controlled-Z) applies a phase to the $|111\rangle$ state only. Symmetric in all three qubits (unlike CCX and CCY), it is related to CZ via a doubly-controlled construction. Diagonal, it applies phases without changing basis states.

$$\text{CCZ} = \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 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \end{pmatrix}$$

Basis action: applies phase only to $|111\rangle$. Basis mapping: $|111\rangle \to -|111\rangle$; all other states unchanged.

CSWAP (also Fredkin or Controlled-SWAP) swaps two qubits if the control is $|1\rangle$. The quantum controlled-SWAP and also universal for classical reversible computation, it is useful for reversible algorithms that require conditional swaps. Self-inverse ($\text{CSWAP}^2 = I$) and symmetric in the two swapped qubits, it conserves Hamming weight (the number of 1s in the bitstring).

Action: $|c\rangle|a\rangle|b\rangle \to |c\rangle|a'\rangle|b'\rangle$ where $a' = c \cdot b + \bar{c} \cdot a$ and $b' = c \cdot a + \bar{c} \cdot b$.

$$\text{Fredkin} = \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 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$

Basis action: swaps the second and third qubits when the first qubit is $|1\rangle$. Basis mapping: $|101\rangle \to |110\rangle$ and $|110\rangle \to |101\rangle$.

Any unitary $U$ can be controlled: a controlled-$U$ gate applies $U$ to target qubits if all control qubits are $|1\rangle$. Construction typically decomposes $U = e^{i\alpha} A X B X C$ where $ABC = I$, then uses controlled single-qubit gates and CNOTs to build the full controlled operation.

Multi-qubit gates are expensive: implementing a controlled-$U$ on $n$ qubits requires $O(n)$ elementary gates and time. For large $n$, it is often more efficient to avoid native multi-qubit gates and instead use shallow circuits composed of two-qubit gates.