# Gate Decomposition

**Gate decomposition** breaks complex gates into simpler, more fundamental gates. Useful for implementing gates not native on specific hardware or for circuit optimization.

## Single-Qubit Decomposition

Any single-qubit unitary can be decomposed as:

$$U = e^{i\alpha} R_Z(\beta) R_X(\gamma) R_Z(\delta)$$

This is the **Z-X-Z** decomposition. Alternative decompositions use different rotation axes.

$$U = e^{i\alpha} R_X(\beta) R_Z(\gamma) R_X(\delta)$$

(X-Z-X decomposition)

## Two-Qubit Decomposition

CNOT can decompose arbitrary two-qubit unitaries:

$$U_{2Q} = (A \otimes B) \text{CNOT} (C \otimes D) \text{CNOT} (E \otimes F)$$

requires up to 3 CNOTs and 12 single-qubit gates. This is the **KAK decomposition**.

## Common Decompositions

**Toffoli in terms of Hadamards, CNOTs, T gates** (~6 CNOTs):

```
     ┌───┐
q_0: ┤ H ├──■───
     └───┘┌─┴─┐
q_1: ─────┤ X ├
          └───┘
```

(Simplified; full Toffoli decomposition is longer)

**SWAP in terms of CNOTs** (3 CNOTs):

```
q_0: ──■────────■──
     ┌─┴─┐┌────┐└─┬─┘
q_1: ┤ X ├┤ CX ├──■──
     └───┘└────┘
```

## Trade-offs

- **Fewer native gates**: decomposition uses fewer gate types but may require more total gates
- **Shorter depth**: reorder decomposed gates to minimize circuit depth
- **Hardware constraints**: decompose to match hardware's native gate set

Quantum compiler tools (Qiskit, Cirq, Q#) handle decomposition automatically.