A circuit uses a finite vocabulary of gates, but a single-qubit state can rotate through a continuum of angles. How can a finite vocabulary be enough? The answer has two parts: arbitrary one-qubit unitaries have an exact description using continuous rotations, and a suitable finite gate set can approximate those rotations to any prescribed accuracy. Approximation alone does not say how long the circuit must be.
Write for the Pauli matrices, also denoted .
Definition 9.1.1
(Pauli rotation)
For a real angle and , the rotation about axis is
The second equality follows from . We measure error by the operator norm . A global phase on an entire circuit does not change the probabilities of its final measurements. It cannot be discarded from an operation that is later controlled: then it becomes a relative phase between control branches.
Exact continuous decomposition
Theorem 9.1.2
(Euler form for a one-qubit unitary)
Every unitary has real parameters such that
Angles need not be unique; at or some phases can be redistributed.
Proof
(Read the angles from the matrix entries)
Choose so that has determinant one. Orthogonality of its columns and determinant one imply
Choose with and . Direct multiplication gives first-column entries
When both entries are nonzero, choose to match their phases; when one vanishes, choose the remaining phase and any value for the redundant parameter. Both determinant-one unitaries then have the same first column, and hence the same second column. This proves the decomposition.
Worked example 9.1.3
(The Hadamard gate)
Let . Since and ,
Read the rightmost gate first. The factor is a global phase for this stand-alone gate.
Worked example 9.1.4
(The phase gate S: a degenerate Euler form)
Let . Since , we get , so and . In the Euler form only the sum is determined: and both work, because . This is the non-uniqueness mentioned in the theorem.
A finite set can be dense
Let . We show that finite words in approximate every single-qubit unitary up to global phase. Since and , inverses of these gates are themselves finite words.
Definition 9.1.5
(Approximately universal gate set)
A set of single-qubit gates is approximately universal if for every single-qubit unitary and every there are a finite word in and a real with .
Theorem 9.1.6
(Approximate single-qubit universality of H and T)
For every single-qubit unitary and every , a finite word in and a real exist such that .
Proof
(An irrational rotation and two nonparallel axes)
Put and . Up to a global phase, and . Their product, up to phase, is
Write , with a unit vector parallel to . Here
The angle is irrational. Indeed, if it were rational, the eigenvalues would be roots of unity; their sum would be an algebraic integer. But has irreducible monic polynomial over the rationals, whose nonintegral constant term shows that it is not an algebraic integer. This uses the standard facts that sums of algebraic integers are algebraic integers and that the monic minimal polynomial of an algebraic integer has integer coefficients.
Integer multiples of an irrational angle are dense modulo , so powers of approximate every rotation about , up to global sign. Conjugating by produces rotations about parallel to , which is not parallel to . Let be the closure, in operator norm and modulo global phase, of words in . It therefore contains every rotation about both axes.
To see why two axes suffice, contains their arbitrarily small rotations and their inverses. Matrix product limits give rotations generated by any real linear combination of and . The small commutator of those rotations, repeated at scale , converges to a rotation generated by ; the identity supplies the third direction. For the limits just used, set and . For real ,
where . Taylor expansion gives one-step errors and , respectively; telescoping products of unitaries shows that the accumulated errors tend to zero. Scaling the commutator and reversing its order supplies any real coefficient of the third direction. These three vectors span , so product limits provide every . Every determinant-one unitary has this form, for instance by the Euler form above or diagonalization. Thus contains all single-qubit unitaries up to phase. By the definition of closure, a finite word approximates each one to any positive error.
Proof X-ray
What the density proof does and does not give
The proof has two independent inputs. Irrationality of comes from an arithmetic fact, that is not an algebraic integer, and it is what makes the powers of dense in the rotations about ; a rational angle would give only finitely many rotations. The nonparallel conjugate axis is what allows the commutator to produce a third direction, and without it the closure would stay inside the one-parameter group about . The non-obvious move is the Trotter-type limit: products of small rotations about two axes converge to rotations about their combinations and commutator, so the closed set also contains the one-parameter group generated by the commutator. Closure and matrix limits prove existence of a finite word for each accuracy. They do not give a useful gate count or a fast algorithm for finding that word.
Worked example 9.1.7
(Angle and axis of the product A)
With and we have , and . Then and , and indeed . Hence and , so . The axis is , and . Their dot product is , so the axes are not parallel.
Exactness and efficiency are different questions
There are only countably many finite words in a finite alphabet, even after identifying global phases, but uncountably many distinct single-qubit rotations up to phase. Therefore some gates cannot be represented exactly by any finite word. This does not contradict density: a countable set can be dense.
The Solovay–Kitaev theorem gives a stronger efficiency statement. For a fixed finite inverse-closed gate set dense in , there are constants such that any target in can be approximated to error by a word of length polynomial in , with an efficient classical compilation algorithm under the theorem's standard gate-description assumptions. Density by itself supplies no such rate. The theorem is stated here, not proved; global-phase conventions must be handled when applying it to . A multi-qubit universal set additionally needs an entangling gate, such as CNOT, together with single-qubit gates; the present proof establishes only the one-qubit part.
Common mistake
(Dense does not mean exactly representable)
That finite words in come arbitrarily close to every unitary does not mean each unitary equals some word. The set of words is countable while the set of unitaries is not, so most unitaries are limits of words but not words themselves.
Common mistake
(Discarding a global phase inside a controlled gate)
The identity is harmless for the stand-alone gate. If both gates are controlled, controlled- equals controlled- followed by the phase gate on the control qubit, because the factor is applied only on the control-one branch, where it is a relative phase. The two controlled gates therefore differ as operators.
Counterexample mode
One axis is not enough
All products of , even with arbitrary real angles, are diagonal. For any diagonal unitary , is a multiple of , whereas . Their distance on this input is at least . Thus rotations cannot approximate arbitrarily well, even allowing a global phase. A continuum of gates about one axis is still not universal.
Practice with solutions
Quick check
(Verify and explain why this is exact rather than merely true up to phase.)
Use in the power series of the exponential.
Solution · Answer
, so conjugating the power series for the exponential gives . No phase was discarded.
Quick check
(Find angles in the Euler form for , including a global phase.)
Start from and rotate the axis to the axis.
Solution · Answer
. The conjugation rotates the axis to the axis; multiplication confirms the global phase.
Quick check
(Why does the countability argument not identify a particular gate that lacks an exact representation?)
Ask what countability can and cannot decide.
Solution · Answer
Countability proves that at least one gate is absent, in fact uncountably many are, but does not decide membership for a named matrix. Such a decision requires additional algebraic information about the entries of gate words.