Quantum Logic Gates

Gate Decomposition Overview

How arbitrary unitaries are broken into the small fixed set of gates a machine can actually execute.

The decomposition problem

A quantum algorithm is written with high-level gates — arbitrary rotations, multi-controlled operations, whole unitaries. Real hardware executes only a small native set. Decomposition is the process of rewriting each abstract gate as an exact product of native gates, and it is a prerequisite for running any circuit.

A hierarchy of levels

Kronos motion — lego machine

Single-qubit: any 2×2 unitary becomes three rotations via Euler ZYZ, then native pulses
Two-qubit: any 4×4 unitary becomes at most three CNOTs plus single-qubit gates via the KAK/canonical decomposition
Controlled gates: controlled-U becomes two CNOTs plus single-qubit gates via ABC
Multi-qubit: n-qubit unitaries recurse via quantum Shannon decomposition down to two-qubit blocks

Exact versus approximate

Some decompositions are exact — they reproduce the target unitary precisely. Others, needed when the native set is discrete (Clifford+T), are approximate: the Solovay-Kitaev theorem guarantees any target can be approached to any accuracy with a gate count that grows only polylogarithmically in the precision.

Optimality bounds

Known lower bounds tell compilers when to stop. A generic two-qubit gate provably needs three CNOTs; a generic n-qubit unitary needs a number of CNOTs that grows as 4^n. Matching these bounds is the goal of a good synthesis routine.

python

# conceptual pipeline
# 1. any U -> KAK -> single-qubit blocks + up to 3 CNOTs
# 2. single-qubit blocks -> ZYZ Euler angles
# 3. Euler angles -> native RZ/SX (virtual-Z + sqrt-X)
def cnot_lower_bound_2q_generic():
    return 3

Downstream steps

Decomposition feeds routing (mapping logical to physical qubits under connectivity limits) and scheduling. The whole pipeline is transpilation. See KAK decomposition, Shannon decomposition, and transpilation.