Universal Gate Sets

Universal gate sets are minimal collections of gates that can approximate any unitary operation to arbitrary precision. Different sets are universal; the choice depends on hardware availability.

The most common set: arbitrary single-qubit gates (e.g., RX, RY, RZ) plus CNOT. This set is universal.

Solovay-Kitaev theorem: any unitary on $n$ qubits can be approximated to precision $\epsilon$ using $O(\log^{3+\delta}(1/\epsilon))$ gates from a finite set.

Clifford + T: {H, S, CNOT} + {T gate}

• Clifford gates alone are not universal (classical simulation exists)
• Adding T gate makes the set universal
• T gate is expensive to implement (magic state distillation on fault-tolerant hardware)

Pauli + Rotation + CNOT: {X, Y, Z, RX, RY, RZ, CNOT}

Rotation gates at arbitrary angles are needed; restrict angles to discrete values (e.g., multiples of $\pi/8$) to get a finite set.

Three-axis rotations: {RX, RY, RZ, CNOT}

XX + RZ: {XX($\theta$), RZ, CNOT} for certain $\theta$

Different platforms support different native gates; universality guarantees you can simulate any algorithm.

In practice, quantum hardware has finite gate sets. CNOT gates are typically slow and error-prone; variational algorithms exploit this by using shallow circuits with few two-qubit gates.

The choice of universal set affects:

• Circuit depth: fewer, cheaper gates → shallower circuits → less decoherence
• Gate fidelity: native gates are faster and more accurate
• Compilation overhead: decomposing to non-native gates adds gates