# Three-Qubit Gates

**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.

## Toffoli (CCX)

**[[quantum-gate-toffoli|Toffoli]]** (Controlled-Controlled-X or CCX) is the three-qubit version of CNOT: 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 CNOT gates but requires many gates (~6 CNOTs); 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$.

## Fredkin (CSWAP)

**[[quantum-gate-fredkin|Fredkin]]** (Controlled-SWAP or CSWAP) 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{Fredkin}^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$.

## General Controlled Gates

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.

## Scalability

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.