Quantum Logic Gates

Clifford+T Synthesis

Compiling arbitrary gates into the fault-tolerant Clifford-plus-T basis, where T-count is the dominant resource.

The fault-tolerant basis

Error-corrected quantum computers work in a discrete gate set, most commonly the Clifford group (H, S, CNOT) plus the T gate. Clifford gates are cheap because they can be implemented transversally in many codes; the T gate is expensive because it requires magic-state distillation. Synthesis for this basis therefore aims above all to minimize the number of T gates.

Why Clifford alone is not enough

Kronos motion — quantum resource

The Gottesman-Knill theorem shows that circuits of only Clifford gates are efficiently simulable on a classical computer, so they cannot provide a quantum advantage. Adding the non-Clifford T gate makes the set universal. The T gate is thus the source of quantum computational power and, being distilled, the dominant cost.

Optimal single-qubit synthesis

For an arbitrary z-rotation RZ(θ) approximated to precision ε, the Ross-Selinger algorithm produces a Clifford+T sequence with T-count close to 3·log2(1/ε), which is provably near-optimal. It uses number theory over the ring Z[1/√2, i] to find the shortest exact word, far better than the generic Solovay-Kitaev bound.

python

import math
def rz_t_count(epsilon):
    # near-optimal Clifford+T T-count for a single RZ(theta)
    return round(3*math.log2(1/epsilon))
print(rz_t_count(1e-10))

T-count and T-depth

Two metrics matter: total T-count (distillation workload) and T-depth (how many layers of T must run in sequence, setting runtime). Circuit optimizers reorder and merge gates to reduce both. Techniques include phase-polynomial synthesis for CNOT+T subcircuits and lattice-based rotation synthesis.

Connections

T gates are applied fault-tolerantly by consuming distilled magic states through gate teleportation. The whole framework rests on the Pauli and Clifford group structure. See gate teleportation, Solovay-Kitaev, and Pauli group.