Quantum Gates and Circuits

Example Quantum Teleportation Circuit

Single-Qubit Gates

All single-qubit gates are 2x2 unitary matrices acting on C^2. They correspond to rotations and reflections on the Bloch sphere.

Pauli Gates

The Pauli matrices form a basis for 2x2 Hermitian traceless matrices:

I = [[1,0],[0,1]] -- identity
X = [[0,1],[1,0]] -- bit flip (NOT), pi rotation about X-axis
Y = [[0,-i],[i,0]] -- combined bit and phase flip, pi rotation about Y-axis
Z = [[1,0],[0,-1]] -- phase flip, pi rotation about Z-axis

Key properties: X^2 = Y^2 = Z^2 = I, XYZ = iI, all are Hermitian and unitary. They anticommute pairwise: {X,Y} = {Y,Z} = {X,Z} = 0.

Maps |0> -> |+> = (|0>+|1>)/sqrt(2) and |1> -> |-> = (|0>-|1>)/sqrt(2). Self-inverse: H^2 = I. Creates uniform superposition -- foundational for most quantum algorithms. H = (X+Z)/sqrt(2), which is a pi rotation about the (X+Z)/sqrt(2) axis.

Phase Gates

S = [[1,0],[0,i]] -- pi/2 phase gate, sqrt(Z). S^2 = Z.
T = [[1,0],[0,e^{i*pi/4}]] -- pi/8 gate, sqrt(S). T^2 = S.

The T gate is crucial because {H, T} generates a dense subset of SU(2). T gates are expensive in fault-tolerant quantum computing, typically requiring magic state distillation.

Rotation Gates

Parameterized single-qubit rotations about Bloch sphere axes:

R_x(theta) = exp(-ithetaX/2) = cos(theta/2)I - i*sin(theta/2)X
R_y(theta) = exp(-ithetaY/2) = cos(theta/2)I - i*sin(theta/2)Y
R_z(theta) = exp(-ithetaZ/2) = [[e^{-itheta/2}, 0], [0, e^{itheta/2}]]

Euler decomposition: Any U in SU(2) can be written as R_z(alpha) R_y(beta) R_z(gamma) for appropriate angles. This provides a canonical parameterization for arbitrary single-qubit gates.

Multi-Qubit Gates

CNOT (Controlled-NOT)

The fundamental two-qubit entangling gate:

CNOT = |0><0| tensor I + |1><1| tensor X

Action: |a,b> -> |a, a XOR b>. Flips the target qubit conditioned on the control being |1>. Combined with single-qubit gates, CNOT is sufficient for universal quantum computation.

CNOT creates entanglement: CNOT(H tensor I)|00> = |Phi+> (Bell state).

Toffoli (CCNOT)

Three-qubit gate: |a,b,c> -> |a,b, c XOR (a AND b)>. Controlled-controlled-NOT. Universal for classical reversible computation. Can be decomposed into 6 CNOTs and single-qubit gates.

The Toffoli gate is not sufficient alone for universal quantum computation (it generates only real amplitudes), but Toffoli + H is universal.

SWAP Gate

SWAP|a,b> = |b,a>. Decomposes into three CNOTs: CNOT_{12} CNOT_{21} CNOT_{12}.

sqrt(SWAP) is an entangling gate. iSWAP = SWAP * (CZ) arises naturally in superconducting architectures.

Controlled-U and Controlled-Phase

CZ (controlled-Z): diagonal gate diag(1,1,1,-1). Symmetric between control and target. CZ = (I tensor H) CNOT (I tensor H).
CU: |0><0| tensor I + |1><1| tensor U for arbitrary single-qubit U.
CP(theta): controlled phase, diag(1,1,1,e^{i*theta}). CZ = CP(pi).

Universal Gate Sets

A gate set is universal if it can approximate any unitary to arbitrary precision.

Common universal sets:

{CNOT, H, T} -- standard for fault-tolerant QC
{CNOT, R_y, R_z} -- continuous parameterization
{Toffoli, H} -- discrete set
{sqrt(SWAP), single-qubit gates}

The Clifford group (generated by {H, S, CNOT}) is NOT universal -- it can be efficiently classically simulated (Gottesman-Knill theorem). Adding any non-Clifford gate (e.g., T) restores universality.

Circuit Model

Quantum circuits represent computations as sequences of gates applied to qubits (wires). Key conventions:

Time flows left to right
Wires represent qubits
Gates are boxes or standard symbols on wires
Measurement is depicted as a meter symbol
Classical wires (double lines) carry measurement outcomes

Circuit depth: maximum number of gate layers (parallelized). Circuit width: number of qubits. Circuit complexity relates to the total gate count.

Circuit Identities

Essential identities for circuit optimization:

HXH = Z, HYH = -Y, HZH = X (Hadamard conjugation swaps X<->Z)
CNOT_{12} (I tensor H) CNOT_{12} = (I tensor H) CZ (I tensor H) -- relating CNOT and CZ
(H tensor H) CNOT_{12} (H tensor H) = CNOT_{21} -- CNOT direction reversal
CNOT_{12} CNOT_{21} CNOT_{12} = SWAP
Two successive CNOTs with same control/target cancel: CNOT^2 = I
(A tensor B)(C tensor D) = (AC) tensor (BD) -- tensor product of independent gates
Controlled-U = (I tensor V) CNOT (I tensor V^dagger) when U = V sigma_z V^dagger -- decomposition pattern

Phase kickback: If U|u> = e^{iphi}|u>, then controlled-U with target |u> kicks the phase onto the control: |+>|u> -> (|0> + e^{iphi}|1>)|u> / sqrt(2). This is the mechanism behind phase estimation.

Bloch Sphere

The Bloch sphere provides geometric visualization for single-qubit states. Pure state |psi> = cos(theta/2)|0> + e^{i*phi}sin(theta/2)|1> maps to the point (sin(theta)cos(phi), sin(theta)sin(phi), cos(theta)) on the unit sphere.

|0> is the north pole, |1> is the south pole
|+>, |-> are on the X-axis equator
|+i>, |-i> are on the Y-axis equator
Gates correspond to rotations: R_n(theta) rotates by angle theta about axis n
Mixed states lie inside the sphere (|r| < 1)
Orthogonal states are antipodal (not perpendicular)
Measurement along axis n projects to one of two antipodal points

The Bloch sphere does not generalize simply to multi-qubit systems (the state space grows exponentially, not linearly).

Solovay-Kitaev Theorem

Theorem: If a finite gate set G generates a dense subgroup of SU(2), then any target gate U in SU(2) can be approximated to precision epsilon using O(log^c(1/epsilon)) gates from G, where c ~ 3.97 (improved to ~1.44 with modern techniques).

Significance: The overhead of compiling arbitrary rotations into a discrete universal gate set is only polylogarithmic -- exponentially better than naive approaches.

Algorithm outline:

Precompute all gate sequences up to a base length, forming an epsilon_0-net over SU(2)
Recursively refine: express the residual error U_target * U_approx^dagger using group commutators [V, W] = VWV^dagger W^dagger
Each recursion level roughly squares the approximation precision

Practical implications: In fault-tolerant QC, gates like R_z(theta) for arbitrary theta must be synthesized from {H, T}. The T-count (number of T gates) is the dominant cost metric. Optimal synthesis algorithms (e.g., Ross-Selinger) achieve T-count ~ 3*log_2(1/epsilon) for single-qubit Z-rotations.

Gate Synthesis and Compilation

Beyond Solovay-Kitaev, practical gate compilation involves:

Unitary decomposition: Any n-qubit unitary decomposes into O(4^n) CNOT gates and single-qubit rotations (Knill's theorem, optimal asymptotically)
KAK decomposition: Any two-qubit gate decomposes into at most 3 CNOTs and single-qubit gates, with the interaction characterized by three parameters
Clifford+T synthesis: Exact synthesis when angles are multiples of pi/4; approximate otherwise
Template matching: Identify and replace subcircuits with equivalent shorter sequences
Peephole optimization: Merge adjacent gates acting on the same qubits

Hardware constraints add further compilation challenges: limited connectivity requires SWAP insertion, native gate sets vary by platform, and noise characteristics influence optimal decomposition choices.