Clifford plus T

In plain terms

A quantum computer needs a finite menu of gates, and the menu has to be rich enough that any operation can be approximated by stringing together gates from it. The Clifford gates, the ones that turn simple errors into simple errors, are not rich enough, as a laptop can simulate them. Adding one more gate fixes that, and the usual choice is the T gate, which rotates the phase of one branch of a superposition by an eighth of a turn.

Why one extra gate suffices takes a chain of steps. Any operation on any number of qubits factors exactly into operations that each touch only two levels of the state space, those factor into controlled operations and single-qubit gates, and controls can be built from controlled-not gates. That reduces universality to one qubit. On one qubit, the words built from the Clifford gates and T include rotations by angles that are irrational multiples of a turn, so their powers fill up a circle of rotations, and three such circles about axes that don't line up generate every rotation of the sphere.

The word approximate is doing real work here. No finite gate set gives every unitary exactly, as there are uncountably many unitaries and only countably many circuits, so the claim is that the reachable set is dense: for any target and any tolerance there's a circuit within the tolerance. How long that circuit needs to be is a separate question, answered by the Solovay-Kitaev algorithm.

In CSD

The corpus proves universality as a theorem about a topological closure, and the proof is assembled from rows that are each independently useful. Every unitary is an exact finite product of controlled-not gates and single-qubit gates, obtained from the two-level decomposition, a Gray-code sandwich that relabels a controlled gate onto an adjacent pair, and a recursion that removes controls one at a time. Density on one qubit comes from the axis-angle layer: a Clifford plus T word has a rotation angle that is an irrational multiple of a turn, proved by showing that twice its cosine would otherwise be an algebraic integer it cannot be, so its powers are dense in its own rotation circle, and a cross-product construction supplies a second and third axis that don't line up.

Two joints make the lift work. Sending a single-qubit gate to the many-qubit gate that acts on one qubit is a continuous monoid homomorphism, so it carries closures into closures, and a phase on the small block is a global phase on the big gate, which is what keeps the modulo-phase statement from degenerating into relative phases. The gates that become limits after one global phase form a submonoid, so the exact product inherits a single phase without list bookkeeping. The honest boundary is that this is density without gate counts, so the efficiency statement is a separate open row.

Mathematically

exists_phase_mem_cliffordTmLim: for m at least one, every unitary on m qubits has a global phase making it a member of cliffordTmLim, the closure of the monoid generated by Clifford and T gates on single qubits and controlled-not gates on pairs. The exact product is mem_closure_elementary, from exists_twoLevel_prod (TwoLevel.lean), exists_multiCtrl_sandwich (MultiControlled.lean) and ctrlSetOf_mem_closure (ControlRecursion.lean), joined by block_mem_unitaryGroup_of_ctrlSetOf, the converse that recovers block unitarity by evaluating the unitarity relation at labels differing only on the target.

One-qubit density is exists_phase_mem_cliffordTLim (CliffordTDensity.lean), which needs irrational_htAngle_div_two_pi (CliffordTAngle.lean, via isIntegral_two_mul_cos_of_eq_two_pi_mul), mem_closure_range_axisRot (SU2Rotation.lean), and not_isIntegral_of_quadratic for the cross-product axis. The lift is gateOfHom with continuous_gateOf and gateOf_smul, and the phase bookkeeping is the submonoid phaseLim with elementary_le_phaseLim. No gate counts: the Solovay-Kitaev efficiency statement is BACKLOG row 74 and is not claimed.

The name

The name Clifford honours William Kingdon Clifford, the Victorian mathematician whose algebras underlie the Pauli operators, and it reached quantum computing through Gottesman's stabiliser formalism rather than from Clifford himself. The T gate's role as the cheapest useful addition emerged from fault-tolerance practice, as it's the gate a distillation factory can supply.

Robert Solovay and Alexei Kitaev independently found, in the late 1990s, that any universal set reaches accuracy eps with circuits of length polylogarithmic in one over eps, which turns density into something a compiler can use.

Related entries

• magic stateA magic state is the fuel of quantum advantage, a single special state that, consumed by otherwise classically trackable Clifford circuits, unlocks the one gate the Gottesman-Knill theorem can't simulate.
• Gottesman-Knill theoremThe Gottesman-Knill theorem marks the boundary of quantum advantage, as circuits built from the Clifford gates can be simulated classically, because in the right picture they're nothing more than linear algebra on bits.
• two-level unitaryEvery quantum operation, on any number of qubits, factors exactly into operations that each touch only two levels of the state space, and a count of how many such factors are needed follows from the same elimination that produces them.
• magic-state distillationDistillation turns many noisy magic states into one clean one, by encoding them in a code whose checks reject the likely errors, and the error rate falls as the cube of itself at every round.
• Toffoli gateThe Toffoli gate flips its target only when both controls are set, which is enough to compute anything classically while remaining reversible, and its count is the currency in which the cost of a quantum algorithm is quoted.