# Gate Composition

**Gate composition** combines gates into circuits. The order matters: composing gates $U$ then $V$ gives the combined gate $VU$ (right-to-left matrix multiplication).

## Sequential Composition

Applying gates in sequence multiplies matrices (right-to-left):

$$|\psi_{\text{out}}\rangle = V_n \cdots V_2 V_1 |\psi_{\text{in}}\rangle$$

The combined unitary is:

$$U_{\text{total}} = V_n \cdots V_2 V_1$$

## Parallel Composition

Gates on different qubits commute and can be applied simultaneously:

$$U_1 \otimes U_2 = (U_1 \otimes I)(I \otimes U_2)$$

Parallelization reduces circuit depth (execution time).

## Circuit Optimization

**Gate cancellation**: adjacent inverse gates cancel, $GG^\dagger = I$:

```
Before:  ├─H─┤ ├─H─┤
         └───┘ └───┘

After:   ├─────┤
         └─────┘
```

**Commutation**: gates on different qubits commute (reorder without changing result):

```
Before:  ├─H─┤ ├─X─┤
         ├─X─┤ ├─H─┤

After:   ├─X─┤ ├─H─┤
         ├─H─┤ ├─X─┤
```

**Merge single-qubit gates**: consecutive single-qubit gates on the same qubit can be merged:

$$R_Z(\alpha) R_X(\beta) = U(\alpha, \beta, \gamma)$$

for appropriate $\gamma$.

## Circuit Depth

The **depth** of a circuit is the longest chain of sequential gates on any qubit. Depth determines execution time on quantum hardware. Minimize depth to reduce decoherence errors.

Example: Bell state circuit has depth 2 (H on qubit 0, then CNOT, then measurement).