Table of Contents

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