Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Approximate Universality and Solovay–Kitaev

1 · Prerequisites

2 · Summary

This page develops discrete approximate universality and the single-qubit Solovay–Kitaev recursion in operator norm. The recursion assumes an inverse- closed dense gate set and a certified finite base net; it yields polylogarithmic word length, while the bit-complexity item states its finite-precision model and precision schedule separately. Projective phase guarantees apply to a whole unconditional block and must not be silently moved through a control.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Effective Unitary Matrix Input

Definition

A finite gate alphabet is a finite list of distinct labels, each assigned one exact matrix in $S U (2) : = {M \in M_{2} (C) : M^{*} M = I_{2}, \det M = 1}$ . A Cauchy name for a target $U \in S U (2)$ is a deterministic procedure which, on unary input $1^{b}$ , returns a rational $2 \times 2$ complex matrix $Q_{b}$ whose real and imaginary entries differ from the corresponding entries of $U$ by at most $2^{- b}$ . The name has a stated time bound $T (b)$ . A precision request is a positive rational $ε \in (0, 1 / 2)$ in binary, using the effective encoding convention of Effective binary encodings and total decoders.

The Cauchy name specifies the exact target through all its approximants; an individual $Q_{b}$ need not be unitary. An exact-real target handle and a Cauchy-name input are distinct interfaces: the first permits ideal exact comparisons, while a finite Turing implementation must use the second.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Inverse-Closed Dense SU(2) Gate Set

Definition

Write $S U (2) : = {M \in M_{2} (C) : M^{*} M = I_{2}, \det M = 1}$ . An inverse-closed dense $S U (2)$ gate package consists of a finite set $G \subset S U (2)$ of exact matrices with finite labels such that $g^{- 1} = g^{*}$ belongs to $G$ for each $g \in G$ and the subgroup $⟨ G ⟩$ of finite products is dense in $S U (2)$ in operator norm. A word is a finite ordered list of labels; its value is the corresponding matrix product, and its length is the number of labels.

For a compiler package, also fix a rational $0 < η_{0} < 1 / 4096$ , a finite list $N_{0}$ of words, and an integer $L_{0}$ such that every $U \in S U (2)$ is within operator-norm distance $η_{0} / 4$ of the value of some word in $N_{0}$ , and every listed word has length at most $L_{0}$ . This is a finite base-net certificate. Density proves that such a certificate exists, but does not compute the list or its maximum word length.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

Fixed-Dimension Dyadic Matrix Routines Have Polynomial Bit Cost

Statement

Fix a positive matrix dimension $d$ and an integer $c \geq 1$ . A dyadic interval is a closed interval with dyadic-rational endpoints; a complex matrix interval stores one such interval for every real and imaginary entry. Suppose each input is given by a Cauchy procedure which, on unary request $1^{q}$ , returns a rational approximation to each real and imaginary entry with error at most $2^{- q}$ and uses $O ((q + 1)^{c})$ bit operations. Suppose exact scalar and matrix inputs have entries of modulus at most $3$ . Each fixed algebraic real constant is supplied by a rational polynomial and an open rational interval with nonroot endpoints on which the polynomial has opposite endpoint signs and exactly one real root. Here rational outputs and fixed rational data are stored as a sign and binary numerator and positive denominator, separated by a fixed delimiter; the fraction need not be reduced. The complete output length is charged to the Cauchy procedure's bit time. When each scalar divisor and each norm used for normalization has modulus at least $2^{- B}$ , the following routines return dyadic intervals of diameter at most $2^{- p}$ containing the exact answer, using $O ((p + B + 1)^{\max (c, 3)})$ bit operations:

any fixed finite composition of sums and products;
quotient by a scalar whose modulus is at least $2^{- B}$ ;
the nonnegative square root of a real in $[0, 1]$ ;
normalization $v / ∥ v ∥_{2}$ of a real vector with $∥ v ∥_{2} \geq 2^{- B}$ ;
the matrix exponential $e^{A}$ when $∥ A ∥ \leq 1$ ; and
the matrix logarithm $\log (I + E) = \sum_{j \geq 1} (- 1)^{j + 1} E^{j} / j$ when $∥ E ∥ \leq 1 / 2$ .

Here $d$ and the number of scalar operations in the fixed composition are constants. The exponent $B$ is needed only for divisions and normalization; the square-root routine also works at input zero. The constants in the complexity bound may depend on the fixed dimension, routine, and Cauchy-time constant.

Facts & Assumptions

Given: Fixed $d$ , output precision $p \geq 1$ , conditioning bound $B \geq 0$ , and Cauchy input procedures with the cost stated above.

[F1]

Effective binary encodings and total decoders supplies only the abstract encoding/decoder convention. The binary numerator/denominator representation and charged output length are specified in the Statement; their parsing cost is established directly in step 1.1.

[F2]

The operator norm is submultiplicative (The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2).

Proof

1.1F1construct

Query each Cauchy procedure at precision $q + 4$ , obtaining a rational $r$ with $∣ r - x ∣ \leq 2^{- q - 4}$ . Round $r$ to a dyadic $a$ with $∣ a - r ∣ \leq 2^{- q - 4}$ and return $[a - 2^{- q - 3}, a + 2^{- q - 3}]$ ; it contains $x$ and has width $2^{- q - 2}$ . This rounding costs $O (L + q^{2})$ for an $L$ -bit rational: scan its numerator and denominator to determine their binary lengths, discard values below the error tolerance, and otherwise retain their leading $q + O (1)$ bits before long division. Since $∣ r ∣ \leq 4$ , truncating both integers at that relative precision changes the quotient by at most $2^{- q - 5}$ after a fixed guard increase; the dyadic division rounding fits the remaining error budget. The scan costs $O (L)$ and the shortened division $O (q^{2})$ , while $L = O ((q + 1)^{c})$ by the query-time bound. If the fixed composition has no operations, copying this input interval already gives the claimed enclosure. Choose $q = p + K^{'} (B + 1) + K^{'} ⌈ \log_{2} (p + 2) ⌉ + C_{0}$ with sufficiently large fixed $K^{'}, C_{0}$ . The interval endpoints have $O (p + B)$ bits after the binary point. Addition, comparison, and rounding use $O (p + B)$ bit operations; schoolbook multiplication and long division use $O ((p + B)^{2})$ . Outward rounding at $q$ fractional bits adds at most $C 2^{- q}$ local error per operation. Induction through the fixed expression tree, using the input bound $3$ and divisor lower bound $2^{- B}$ , gives a bound $M = 2^{K (B + 1)}$ for all exact intermediate magnitudes and error-amplification factors, with fixed $K$ : sums and products of a fixed number of quantities bounded by $2^{K (B + 1)}$ remain so after increasing $K$ , while a quotient has magnitude at most $M 2^{B}$ and error gain at most $2^{O (B + 1)}$ by the estimate below. The expression has only a fixed number of such operations, so one larger $K$ covers every stage. For a quotient $x / y$ , let $x^{'}, y^{'}$ be its midpoint inputs, each within $δ$ of the exact value, where $δ \leq 2^{- B - 1}$ . Then $∣ y^{'} ∣ \geq 2^{- B - 1}$ and $∣ x^{'} ∣ \leq 2 M$ , so $∣ \frac{x}{y} - \frac{x^{'}}{y^{'}} ∣ \leq 2^{B} δ + M 2^{2 B + 2} δ = 2^{O (B + 1)} δ$ . The stated guard precision therefore makes propagated input and rounding errors at most $2^{- p - 4}$ . Each Cauchy query costs $O ((q + 1)^{c})$ and each dyadic operation costs $O ((p + B)^{2})$ , so the fixed routine costs $O ((p + B + 1)^{\max (c, 2)})$ and encloses the exact answer.

2.1F2step 1.1algebra

To compute $\sqrt{x}$ for $0 \leq x \leq 1$ , request an interval $[x_{-}, x_{+}]$ of width at most $2^{- 2 p - 12}$ and set $ℓ = \max (0, x_{-})$ and $u = \min (1, x_{+})$ . Then $ℓ \leq x \leq u$ and $u - ℓ \leq 2^{- 2 p - 12}$ . The inequality $∣ \sqrt{x} - \sqrt{y} ∣ \leq \sqrt{∣ x - y ∣}$ shows that the input uncertainty contributes at most $2^{- p - 6}$ . Bisect separately for the exact rational endpoints $ℓ, u$ on $[0, 1]$ , comparing squared dyadic midpoints with those endpoints. After $O (p)$ bisections the two square roots are enclosed by dyadic intervals of width at most $2^{- p - 4}$ ; monotonicity encloses $\sqrt{x}$ in their combined interval, whose width is at most $2^{- p - 6} + 2^{- p - 3} < 2^{- p}$ . Each comparison uses $O (p^{2})$ bit operations, so the total is $O (p^{3})$ . For normalization, choose a fixed power of two $R \geq 3 \sqrt{d}$ and compute $∥ v ∥_{2} = R \sqrt{\sum_{i} (v_{i} / R)^{2}}$ to $q$ bits, so the square-root input lies in $[0, 1]$ . The norm changes by at most $∥ v - v^{'} ∥_{2}$ ; division by a norm at least $2^{- B}$ and the preceding division estimate show that $q$ guard bits suffice to return each coordinate of $v / ∥ v ∥_{2}$ within $2^{- p}$ . The vector has fixed dimension, so this costs $O ((p + B + 1)^{\max (c, 3)})$ .

2.2F2step 1.1algebra

Request the entries of $A$ to $q^{'}$ bits, where $q^{'} = p + 2 ⌈ \log_{2} (p + 2) ⌉ + C_{0}$ and $C_{0}$ is a sufficiently large absolute constant. Let $A^{'}$ be the midpoint matrix. Since $d$ is fixed, $∥ A - A^{'} ∥ \leq C 2^{- q^{'}}$ and $∥ A^{'} ∥ \leq 3 / 2$ . The telescoping identity for powers gives $∥ A^{j} - A^{' j} ∥ \leq j (3 / 2)^{j - 1} ∥ A - A^{'} ∥$ , so their exponential series differ by at most $e^{3 / 2} ∥ A - A^{'} ∥$ . Truncate the series for $e^{A^{'}}$ at $m = 24 (p + 2)$ . Using $j! \geq 2^{j - 1}$ , its tail is at most $8 (3 / 4)^{m + 1} < 2^{- p - 4}$ . Compute terms recursively as $T_{0} = I$ and $T_{j} = T_{j - 1} A^{'} / j$ , rounding each product and division outward to $q^{'}$ fractional bits. The error recurrence is $e_{j} \leq (3 / 2) e_{j - 1} / j + C 2^{- q^{'}}$ ; after $j = 1$ , its multiplier is at most $3 / 4$ , so $e_{j} \leq C^{'} 2^{- q^{'}}$ uniformly. Summing $m$ terms contributes at most $C^{'} m 2^{- q^{'}}$ . The choice of $q^{'}$ makes total error, including the input perturbation, less than $2^{- p}$ . There are $O (p)$ products and divisions of fixed-size matrices with $O (p)$ -bit operands, hence the dyadic arithmetic cost is $O ((p + 1)^{3})$ . Including Cauchy queries as in step 1.1, the routine cost is $O ((p + 1)^{\max (c, 3)})$ . For $∥ E ∥ \leq 1 / 2$ , request the entries to the same precision and let $E^{'}$ be the midpoint, so $∥ E^{'} ∥ \leq 3 / 4$ . The series difference between $E$ and $E^{'}$ is bounded by $\sum_{j \geq 1} ∥ E^{j} - E^{' j} ∥ / j \leq 4 ∥ E - E^{'} ∥$ . Truncate the logarithm series for $E^{'}$ at $m = 24 (p + 2)$ . Its tail is at most $\sum_{j > m} (3 / 4)^{j} / j \leq 4 (3 / 4)^{m + 1} < 2^{- p - 4}$ . Successive computed powers have errors bounded by a geometric sum of their rounding errors, since $∥ E^{'} ∥ \leq 3 / 4$ . After multiplication by $1 / j$ and summation, total power, coefficient and outward-rounding error is at most $C (m + 1) 2^{- q^{'}}$ , below $2^{- p - 2}$ after increasing the fixed constant $C_{0}$ . Thus the logarithm interval also has diameter at most $2^{- p}$ and dyadic arithmetic cost $O ((p + 1)^{3})$ ; including Cauchy queries, its cost is $O ((p + 1)^{\max (c, 3)})$ .

3.1F1step 1.1step 2.2∎

Let $α$ be a fixed algebraic real constant, described by a rational polynomial $f$ and an open rational interval with nonroot endpoints on which $f$ has opposite endpoint signs and exactly one real root, namely $α$ . At each bisection, evaluate $f$ exactly at the rational midpoint. If it is a root, return it exactly; otherwise the unique-root and sign-change conditions identify the half containing $α$ . After $O (p)$ bisections the interval has width at most $2^{- p - 3}$ ; round its lower endpoint down and its upper endpoint up to multiples of $2^{- p - 3}$ . The resulting dyadic interval has width at most $3 \cdot 2^{- p - 3} < 2^{- p}$ . An exact rational root is enclosed by the same outward-rounding rule. Each evaluation has $O (p)$ -bit operands and fixed degree, and there are $O (p)$ bisections, giving $O (p^{3})$ bit operations. Real and imaginary parts are handled separately. The number of matrix coordinates is fixed, so all coordinatewise bounds above give the claimed matrix-interval bounds.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Powers of an Irrational Rotation Are Dense on the Circle

Statement

If $α \in R ∖ Q$ , then ${e^{2 π i n α} : n \in Z}$ is dense in the unit circle.

Facts & Assumptions

Given: An irrational real number $α$ .

[F1]

Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ : the unique integer part satisfies $⌊ x ⌋ \leq x < ⌊ x ⌋ + 1$ , so the fractional part ${x} : = x - ⌊ x ⌋$ lies in $[0, 1)$ .

[F2]

The map $β \mapsto e^{2 π i β}$ is continuous and onto the unit circle, and two points agree exactly when their parameters differ by an integer ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ , $\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential, $\ker (\exp) = 2 π i Z$ , and $\exp z = \exp w$ exactly when $z - w \in 2 π i Z$ , $t \mapsto (\cos t, \sin t)$ is a bijection from $[0, 2 π)$ onto the real unit circle, The derivatives of sine and cosine are cosine and minus sine).

Proof

1.1F1givenchoose

Fix an integer $M \geq 2$ . Among the $M + 1$ fractional parts ${j α}$ for $0 \leq j \leq M$ , two lie in one of the $M$ half-open intervals of length $1 / M$ . Their difference is nonzero, since $α$ is irrational, and has absolute value $δ < 1 / M$ . Choosing the sign of the index difference gives an integer $q \neq 0$ with ${q α} = δ$ .

2.1F1F2step 1.1algebrachoose∎

For any $β \in [0, 1)$ , let $k = ⌊ β / δ ⌋$ . Then $0 \leq β - k δ < δ$ and $k δ < 1$ . Since ${k q α} = k δ$ , a power of $e^{2 π i α}$ has parameter within $1 / M$ of $β$ modulo integers. By [F2], this approximates the circle point $e^{2 π i β}$ ; as $M$ is arbitrary, the integer powers are dense.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A Quantitative Logarithm Near the Identity in SU(2)

Statement

For a matrix $M$ , write $e^{M} = \sum_{j \geq 0} M^{j} / j!$ . Here $S U (2) : = {M \in M_{2} (C) : M^{*} M = I_{2}, \det M = 1}$ . If $D \in S U (2)$ and $∥ D - I ∥ \leq ρ \leq 1 / 2$ , then the operator-norm convergent series $\log D = \sum_{j = 1}^{\infty} (- 1)^{j + 1} (D - I)^{j} / j$ satisfies $e^{\log D} = D$ , is traceless and skew-Hermitian, and $∥ \log D ∥ \leq - \log (1 - ρ) \leq 2 ρ$ .

Facts & Assumptions

Given: $D \in S U (2)$ and $∥ D - I ∥ \leq ρ \leq 1 / 2$ .

[F1]

A normal complex matrix has an orthonormal eigenbasis (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

[F2]

The operator norm is submultiplicative (The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2); its triangle inequality follows from the operator-norm definition by applying the vector triangle inequality to each unit input vector and taking the maximum (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

[F3]

The complex exponential is defined by its convergent power series and satisfies the addition identity ( $\exp (z + w) = \exp z \exp w$ , and the complex exponential extends the real exponential).

[F4]

The natural logarithm is the inverse of the real exponential on positive reals (The natural logarithm as the inverse of the exponential function).

[F5]

For real $t$ , $e^{i t} = \cos t + i \sin t$ and $∣ e^{i t} - 1 ∣ = 2 ∣ \sin (t / 2) ∣$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ).

[F6]

For complex $z$ , $e^{z} = 1$ exactly when $z \in 2 π i Z$ ( $\ker (\exp) = 2 π i Z$ , and $\exp z = \exp w$ exactly when $z - w \in 2 π i Z$ ).

[F7]

Every point of the unit circle has a real angular parameter ( $t \mapsto (\cos t, \sin t)$ is a bijection from $[0, 2 π)$ onto the real unit circle).

[F8]

Sine and cosine are continuous and $\sin 0 = 0$ (The derivatives of sine and cosine are cosine and minus sine).

[F9]

Sine is strictly increasing on $[- π / 2, π / 2]$ (Signs, monotonicity intervals, and ranges of sine and cosine).

[F10]

Sine is odd, and the cofunction and double-angle identities include $\sin (π / 6) = \cos (π / 3)$ and $\cos (π / 3) = 1 - 2 \sin^{2} (π / 6)$ (Cofunction, supplementary, quarter-turn, and reflection identities for the six trigonometric functions, Double-angle and quadratic power-reduction identities).

[F11]

A complex power series may be differentiated term by term inside its disc of convergence (Inside its disc of convergence a complex power series is holomorphic and may be differentiated term by term).

[F12]

The complex exponential has derivative itself, complex derivatives obey the chain, product and quotient rules, and a holomorphic function with zero derivative on a domain is constant (The complex exponential is entire and its complex derivative is itself, The chain rule for complex derivatives, Linearity, product, reciprocal, and quotient rules for complex derivatives, A holomorphic function with zero derivative on a domain is constant).

[F13]

A complex-differentiable function is continuous (Complex differentiability at a point implies continuity there).

[F14]

A continuous real-valued function on an interval takes every value between its endpoint values (Intermediate value theorem, by bisection with a canonical left-half rule: a continuous function on $[a, b]$ takes every value between $f (a)$ and $f (b)$ ).

Proof

1.1F1F5F6F7F8F9F10givenalgebra

Put $s = \sin (π / 6)$ . Since $0 < π / 6 < π / 2$ , [F8] and [F9] give $s > 0$ . By [F10], $s = \cos (π / 3) = 1 - 2 s^{2}$ , so $(2 s - 1) (s + 1) = 0$ and positivity gives $s = 1 / 2$ . By [F1], $D$ is unitarily diagonalizable with eigenvalues $λ_{1}, λ_{2}$ on the unit circle. Since $\det D = 1$ , $λ_{1} λ_{2} = 1$ . Choose principal angular representatives $θ_{j} \in (- π, π]$ using [F7]. The norm bound and [F5] give $2 ∣ \sin (θ_{j} / 2) ∣ = ∣ λ_{j} - 1 ∣ \leq ρ \leq 1 / 2$ , hence $∣ \sin (θ_{j} / 2) ∣ \leq 1 / 4 < 1 / 2 = \sin (π / 6)$ . Oddness and strict monotonicity in [F9] force $∣ θ_{j} ∣ < π / 3$ . Now [F6] gives $θ_{1} + θ_{2} \in 2 π Z$ ; the bound on their sum forces $θ_{2} = - θ_{1}$ .

2.1F1F3F5F6F8F9F10F11F12F13F14step 1.1algebra

For $∣ z ∣ < 1$ , the scalar power series $L (z) = \sum_{j \geq 1} (- 1)^{j + 1} z^{j} / j$ converges absolutely by comparison with $\sum_{j \geq 1} ∣ z ∣^{j}$ , so its disc of convergence contains the unit disk. By [F11], $L^{'} (z) = \sum_{j \geq 1} (- 1)^{j + 1} z^{j - 1} = \sum_{k \geq 0} (- z)^{k} = \frac{1}{1 + z},$ where the last equality is the finite geometric-sum identity followed by a limit. Since $1 + z \neq 0$ on the unit disk, [F12] gives ${(\frac{e^{L (z)}}{1 + z})}^{'} = \frac{e^{L (z)} L^{'} (z) (1 + z) - e^{L (z)}}{(1 + z)^{2}} = 0.$ The open unit disk is convex, hence a connected open domain, so [F12] makes this quotient constant there. Its value at $0$ is $1$ , and therefore $e^{L (z)} = 1 + z$ . For $z = e^{i t} - 1$ with $∣ t ∣ < π / 3$ , [F5], [F9], and [F10] show $∣ z ∣ = 2 ∣ \sin (t / 2) ∣ < 1$ . Thus [F6] gives $L (e^{i t} - 1) - i t \in 2 π i Z$ . This difference is continuous in $t$ by [F13], [F5], and [F8]. Dividing it by $2 π i$ gives a continuous integer-valued real function. If it took distinct values at two points, restrict to the closed interval between them; [F14] would force it to take a noninteger value between them; hence it is constant and, at $t = 0$ , zero. Substitution of $z = λ_{j} - 1$ now shows the matrix series diagonalizes to $i θ_{1}, i θ_{2}$ , so exponentiating it gives $D$ .

3.1F1F2F4step 1.1step 2.1algebra∎

By [F2], the norm of the series is at most $\sum_{j \geq 1} ρ^{j} / j$ . The scalar identity from step 2.1 at $z = - ρ$ and [F4] identify this sum with $- \log (1 - ρ)$ . Since $1 / j \leq 1$ and $\sum_{j \geq 1} ρ^{j} = ρ / (1 - ρ) \leq 2 ρ$ for $0 \leq ρ \leq 1 / 2$ , the claimed bound follows. The eigenvalues of $\log D$ are $i θ_{1}, - i θ_{1}$ , so it is skew-Hermitian and has trace zero.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Compactness Gives a Finite SU(2) Base Net

Statement

For every $δ > 0$ and every finite $G \subset S U (2)$ whose generated subgroup is dense, there is a finite list of words in $G$ whose values form a $δ$ -net of $S U (2)$ . The maximum length of the words in that finite list is finite. This is an existence statement; it does not compute a net from the density hypothesis.

Facts & Assumptions

Given: A finite $G \subset S U (2)$ whose generated subgroup is dense and a real $δ > 0$ .

[F1]

The closed unit ball of a finite-dimensional real or complex normed space is compact (The closed unit ball is compact if and only if the normed space is finite-dimensional).

[F2]

The operator norm defines the matrix-space norm used here (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

Proof

1.1F1F2algebra

The ambient space $M_{2} (C)$ is finite-dimensional over $C$ . For $U \in S U (2)$ , norm preservation gives $∥ U ∥ = 1$ by [F2], so $S U (2)$ lies in the closed operator-norm unit ball. It is closed there because $U^{*} U = I$ and $\det U = 1$ are continuous equations in the matrix entries and their conjugates. [F1] makes the closed unit ball compact; therefore its closed subset $S U (2)$ is compact.

2.1F1F2givenstep 1.1construct

Let $S$ be the values of finite words in $G$ and let $H = \overline{S} \subseteq S U (2)$ . Since $S$ is closed under multiplication and matrix multiplication is continuous, $H$ is a closed semigroup. For each integer $n \geq 1$ , let $N_{n}$ be the least number of operator-norm balls of radius $1 / n$ covering $S U (2)$ ; compactness gives such a finite cover. Fix $g \in G$ . Two of $I, g, \dots, g^{N_{n}}$ lie in one cover ball, say $g^{r}, g^{s}$ with $r < s$ . By [F2], $∥ g^{s - r} - I ∥ = ∥ (g^{s} - g^{r}) g^{- r} ∥ < 2 / n$ . Let $d_{n}$ be the least $d \in {1, \dots, N_{n}}$ with $∥ g^{d} - I ∥ < 2 / n$ . If $d_{n} = 1$ for infinitely many $n$ , then $g = I$ and $g^{- 1} = g \in S$ ; otherwise $d_{n} \geq 2$ eventually, and $g^{d_{n} - 1} \in S$ satisfies $∥ g^{d_{n} - 1} - g^{- 1} ∥ = ∥ (g^{d_{n}} - I) g^{- 1} ∥ < 2 / n$ , so $g^{- 1} \in H$ . This holds for every $g \in G$ . Hence $H$ contains $G$ and its inverses, so it contains $⟨ G ⟩$ ; closedness of $H$ and density of $⟨ G ⟩$ give $H = S U (2)$ . Therefore word values in $G$ are dense.

3.1step 1.1step 2.1choose∎

For each $U \in S U (2)$ , density supplies a word value $g_{U} \in S$ with $∥ U - g_{U} ∥ < δ / 2$ . The open balls of radius $δ / 2$ centered at these word values cover $S U (2)$ . Compactness gives a finite subcover with centers $g_{1}, \dots, g_{r}$ . Choose one finite word representing each $g_{j}$ ; the resulting list is a $δ$ -net, and the maximum of its finitely many word lengths is finite. The compactness argument supplies no effective search cutoff or certificate.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Pauli Vector Multiplication and Commutator Formula

Statement

For the Pauli matrices $X, Y, Z$ in The Pauli matrices, the matrices are Hermitian, traceless, and square to $I$ . For $u, v \in R^{3}$ , writing $u \cdot σ = u_{1} X + u_{2} Y + u_{3} Z$ gives $(u \cdot σ) (v \cdot σ) = (u \cdot v) I + i (u \times v) \cdot σ .$ Also, the Pauli triple is a real basis of the traceless Hermitian $2 \times 2$ matrices, $∥ u \cdot σ ∥ = ∣ u ∣$ , and the commutator therefore satisfies $[i u \cdot σ, i v \cdot σ] = - 2 i (u \times v) \cdot σ .$

Facts & Assumptions

Given: The standard Pauli matrices $X = (\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array})$ , $Y = (\begin{array}{cc} 0 & - i \\ i & 0 \end{array})$ , $Z = (\begin{array}{cc} 1 & 0 \\ 0 & - 1 \end{array})$ .

[F1]

The Pauli matrices defines $X, Y, Z$ in the ordered computational basis by the three displayed matrices in its Definition.

Proof

1.1F1algebra

Taking conjugate transposes of the displayed matrices gives $X^{*} = X, Y^{*} = Y, Z^{*} = Z$ , and their traces are all zero. Direct multiplication gives $X^{2} = Y^{2} = Z^{2} = I$ and $X Y = i Z$ , $Y X = - i Z$ , $Y Z = i X$ , $Z Y = - i X$ , $Z X = i Y$ , $X Z = - i Y$ . For example, $X Y = (\begin{array}{cc} i & 0 \\ 0 & - i \end{array}) = i Z$ and $Y X = (\begin{array}{cc} - i & 0 \\ 0 & i \end{array}) = - i Z$ ; the remaining four products are respectively $(\begin{array}{cc} 0 & i \\ i & 0 \end{array}) = i X$ , $(\begin{array}{cc} 0 & - i \\ - i & 0 \end{array}) = - i X$ , $(\begin{array}{cc} 0 & 1 \\ - 1 & 0 \end{array}) = i Y$ , and $(\begin{array}{cc} 0 & - 1 \\ 1 & 0 \end{array}) = - i Y$ .

2.1F1step 1.1algebra

Expand $(u \cdot σ) (v \cdot σ)$ bilinearly. The three diagonal terms are $(u_{1} v_{1} + u_{2} v_{2} + u_{3} v_{3}) I$ by step 1.1. The paired off-diagonal terms are $i (u_{2} v_{3} - u_{3} v_{2}) X + i (u_{3} v_{1} - u_{1} v_{3}) Y + i (u_{1} v_{2} - u_{2} v_{1}) Z$ , exactly $i (u \times v) \cdot σ$ . Put $A = i u \cdot σ$ and $B = i v \cdot σ$ . Then $[A, B] = A B - B A = - (u \cdot σ) (v \cdot σ) + (v \cdot σ) (u \cdot σ)$ ; the vector-product formula and $v \times u = - u \times v$ give $[A, B] = - 2 i (u \times v) \cdot σ$ .

3.1F1step 1.1step 2.1algebra∎

A traceless Hermitian matrix has the form $(\begin{array}{cc} a & b - i c \\ b + i c & - a \end{array})$ with real $a, b, c$ , which equals $b X + c Y + a Z$ . This proves the basis assertion. The product identity at $u = v$ gives $(u \cdot σ)^{2} = ∣ u ∣^{2} I$ ; since $u \cdot σ$ is Hermitian, for every vector $x$ we have $∥ (u \cdot σ) x ∥^{2} = ⟨ (u \cdot σ)^{2} x, x ⟩ = ∣ u ∣^{2} ∥ x ∥^{2}$ . Taking the supremum over unit vectors gives $∥ u \cdot σ ∥ = ∣ u ∣$ . Also $i u \cdot σ$ is traceless skew-Hermitian by the established matrix traces and adjoints.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A Quantitative Balanced Commutator in SU(2)

Statement

For a matrix $M$ , write $e^{M} = \sum_{j \geq 0} M^{j} / j!$ . Here $S U (2) : = {M \in M_{2} (C) : M^{*} M = I_{2}, \det M = 1}$ . If $D \in S U (2)$ and $0 \leq ∥ D - I ∥ \leq η \leq 1 / 16$ , there are $V, W \in S U (2)$ such that $∥ V - I ∥, ∥ W - I ∥ \leq \sqrt{η}, ∥ D - V W V^{*} W^{*} ∥ \leq 40 η^{3 / 2} .$

Facts & Assumptions

Given: $D \in S U (2)$ and $0 \leq ∥ D - I ∥ \leq η \leq 1 / 16$ .

[F1]

The near-identity logarithm is traceless and skew-Hermitian and has norm at most $2 η$ (A Quantitative Logarithm Near the Identity in SU(2)).

[F2]

For real vectors $a, b$ , Pauli multiplication gives $[i a \cdot σ, i b \cdot σ] = - 2 i (a \times b) \cdot σ$ (Pauli Vector Multiplication and Commutator Formula).

[F3]

The operator norm is submultiplicative (The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2).

[F4]

Euler's formula and the Pythagorean identity give $e^{i t} = \cos t + i \sin t$ and $\cos^{2} t + \sin^{2} t = 1$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ).

[F5]

Sine is differentiable with derivative cosine and $\sin 0 = 0$ (The derivatives of sine and cosine are cosine and minus sine); the mean value theorem applies to a continuous function on a closed interval that is differentiable in its interior (The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[F6]

The operator-norm triangle inequality follows from its definition by applying the vector triangle inequality to each unit input and taking the maximum (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

Proof

1.1F1F2givenconstruct

Write $X = \log D = i v \cdot σ$ with $v \in R^{3}$ ; the Pauli matrices form a real basis of the traceless skew-Hermitian $2 \times 2$ matrices, and [F2] gives $∥ X ∥ = ∣ v ∣$ . If $v = 0$ , take $a = b = 0$ and $V = W = I$ . Otherwise set $u = v / ∣ v ∣$ , choose the smallest index $k \in {1, 2, 3}$ attaining $\min_{i} ∣ u_{i} ∣$ , and let $e_{k}$ be the corresponding coordinate vector. Then $w = u \times e_{k}$ has norm at least $\sqrt{2 / 3} > 1 / 2$ ; put $e = w / ∣ w ∣$ . This is a deterministic choice with $e ⊥ u$ . Set $a = \sqrt{∣ v ∣ / 2} e$ and $b = - \sqrt{∣ v ∣ / 2} (u \times e)$ . Then $a \times b = - v / 2$ and $∣ a ∣ = ∣ b ∣ = \sqrt{∣ v ∣ / 2} \leq \sqrt{η}$ .

2.1F2F4F5step 1.1algebra

For every real $t$ , $∣ \sin t ∣ \leq ∣ t ∣$ : it is immediate at $t = 0$ , and otherwise [F5] and the mean value theorem give $\sin t - \sin 0 = \cos (c) t$ for some $c$ between $0$ and $t$ ; [F4] implies $∣ \cos c ∣ \leq 1$ . Put $A = i a \cdot σ$ , $B = i b \cdot σ$ , $V = e^{A}$ and $W = e^{B}$ . For $a \neq 0$ , $P = a \cdot σ / ∣ a ∣$ is Hermitian, traceless and satisfies $P^{2} = I$ by [F2]; its eigenvalues are $1, - 1$ . Thus $e^{A} = I \cos ∣ a ∣ + i P \sin ∣ a ∣$ by the power series and [F4], so it is unitary with determinant $1$ and $∥ e^{A} - I ∥ = 2 ∣ \sin (∣ a ∣ / 2) ∣ \leq ∣ a ∣$ . If $a = 0$ , $e^{A} = I$ ; the same argument applies to $B$ . By [F2], $[A, B] = X$ , and both distances are at most $\sqrt{η}$ .

3.1F3F6step 2.1algebra

Expand $e^{A} e^{B} e^{- A} e^{- B}$ as a sum of homogeneous terms in $A, B$ . Its degree-one terms cancel, and direct multiplication of the degree-two terms gives $A B - B A = [A, B]$ . By [F3], products have norm at most the product of their norms; the triangle inequality [F6] therefore bounds the sum of norms of all terms of total degree $n$ by $(4 s)^{n} / n!$ , where $s = \max (∥ A ∥, ∥ B ∥) \leq 1 / 4$ . Hence the degree-at-least-three remainder has norm at most $(4 s)^{3} e^{4 s} / 6 < 32 s^{3}$ .

4.1F1F3F6step 2.1step 3.1algebra∎

The exponential series and [F3] give $∥ e^{X} - I - X ∥ \leq ∥ X ∥^{2} e^{∥ X ∥} / 2 \leq 2 s^{4} e^{2 s^{2}} \leq s^{3}$ , since $∥ X ∥ = ∥ [A, B] ∥ \leq 2 s^{2}$ and $s \leq 1 / 4$ . By the triangle inequality [F6], $∥ e^{X} - e^{A} e^{B} e^{- A} e^{- B} ∥ \leq 33 s^{3} \leq 40 η^{3 / 2}$ . By [F1], $e^{X} = D$ ; step 2.1 gives $[A, B] = X$ , and step 3.1 controls the commutator expansion. These facts prove the claim.

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Two Nonparallel One-Parameter Subgroups Generate SU(2) After Closure

Statement

For a matrix $M$ , write $e^{M} = \sum_{j \geq 0} M^{j} / j!$ . Write $S U (2) : = {M \in M_{2} (C) : M^{*} M = I_{2}, \det M = 1}$ . Let $a, b \in R^{3}$ be nonparallel unit vectors, let $σ = (X, Y, Z)$ be the Pauli triple, and put $A = i a \cdot σ$ and $B = i b \cdot σ$ . If $H$ is the operator-norm closure of the subgroup generated by ${e^{t A}, e^{t B} : t \in R}$ , then $H = S U (2)$ .

Facts & Assumptions

Given: Nonparallel unit vectors $a, b \in R^{3}$ and the Pauli matrices $X, Y, Z$ .

[F1]

The Pauli-vector product and commutator identities hold, and the Pauli triple is a real basis of traceless Hermitian $2 \times 2$ matrices (Pauli Vector Multiplication and Commutator Formula).

[F2]

[F3]

The operator norm is submultiplicative (The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2).

[F4]

Proof

1.1F1F2F4givenalgebra

Put $P_{a} = a \cdot σ$ . By [F1], $P_{a} = P_{a}^{*}$ , $P_{a}^{2} = I$ and $tr P_{a} = 0$ . Its eigenvalues are $1, - 1$ by [F2], so the power series gives $e^{t A} = I \cos t + i P_{a} \sin t$ and its eigenvalues are $e^{i t}, e^{- i t}$ . By [F4] it is unitary, and its determinant is one. The same holds for $B$ . Thus the generated subgroup lies in $S U (2)$ ; its closure $H$ also lies there because the defining matrix equations for $S U (2)$ are closed. Continuity of multiplication and inversion makes $H$ a subgroup.

2.1F1F3step 1.1construct

By [F1], $[A, B] = - 2 i (a \times b) \cdot σ$ . Let $c = a \times b \neq 0$ and $s_{0} = \max (∥ A ∥, ∥ B ∥)$ . For $∣ t ∣ \leq 1$ , multiplying the four exponential series $e^{t A} e^{t B} e^{- t A} e^{- t B}$ gives degree-one coefficient $A + B - A - B = 0$ and degree-two coefficient $A B - B A = [A, B]$ . Submultiplicativity bounds the sum of norms of all degree- $m$ terms by $(4 s_{0})^{m} / m!$ . Hence the terms of degree at least three have norm at most $K ∣ t ∣^{3}$ , where $K = (4 s_{0})^{3} e^{4 s_{0}} / 6$ . For fixed $r \geq 0$ , put $t = \sqrt{r / n}$ . The commutator factor is $X_{n} = I + r [A, B] / n + R_{n}$ with $∥ R_{n} ∥ \leq K r^{3 / 2} n^{- 3 / 2}$ . Set $Y_{n} = I + r [A, B] / n$ . For fixed $r$ , the norms of $X_{n}^{k}$ and $Y_{n}^{k}$ are bounded uniformly over $0 \leq k \leq n$ , because each one-step norm is at most $1 + C_{r} / n$ for all sufficiently large $n$ . The telescoping identity $X_{n}^{n} - Y_{n}^{n} = \sum_{k = 0}^{n - 1} X_{n}^{n - 1 - k} (X_{n} - Y_{n}) Y_{n}^{k}$ bounds their difference by $O (n^{- 1 / 2})$ . The binomial expansion of $Y_{n}^{n}$ converges to the exponential series for $e^{r [A, B]}$ : its $k$ th term is bounded by $(r ∥ [A, B] ∥)^{k} / k!$ , a summable sequence. Swapping $A$ and $B$ gives $e^{- r [A, B]}$ for $r \geq 0$ . Every approximant belongs to the generated subgroup, so closedness gives $e^{s [A, B]} \in H$ for every real $s$ .

3.1F1step 1.1step 2.1algebra

The vectors $a, b, c$ form a basis of $R^{3}$ , since $c$ is nonzero and orthogonal to both $a$ and $b$ . By [F1], every traceless skew-Hermitian $2 \times 2$ matrix $L$ is a real linear combination $x A + y B + z [A, B]$ . For fixed matrices $S, T$ , exponential-series expansion gives $e^{S / n} e^{T / n} = I + (S + T) / n + O (n^{- 2})$ and $e^{(S + T) / n} = I + (S + T) / n + O (n^{- 2})$ . The one-step difference is $O (n^{- 2})$ ; the norms of intermediate powers up to $n$ are bounded by $e^{∥ S ∥ + ∥ T ∥ + 1}$ for sufficiently large $n$ . Telescoping therefore gives $(e^{S / n} e^{T / n})^{n} \to e^{S + T}$ . The same estimate for three factors gives $(e^{x A / n} e^{y B / n} e^{z [A, B] / n})^{n} \to e^{L}$ . Every factor lies in $H$ by step 1.1 and step 2.1, so closedness gives $e^{L} \in H$ .

4.1F2step 1.1step 3.1algebra∎

Every $U \in S U (2)$ is normal, so [F2] diagonalizes it. Its eigenvalues lie on the unit circle and their product is one, so they are $e^{i θ}, e^{- i θ}$ for some real $θ$ . In that orthonormal eigenbasis, the matrix with diagonal entries $i θ, - i θ$ is traceless and skew-Hermitian, and its exponential is $U$ . Step 3.1 gives $U \in H$ . Since $H \subseteq S U (2)$ by step 1.1, $H = S U (2)$ .

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Clifford+T Is Dense Projectively on One Qubit

Statement

Use the Pauli matrices $X, Y, Z$ and exact gates $H = (X + Z) / \sqrt{2}$ and $T = diag (1, e^{i π / 4})$ from The Pauli matrices and Exact one-qubit gates and rotations. Write $P U (2)$ for the quotient of $U (2)$ by its unit-modulus scalar matrices, equipped with the quotient topology. Their normalized lifts $h = i H$ and $t = e^{- i π / 8} T$ lie in $S U (2)$ and generate a dense subgroup of $S U (2)$ ; therefore the projective classes of $H, T$ generate a dense subgroup of $P U (2)$ .

Facts & Assumptions

Given: The exact Pauli matrices and one-qubit gates identified in the Statement.

[F1]

Pauli Vector Multiplication and Commutator Formula: the matrices $X, Y, Z$ are Hermitian and traceless, satisfy the Pauli vector product formula, and form a real basis of traceless Hermitian $2 \times 2$ matrices.

[F2]

The monic minimal polynomial of an algebraic integer over $Q$ has integer coefficients (Minimal-polynomial criterion for algebraic integers).

[F3]

A number field is a finite extension of $Q$ (Number field).

[F4]

Powers of an irrational rotation are dense on the circle (Powers of an Irrational Rotation Are Dense on the Circle).

[F5]

Two nonparallel one-parameter subgroups about Pauli axes have closure $S U (2)$ (Two Nonparallel One-Parameter Subgroups Generate SU(2) After Closure).

[F6]

Euler's formula gives $e^{i t} = \cos t + i \sin t$ for real $t$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ).

[F7]

A unitary matrix has an orthonormal eigenbasis (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

[F8]

Sine and cosine are continuous, with $\sin 0 = 0$ and $\cos 0 = 1$ (The derivatives of sine and cosine are cosine and minus sine).

[F9]

Exact one-qubit gates and rotations: in the ordered computational basis, $H = (X + Z) / \sqrt{2}$ and $T = diag (1, e^{i π / 4})$ with the displayed scalar phases kept exactly.

[F10]

Every unit-modulus complex number has a real angular parameter ( $t \mapsto (\cos t, \sin t)$ is a bijection from $[0, 2 π)$ onto the real unit circle).

[F11]

Cosine is strictly decreasing on $[0, π]$ (Signs, monotonicity intervals, and ranges of sine and cosine).

[F12]

The cosine addition formula gives $\cos (2 u) = \cos^{2} u - \sin^{2} u$ (The addition formulas for sine and cosine), and $\cos (π / 2) = 0$ (Quarter-turn values and shifts by pi/2 and pi). Together with the Pythagorean identity from [F6], this gives $\cos (2 u) = 2 \cos^{2} u - 1 = 1 - 2 \sin^{2} u$ .

Proof

1.1F1F6F9F11F12givenalgebra

From [F1] and [F9], $X, Z$ are Hermitian and traceless, and $X^{2} = Z^{2} = I$ , $X Z = - i Y$ , $Z X = i Y$ . Hence $H^{*} = H$ , $tr H = 0$ and $H^{2} = (X^{2} + X Z + Z X + Z^{2}) / 2 = I$ . Directly, $H = 2^{- 1 / 2} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array})$ has determinant $- 1$ , so $h = i H$ is unitary with determinant $1$ . By [F6], $t = e^{- i π / 8} T = diag (e^{- i π / 8}, e^{i π / 8})$ is also in $S U (2)$ . Put $V = h t$ , $s = \sin (π / 8)$ and $c = \cos (π / 8)$ . Multiplying the displayed Pauli matrices gives $V = (s / \sqrt{2}) I + i (c X - s Y + c Z) / \sqrt{2}$ ; hence $tr V = \sqrt{2} s = : x$ . By [F12], $0 = \cos (π / 2) = 2 \cos^{2} (π / 4) - 1$ . Since $0 < π / 4 < π / 2$ and cosine is strictly decreasing by [F11], $\cos (π / 4) > \cos (π / 2) = 0$ , hence $\cos (π / 4) = 1 / \sqrt{2} = \sqrt{2} / 2$ . Applying the other double-angle form in [F12] at $u = π / 8$ gives $\sqrt{2} / 2 = 1 - 2 s^{2}$ . Therefore $x^{2} = 2 s^{2} = 1 - \sqrt{2} / 2$ .

2.1F2F3step 1.1algebra

The number $x$ is a root of the monic rational quartic $P (X) = X^{4} - 2 X^{2} + 1 / 2$ . It has no rational root: if $r \in Q$ were a root, then $r^{2}$ would solve $z^{2} - 2 z + 1 / 2 = 0$ , whose roots $1 \pm \sqrt{2} / 2$ are irrational. Indeed, if $\sqrt{2} = a / b$ in lowest terms, then $a^{2} = 2 b^{2}$ is even, so $a$ is even because an odd integer has odd square. Substituting $a = 2 c$ gives $b^{2} = 2 c^{2}$ even, so $b$ is even too, a contradiction. If $P$ factored over $Q$ , its lack of a rational root forces a factorization into two monic rational quadratics; write $P = (X^{2} + a X + b) (X^{2} - a X + d)$ . Comparing coefficients gives $a (d - b) = 0$ , $b + d - a^{2} = - 2$ , and $b d = 1 / 2$ . If $a = 0$ , then $b, d$ would be rational roots of $Z^{2} + 2 Z + 1 / 2$ , whose discriminant is $2$ , not a rational square. If $d = b$ , then $b^{2} = 1 / 2$ , also impossible in $Q$ . Thus $P$ is irreducible and is the monic minimal polynomial of $x$ . Every power of $x$ reduces using $P (x) = 0$ to a rational linear combination of $1, x, x^{2}, x^{3}$ , while these four powers are linearly independent over $Q$ by irreducibility of $P$ . Hence $[Q (x) : Q] = 4$ , so $Q (x)$ is a number field by [F3]. Finally [F2] shows $x$ is not an algebraic integer because $P \notin Z [X]$ .

3.1step 2.1algebra

Write the eigenvalues of $V$ as $e^{i α}, e^{- i α}$ , so $x = 2 \cos α$ . If $α / π$ were rational, these eigenvalues would be roots of unity. For each positive integer $m$ , the polynomials $S_{0} = 2$ , $S_{1} = X$ , $S_{m + 1} = X S_{m} - S_{m - 1}$ are monic integer polynomials for $m \geq 1$ and satisfy $S_{m} (λ + λ^{- 1}) = λ^{m} + λ^{- m}$ . For a root of unity of order $m$ , this makes $x$ a root of the monic integer polynomial $S_{m} (X) - 2$ , contradicting step 2.1. Hence $α / π$ is irrational.

4.1F1F4F6F7F8F11step 1.1step 3.1algebra

By [F7], $V \in S U (2)$ has eigenvalues $e^{i α}, e^{- i α}$ . Step 3.1 makes $α / (2 π)$ irrational, so [F4] makes its integer multiples dense modulo one. Diagonalizing $V$ shows its powers are dense in the torus ${Q diag (e^{i t}, e^{- i t}) Q^{*} : t \in R}$ , because the parametrization is continuous and $2 π$ -periodic by [F6,F8]. The Pauli-vector part of the explicit matrix in step 1.1 is proportional to $v = (c, - s, c)$ , where $c = \cos (π / 8)$ and $s = \sin (π / 8)$ . Since $x = \sqrt{2} s$ and $x^{2} = 1 - \sqrt{2} / 2$ , the Pythagorean identity gives $c^{2} = 1 - s^{2} = 1 - x^{2} / 2 > 1 / 2$ , so both the $Z$ coordinate $c$ and the $X Y$ component $(c, - s)$ of $v$ are nonzero. The subgroup generated by $h, t$ contains $t V t^{- 1}$ , so its closure also contains the conjugate torus. Conjugation by $t = \exp (- i π Z / 8)$ rotates Pauli vectors about the $Z$ axis by $π / 4$ : direct multiplication gives $t X t^{*} = \cos (π / 4) X + \sin (π / 4) Y$ and $t Y t^{*} = - \sin (π / 4) X + \cos (π / 4) Y$ , while $t Z t^{*} = Z$ . If the rotated vector were parallel to $v$ , the nonzero $Z$ coordinate would force the scalar to be $1$ , so the nonzero vector $(c, - s)$ would be fixed by the planar rotation $R_{π / 4}$ . But $\det (R_{π / 4} - I) = 2 (1 - \cos (π / 4)) > 0$ by [F11], so no nonzero planar vector is fixed. Hence the two axes are nonparallel. Normalize them as $a = v / ∣ v ∣$ and $b = R_{z} (π / 4) v / ∣ v ∣$ ; they are nonparallel unit vectors because planar rotations preserve Euclidean length. Thus the closure contains the one-parameter subgroups about two nonparallel unit axes.

5.1F5F6F10step 4.1algebra∎

By [F5] the closure of the subgroup generated by $h, t$ is $S U (2)$ . The quotient map from $S U (2)$ to $P U (2)$ is continuous by the quotient topology. It is onto: for any $Q \in U (2)$ , unitarity gives $∣ \det Q ∣ = 1$ . By [F10] and Euler's formula [F6], write $\det Q = e^{i θ}$ and set $λ = e^{- i θ / 2}$ . Then $∣ λ ∣ = 1$ , $λ^{2} = (\det Q)^{- 1}$ , and $λ Q \in S U (2)$ has the same projective class as $Q$ . A continuous image of a dense subset is dense in the image, so the projective classes of words in $h, t$ are dense in $P U (2)$ . Finally $h = i H$ and $t = e^{- i π / 8} T$ , so these classes equal those of $H, T$ .

LemmaStatement: AI-adaptedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Error Cancellation in an SU(2) Commutator

Statement

Let $V, W, \tilde{V}, \tilde{W} \in S U (2)$ and $0 \leq η \leq 1 / 16$ , with $∥ V - I ∥, ∥ W - I ∥ \leq \sqrt{η}$ and $∥ \tilde{V} - V ∥, ∥ \tilde{W} - W ∥ \leq η$ . Then $∥ V W V^{*} W^{*} - \tilde{V} \tilde{W} {\tilde{V}}^{*} {\tilde{W}}^{*} ∥ \leq 4 η^{3 / 2} + 2 η^{2} \leq 5 η^{3 / 2} .$

Facts & Assumptions

Given: Four unitary matrices with the stated distances, where $0 \leq η \leq 1 / 16$ .

[F1]

The operator norm is defined as the maximum over unit vectors (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

[F2]

The operator norm is submultiplicative (The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2).

Proof

1.1givenF1algebra

From [F1], left multiplication by a unitary $Q$ preserves norm because $∥ Q X v ∥ = ∥ X v ∥$ for each unit vector $v$ ; right multiplication preserves norm because $Q$ maps the unit sphere bijectively to itself. Taking $X = I$ also gives $∥ Q ∥ = 1$ . Set $E = V^{*} \tilde{V}$ and $F = W^{*} \tilde{W}$ . Then $E, F$ are unitary, $∥ E - I ∥ = ∥ V^{*} (\tilde{V} - V) ∥ = ∥ \tilde{V} - V ∥ \leq η$ , and $∥ F - I ∥ = ∥ W^{*} (\tilde{W} - W) ∥ = ∥ \tilde{W} - W ∥ \leq η$ .

2.1F1F2step 1.1algebra

Keeping $W$ fixed, the commutator difference caused by replacing $V$ by $\tilde{V} = V E$ is $V (E W E^{*} - W) V^{*} W^{*}$ . Unitary left and right multiplication from [F1] leave its norm equal to $∥ E W E^{*} - W ∥$ . Since $E E^{*} = I$ , $E W E^{*} - W = E (W - I) E^{*} - (W - I) = (E - I) (W - I) E^{*} + (W - I) (E^{*} - I)$ . Unitary norm invariance, $∥ E^{*} ∥ = 1$ , and $∥ E^{*} - I ∥ = ∥ E - I ∥$ bound this by $2 ∥ E - I ∥ ∥ W - I ∥ \leq 2 η^{3 / 2}$ ; the equality $∥ E^{*} - I ∥ = ∥ E - I ∥$ follows from $E^{*} - I = - E^{*} (E - I)$ .

3.1F1F2step 1.1step 2.1algebra∎

After the first replacement, keep $\tilde{V}$ fixed and replace $W$ by $\tilde{W} = W F$ . The commutator difference is $\tilde{V} W (F {\tilde{V}}^{*} F^{*} - {\tilde{V}}^{*}) W^{*}$ . The expansion in step 2.1, with ${\tilde{V}}^{*} - I$ in place of $W - I$ , bounds its norm by $2 ∥ F - I ∥ ∥ \tilde{V} - I ∥ \leq 2 η (\sqrt{η} + η)$ , since $∥ \tilde{V} - I ∥ \leq ∥ V - I ∥ + ∥ \tilde{V} - V ∥ \leq \sqrt{η} + η$ . The operator-norm triangle inequality follows from [F1] and the vector triangle inequality by taking the maximum over unit vectors. Combining the two replacements gives $4 η^{3 / 2} + 2 η^{2} \leq 5 η^{3 / 2}$ because $η \leq 1 / 16$ .

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Solovay–Kitaev Unitary Compiler for SU(2)

Definition

Inputs: A fixed inverse-closed dense gate package $G$ with the finite base-net certificate $(N_{0}, η_{0}, L_{0})$ from Inverse-Closed Dense SU(2) Gate Set, an exact-real target $U \in S U (2)$ , and a rational $0 < ε \leq η_{0}$ . This is an ideal exact-real procedure: fixed-dimensional exact matrix arithmetic, matrix logarithm/exponential, and exact comparisons are unit-cost operations. It is not, by this definition alone, a finite Turing algorithm.

Set $η_{j + 1} = 64 η_{j}^{3 / 2}$ for $j \geq 0$ . Choose the least integer $J \geq 0$ with $η_{J} \leq ε$ . Define $Compile (U, j)$ recursively:

If $j = 0$ , return the first word $A \in N_{0}$ with $∥ U - A ∥ \leq η_{0}$ .
If $j > 0$ , set $A = Compile (U, j - 1)$ and $D = U A^{*}$ . If $D = I$ , set $V = W = I$ . Otherwise apply the Pauli-coordinate construction in A Quantitative Balanced Commutator in SU(2) to $D$ and $η_{j - 1}$ , obtaining $V, W \in S U (2)$ with $D$ approximated by $V W V^{*} W^{*}$ .
Set $B = Compile (V, j - 1)$ and $C = Compile (W, j - 1)$ . Return the word $B C B^{*} C^{*} A$ . Store concatenations and inverses as a shared expression DAG; an inverse word is formed by reversing its label order and replacing each label by its listed inverse. Expanding the DAG writes the ordinary gate word.

Return $Compile (U, J)$ . The recursion depth is finite because each call decreases the nonnegative integer $j$ .

Well-definedness

Solovay–Kitaev Error and Resource Bound ↗ establishes this procedure's level existence and recursive admissibility: its step 3.1 gives the least finite $J$ , while steps 1.1–2.1 give the inductive bound $∥ D - I ∥ \leq η_{j - 1}$ for every balanced-commutator call. The displayed level formula has $0 < η_{j} \leq η_{0} < 64^{- 2} < 1 / 16$ , so each such call satisfies the lemma's norm and radius hypotheses. The base-net certificate supplies the level-zero choice. This is the well-definedness justification for the instructions above; the error and resource conclusions are stated and proved in that theorem.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Solovay–Kitaev Error and Resource Bound

Statement

For a fixed inverse-closed dense $G \subset S U (2)$ and a certified base net of radius $0 < η_{0} < 64^{- 2}$ and a target $U \in S U (2)$ , the level recursion $Compile (U, J)$ of Solovay–Kitaev Unitary Compiler for SU(2) returns, for every real $0 < ε \leq η_{0}$ , a word $W$ with $∥ U - W ∥ \leq ε$ , where $J$ is the least nonnegative integer with $η_{J} \leq ε$ . For a real tolerance this means selecting $J$ by ideal exact-real comparisons and calling the level subroutine directly; the algorithm's top-level tolerance input is rational. The level errors may be chosen as $η_{j} = 64^{- 2} (64^{2} η_{0})^{(3 / 2)^{j}} .$ The word length is at most $L_{0} 5^{j}$ at level $j$ , hence $O (\log^{\log_{3 / 2} 5} (1 / ε)) = O (\log^{3.97} (1 / ε))$ . With shared recursive words, the exact-real arithmetic count is $O (\log^{\log_{3 / 2} 3} (1 / ε)) = O (\log^{2.71} (1 / ε))$ ; printing the expanded word takes $O (\log^{3.97} (1 / ε))$ time. The latter are exact-real arithmetic bounds, not bit-complexity bounds.

Facts & Assumptions

Given: The fixed gate package and base-net certificate, a target $U \in S U (2)$ , and a real $0 < ε \leq η_{0} < 64^{- 2}$ , with ideal exact-real comparisons for selecting the level.

[F1]

The compiler uses a level-zero word within $η_{0}$ and at each later level uses one lower-level approximation to $U$ and two to the balanced commutator factors (Solovay–Kitaev Unitary Compiler for SU(2)).

[F2]

If $∥ D - I ∥ \leq η \leq 1 / 16$ , there are $V, W$ within $\sqrt{η}$ of $I$ whose commutator is within $40 η^{3 / 2}$ of $D$ (A Quantitative Balanced Commutator in SU(2)).

[F3]

Approximating each of $V, W$ within $η$ changes their commutator by at most $5 η^{3 / 2}$ when both are within $\sqrt{η}$ of $I$ (Error Cancellation in an SU(2) Commutator).

[F4]

Every compiled gate word is unitary because its letters lie in $G \subset S U (2)$ (Inverse-Closed Dense SU(2) Gate Set). From the operator-norm definition (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||), left multiplication by a unitary preserves norm because it preserves vector norms, and right multiplication preserves norm because it maps the unit sphere bijectively to itself.

[F5]

$\log$ denotes the natural logarithm, the inverse of the positive real exponential; it is strictly increasing, $\log 1 = 0$ , and it obeys the product and reciprocal laws. For $b > 0$ , $b \neq 1$ , set $\log_{b} x : = \log x / \log b$ . For $x > 0$ and real $t$ , use $x^{t} : = \exp (t \log x)$ ; the logarithm product law and inverse relation imply $(x y)^{t} = x^{t} y^{t}$ and $(x^{s})^{t} = x^{s t}$ for positive $x, y$ and real $s, t$ . Also $⌈ y ⌉ : = - ⌊ - y ⌋$ , where $⌊ \cdot ⌋$ is the integer part (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ ).

Proof

1.1F1F4givenalgebra

We prove by induction that level $j$ has error at most $η_{j}$ . The base net gives error at most $η_{0}$ at level zero. Suppose the lower-level word $A$ has error at most $η_{j - 1}$ . Since $A$ is unitary, right multiplication by $A^{*}$ maps the unit sphere bijectively to itself; the operator-norm definition in [F4] therefore gives $∥ D - I ∥ = ∥ (U - A) A^{*} ∥ = ∥ U - A ∥ \leq η_{j - 1}$ .

2.1F1F2F3F4step 1.1algebra

By [F2] choose $V, W$ within $\sqrt{η_{j - 1}}$ of $I$ whose exact commutator differs from $D$ by at most $40 η_{j - 1}^{3 / 2}$ . The level- $(j - 1)$ words $B, C$ approximate $V, W$ within $η_{j - 1}$ , so [F3] bounds the additional commutator error by $5 η_{j - 1}^{3 / 2}$ . The combined bound follows from the operator-norm triangle inequality, which follows from [F4] and the vector triangle inequality. If $C_{0} = B C B^{*} C^{*} A$ , then $U - C_{0} = (D - B C B^{*} C^{*}) A$ ; right multiplication by the unitary $A$ preserves norm by [F4]. Thus the returned word approximates $U$ to at most $45 η_{j - 1}^{3 / 2} \leq 64 η_{j - 1}^{3 / 2} = η_{j}$ .

3.1F5step 2.1algebra

Set $q_{j} = 64^{2} η_{j}$ and $q_{0} = 64^{2} η_{0} \in (0, 1)$ . The recurrence gives $q_{j + 1} = q_{j}^{3 / 2}$ ; with the positive-real-power convention in [F5], induction yields $q_{j} = q_{0}^{(3 / 2)^{j}}$ and hence the displayed error formula. Put $q_{ε} = 64^{2} ε \in (0, q_{0}]$ . Since $\log$ is strictly increasing and obeys the reciprocal law [F5], $η_{j} \leq ε$ is equivalent to ${(\frac{3}{2})}^{j} \geq \frac{\log (1 / q_{ε})}{\log (1 / q_{0})} .$ The ratio is at least $1$ , and $\log_{3 / 2}$ is increasing because $3 / 2 > 1$ and $\log$ is strictly increasing. Thus the least nonnegative integer level is $J = ⌈ \log_{3 / 2} \frac{\log (1 / (64^{2} ε))}{\log (1 / (64^{2} η_{0}))} ⌉,$ with the ceiling convention in [F5].

4.1F1step 3.1algebra∎

The recursive word contains two copies each of the level- $(j - 1)$ words $B, C$ and one copy of $A$ , so its length is at most $5 L_{j - 1}$ and hence at most $L_{0} 5^{j}$ . The recursion tree has three recursive calls per node, so its shared-DAG arithmetic count is $O (3^{j})$ ; expanding and printing the word takes at most $O (5^{j})$ . Since $j = O (\log \log (1 / ε))$ , these are respectively $O (\log^{\log_{3 / 2} 3} (1 / ε))$ and $O (\log^{\log_{3 / 2} 5} (1 / ε))$ .

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Finite-Precision Bit Complexity of the SU(2) Solovay–Kitaev Compiler

Statement

Fix a finite inverse-closed dense $G \subset S U (2)$ whose real and imaginary gate-entry coordinates are algebraic numbers supplied by their minimal polynomials over $Q$ and rational isolating intervals with opposite endpoint signs and exactly one real root, and fix a rational certified base-net radius $0 < η_{0} < 64^{- 2}$ . Let the finite base-net certificate be fixed. Suppose $U \in S U (2)$ is given by a Cauchy name whose query on unary input $1^{b}$ takes at most $(b + 1)^{c}$ bit operations for a fixed integer $c \geq 1$ . Given rational $0 < ε \leq η_{0}$ encoded as $ε = p / q$ by positive binary integers $p, q$ with a fixed delimiter (not necessarily reduced), there is a deterministic Turing implementation of the Solovay–Kitaev recursion that outputs a gate word $W$ with $∥ U - W ∥ \leq ε$ and length $O (\log^{\log_{3 / 2} 5} (1 / ε))$ . If $s_{ε}$ is the binary encoding length of $ε$ and $N = ⌈ \log_{2} (2 / ε) ⌉$ , its bit time, including reading $ε$ and printing the expanded word, is $O ((N + s_{ε})^{c + 10}) .$ Here $s_{ε}$ is the total bit length of this numerator/denominator encoding. The constants depend on $G$ , the fixed base-net certificate, and the fixed algebraic descriptions. This is distinct from the exact-real arithmetic count in Solovay–Kitaev Error and Resource Bound.

Facts & Assumptions

Given: The fixed gate package and base-net certificate, a target Cauchy name of the stated polynomial query time, and rational $0 < ε \leq η_{0} < 64^{- 2}$ encoded as $ε = p / q$ by positive binary integers $p, q$ with a fixed delimiter (the fraction need not be reduced). Its length $s_{ε}$ is the total bit length of this encoding, which can be parsed in $O (s_{ε})$ bit operations.

[F1]

A Cauchy name returns rational matrix entries with error at most $2^{- b}$ on query $1^{b}$ , and the requested rational tolerance is encoded in binary under the effective encoding convention (Effective Unitary Matrix Input).

[F2]

The ideal recursion uses a level-zero base-net word and at each later level one lower-level approximation to the target plus two approximations to balanced commutator factors (Solovay–Kitaev Unitary Compiler for SU(2)).

[F3]

For residual radius $η \leq 1 / 16$ , suitable balanced factors exist with commutator error at most $40 η^{3 / 2}$ (A Quantitative Balanced Commutator in SU(2)). For any $V, W \in S U (2)$ within $\sqrt{η}$ of $I$ , replacing each by an $S U (2)$ word within $η$ adds at most $5 η^{3 / 2}$ to the commutator error (Error Cancellation in an SU(2) Commutator). Step 4.1 establishes the required bounds for the particular factors constructed here.

[F4]

For fixed dimension, dyadic interval routines compute sums, products, quotients, normalizations, square roots, matrix logarithms and exponentials with cost $O ((p + B + 1)^{\max (c, 3)})$ under the stated denominator bounds (Fixed-Dimension Dyadic Matrix Routines Have Polynomial Bit Cost).

[F5]

The logarithm of a near-identity $S U (2)$ matrix is traceless and skew-Hermitian, and its operator norm is its Pauli-vector length (A Quantitative Logarithm Near the Identity in SU(2), Pauli Vector Multiplication and Commutator Formula).

[F6]

Inverse-Closed Dense SU(2) Gate Set: each gate label denotes an exact matrix in $S U (2)$ , and the fixed base-net certificate places a listed word within $η_{0} / 4$ of every target in $S U (2)$ .

[F7]

$\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ : for real $t$ , $e^{i t} = \cos t + i \sin t$ and $\cos^{2} t + \sin^{2} t = 1$ .

[F8]

Sine is differentiable with derivative cosine and $\sin 0 = 0$ (The derivatives of sine and cosine are cosine and minus sine), hence it is continuous; the mean value theorem applies on a closed interval to a function continuous there and differentiable inside (The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[F9]

The operator norm is the maximum over unit vectors (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

[F10]

For $b > 0$ , $b \neq 1$ , $\log_{b} x : = \log x / \log b$ ; for $x > 0$ and real $t$ , $x^{t} : = \exp (t \log x)$ , so $(x y)^{t} = x^{t} y^{t}$ and $(x^{s})^{t} = x^{s t}$ by the logarithm product law and inverse relation; and $⌈ y ⌉ : = - ⌊ - y ⌋$ , with floor supplied by Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ . The natural logarithm is strictly increasing and obeys $\log 1 = 0$ (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

Proof

1.1F1F2F10givenalgebra

Set $q_{0} = 4096 η_{0} < 1$ . The exact error recurrence is $η_{j + 1} = 64 η_{j}^{3 / 2}$ , so for $q_{j} = 4096 η_{j}$ we have $q_{j + 1} = q_{j}^{3 / 2}$ and $η_{j} = 2^{- 12} q_{0}^{(3 / 2)^{j}}$ . Choose fixed integers $K, A$ with $q_{0}^{(3 / 2)^{K}} < 1 / 2$ and $2^{A} q_{0} \geq 1$ . Let $j_{N}$ be the least integer with $(3 / 2)^{j_{N}} \geq N$ and set $J = K + j_{N}$ . Then $q_{J} \leq 2^{- N} \leq ε / 2$ , hence $η_{J} \leq ε$ . Write the encoded rational tolerance as $ε = p / q$ with positive integers $p, q$ . Since $q < 2^{s_{ε}}$ and $p \geq 1$ , we have $N \leq s_{ε} + 1$ ; binary search over integers $0, \dots, s_{ε} + 1$ using exact comparisons $2^{N} p \geq 2 q$ computes $N$ in time polynomial in $s_{ε}$ . The integer $j_{N}$ is found by repeated rational multiplication by $3 / 2$ ; $J = O (\log N)$ . Put $B = 12 + A ⌈ (3 / 2)^{J} ⌉$ , $L_{J} = L_{0} 5^{J}$ , and $P = 64 (B + ⌈ \log_{2} (L_{J} + 1) ⌉ + 32)$ . For every $j \leq J$ , $η_{j} \geq 2^{- B}$ ; also $B = O (N)$ , $\log_{2} (L_{J} + 1) = O (\log N)$ , and $P = O (N)$ . Each routine is requested at precision $P$ or higher, so word-product errors and interval widths are below $2^{- B - 20}$ ; in particular, an interval for $τ_{j} : = η_{j} / 128$ has width at most $τ_{j} / 4$ . Compute these recurrence intervals from the rational $η_{0}$ using certified square-root and multiplication calls at precision $P$ ; since $2^{- P} \leq 2^{- B - 9}$ , each resulting interval is narrower than $η_{j} / 512$ .

1.2F1F4F6givenconstruct

At level zero, compute certified Frobenius-distance intervals from the target to each word in the fixed base net, and return the first word whose upper endpoint is at most $η_{0}$ . By the base-net certificate in [F6], some word is at operator-norm distance at most $η_{0} / 4$ ; its Frobenius distance is at most $\sqrt{2} η_{0} / 4$ . Since the fixed dimension is two, the chosen precision $P$ makes the Frobenius-distance interval error less than $η_{0} / 8$ , so this word's upper endpoint is below $η_{0}$ . For the selected word, operator norm is bounded by Frobenius norm, giving actual error at most $η_{0}$ .

2.1F4F5F7F8F9step 1.1construct

At a nonbase node of level $j$ , recursively obtain the exact gate word $A$ for the lower-level call and set $D = U A^{*}$ . Inductively, by [F9], for any unitary $Q$ one has $∥ X Q ∥ = \max_{∥ v ∥ = 1} ∥ X Q v ∥ = \max_{∥ w ∥ = 1} ∥ X w ∥ = ∥ X ∥$ because $Q$ maps the unit sphere bijectively to itself; thus $∥ D - I ∥ = ∥ (U - A) A^{*} ∥ = ∥ U - A ∥ \leq η_{j - 1} < 1 / 2$ . Use interval routines to enclose $X = \log D$ and $r = ∥ X ∥$ by rational intervals $[r_{-}, r_{+}]$ of width at most $τ_{j} / 4$ , and compute a rational interval $[τ_{j}^{-}, τ_{j}^{+}]$ for $τ_{j} = η_{j} / 128$ of width at most $τ_{j} / 4$ . These intervals are certified; branch by comparing rational endpoints: if $r_{+} \leq 2 τ_{j}^{-}$ , return $A$ with no correction. Then $r \leq r_{+} \leq 2 τ_{j}^{-} \leq 2 τ_{j}$ . Since the eigenvalues of the traceless skew-Hermitian $X$ are $i r, - i r$ and $D = e^{X}$ , $∥ D - I ∥ = 2 ∣ \sin (r / 2) ∣ \leq r \leq 2 τ_{j} < η_{j}$ ; here $∣ \sin t ∣ \leq ∣ t ∣$ follows from [F8], the mean value theorem, and [F7]. Otherwise, $r_{+} > 2 τ_{j}^{-}$ . The interval widths imply $τ_{j}^{-} \geq 3 τ_{j} / 4$ and $r_{-} \geq r_{+} - τ_{j} / 4$ , hence $r \geq r_{-} > 2 τ_{j}^{-} - τ_{j} / 4 \geq 5 τ_{j} / 4 > τ_{j}$ . Thus the balanced branch has the certified denominator lower bound it needs. The branch comparison uses only rational interval endpoints, not an exact-real comparison with $τ_{j}$ or an exact-zero test.

3.1F4F5F7step 2.1algebra

In the balanced branch write $X = i v \cdot σ$ , so $∣ v ∣ = r$ by [F5], and set $u = v / r$ . At least one coordinate satisfies $∣ u_{k} ∣ \leq 1 / \sqrt{3}$ . Compute intervals for $∣ u_{1} ∣, ∣ u_{2} ∣, ∣ u_{3} ∣$ of width at most $1 / 16$ , and choose the first whose certified upper endpoint is at most $3 / 4$ ; one exists since $1 / \sqrt{3} + 1 / 16 < 3 / 4$ . For its coordinate vector $e_{k}$ , set $e = (u \times e_{k}) / ∣ u \times e_{k} ∣$ , $a = \sqrt{r / 2} e$ , and $b = - \sqrt{r / 2} (u \times e)$ . The denominator is at least $\sqrt{7} / 4 > 1 / 2$ , so interval normalization is conditioned; also $e ⊥ u$ , $∣ u \times e ∣ = 1$ , and $a \times b = - (r / 2) u = - v / 2$ . Thus, for $A_{0} = i a \cdot σ$ and $B_{0} = i b \cdot σ$ , the Pauli commutator identity gives $[A_{0}, B_{0}] = X$ . The near-identity bound gives $r \leq 2 η_{j - 1}$ , hence $∥ a ∥ = ∥ b ∥ = \sqrt{r / 2} \leq \sqrt{η_{j - 1}}$ . Exponentiating defines exact $V = e^{A_{0}}, W = e^{B_{0}}$ ; interval routines provide Cauchy names for these exact child targets. The lower bound $r > τ_{j} \geq 2^{- B - 7}$ from step 2.1 and the cross-product bound show every denominator has at most $B + O (1)$ conditioning bits. For example, with $Q_{a} = (a \cdot σ) / ∣ a ∣$ , [F5] gives $Q_{a}^{*} = Q_{a}$ , $Q_{a}^{2} = I$ , and $tr (Q_{a}) = 0$ . Grouping the even and odd terms of the exponential series gives $V = \cos ∣ a ∣ I + i \sin ∣ a ∣ Q_{a}$ by [F7]. This formula implies $V^{*} V = I$ ; writing $Q_{a} = (\begin{array}{cc} x & z \\ \overline{z} & - x \end{array})$ , the identity $Q_{a}^{2} = I$ gives $x^{2} + ∣ z ∣^{2} = 1$ , and direct determinant calculation then gives $\det V = \cos^{2} ∣ a ∣ + \sin^{2} ∣ a ∣ = 1$ . The same calculation gives $W \in S U (2)$ .

4.1F3F5F7F8F9step 2.1step 3.1algebra

Put $s = ∥ A_{0} ∥ = ∥ B_{0} ∥ = \sqrt{r / 2} \leq \sqrt{η_{j - 1}} < 1 / 64$ . The Hermitian involution $Q_{a}$ in step 3.1 has eigenvalues $1, - 1$ , so its displayed exponential formula gives $∥ V - I ∥ = ∣ e^{i s} - 1 ∣ = 2 ∣ \sin (s / 2) ∣ \leq s$ , and likewise $∥ W - I ∥ \leq s$ . Here the scalar exponential product identity follows by multiplying its absolutely convergent series; together with [F7] it gives the sine expression, and [F8] gives the last inequality as in step 2.1. From [F9], applying the vector triangle inequality to unit inputs gives the operator-norm triangle inequality, and $∥ Y Z v ∥ \leq ∥ Y ∥ ∥ Z v ∥ \leq ∥ Y ∥ ∥ Z ∥$ gives submultiplicativity. Expand $e^{A_{0}} e^{B_{0}} e^{- A_{0}} e^{- B_{0}}$ in homogeneous degrees: degrees zero, one and two sum to $I + [A_{0}, B_{0}] = I + X$ , and the sum of norms in degree $n$ is at most $(4 s)^{n} / n!$ by the multinomial identity. Its remaining tail is therefore at most $(4 s)^{3} e^{4 s} / 6 < 32 s^{3}$ , since $4 s < 1$ and $e = \sum_{n \geq 0} 1 / n! < 3$ . Also $∥ X ∥ = ∥ [A_{0}, B_{0}] ∥ \leq 2 s^{2}$ , so $∥ e^{X} - I - X ∥ \leq 2 s^{4} e^{2 s^{2}} \leq s^{3}$ ; indeed $e^{2 s^{2}} \leq (1 - 2 s^{2})^{- 1}$ and $2 s / (1 - 2 s^{2}) < 1$ . Since $D = e^{X}$ and $V^{*} = e^{- A_{0}}, W^{*} = e^{- B_{0}}$ , these estimates give $∥ D - V W V^{*} W^{*} ∥ \leq 33 s^{3} \leq 40 η_{j - 1}^{3 / 2}$ for these exact factors, independently of the existential clause of [F3].

5.1F2F3F9step 1.2step 2.1step 4.1

Recursively compile these exact $V, W$ at level $j - 1$ , obtaining words $\tilde{V}, \tilde{W}$ within $η_{j - 1}$ of them. Step 4.1 approximates $D$ by $V W V^{*} W^{*}$ within $40 η_{j - 1}^{3 / 2}$ and verifies both factor distances required by the cancellation bound in [F3], which adds at most $5 η_{j - 1}^{3 / 2}$ when $V, W$ are replaced by $\tilde{V}, \tilde{W}$ . Since $U - (\tilde{V} \tilde{W} {\tilde{V}}^{*} {\tilde{W}}^{*} A) = (D - \tilde{V} \tilde{W} {\tilde{V}}^{*} {\tilde{W}}^{*}) A$ and $A$ is unitary, [F9] right-multiplication invariance gives the same error norm. Thus the returned word $\tilde{V} \tilde{W} {\tilde{V}}^{*} {\tilde{W}}^{*} A$ approximates $U$ within $45 η_{j - 1}^{3 / 2} \leq η_{j}$ . Together with the small-residual branch and step 1.2, induction proves the claimed error. The recursion has at most three calls per node and each output length satisfies $L_{j} \leq 5 L_{j - 1}$ , so its expanded length is at most $L_{0} 5^{J}$ .

6.1F1F2F4step 1.1step 5.1algebra∎

Every exact target in a recursive call is represented by a Cauchy name obtained from its parent using matrix products, logarithms, Pauli coordinates, division by $r \geq τ_{j}$ , normalization, square roots and exponentials. In the balanced branch the only small square-root radicand is $x = r / 2 > τ_{j} / 2$ . Request an enclosing interval of width at most $2^{- b} \sqrt{τ_{j}} / 16$ and at most $τ_{j} / 4$ ; its endpoints are then at least $τ_{j} / 4$ . The identity $∣ \sqrt{x} - \sqrt{y} ∣ = ∣ x - y ∣ / (\sqrt{x} + \sqrt{y})$ bounds the spread of their square roots by $2^{- b} / 16$ . Both width requirements follow from $b + O (1 + \log_{2} (1 / τ_{j}))$ input bits, using the levelwise dyadic lower bound $τ_{j} \geq 2^{- 19 - A ⌈ (3 / 2)^{j} ⌉}$ from step 1.1; no exact square-root comparison is needed to select the precision. Bisect the rational endpoints to $b + O (1)$ output bits as in [F4], costing cubic bit time in the working precision. Use this conditioned routine for $\sqrt{r / 2}$ . For norms used in normalization, the Lipschitz estimate $∣ ∥ v ∥ - ∥ v^{'} ∥ ∣ \leq ∥ v - v^{'} ∥$ in [F4] likewise permits additive input precision; computing the norm of the rational midpoint by square-root bisection needs no further parent query. Each such query uses one parent matrix query at the required guard precision; the query returns all entries together, which the routines reuse. The interval routines have conditioning-bit bound $O (1 + \log_{2} (1 / η_{j}))$ . The sum of these bounds along a branch is $O (B)$ , because $\log_{2} (1 / η_{j}) \leq 12 + A (3 / 2)^{j}$ is geometric. Put $r_{0} = \max (c, 3)$ . Induction through the at most $J$ derived-name layers therefore bounds a query at precision $b$ by $O (J (b + B + \log L_{J} + 1)^{r_{0}})$ . At requested precision $P = O (N)$ , this is polynomial in $N$ for every node. The finitely many algebraic gate entries are enclosed once by the minimal-polynomial bisection in [F4], in $O (P^{3})$ time. The recursion tree has at most $3^{J}$ nodes. After this precomputation, direct evaluation of all word matrices costs at most $O (3^{J} J L_{J} P^{2})$ bit operations; the remaining fixed-dimensional interval routines and derived target-name evaluations cost at most $O (3^{J} J (P + B + \log L_{J} + 1)^{r_{0}})$ . Since $J = O (\log N)$ , $5^{J} = O (N^{\log_{3 / 2} 5})$ and $3^{J} = O (N^{\log_{3 / 2} 3})$ , each of these costs, together with reading $ε$ and printing the expanded output, is bounded by $O ((N + s_{ε})^{c + 10})$ .

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Fixed-Arity Unitary Error Budget

Statement

Fix $k \geq 1$ , $U \in U (2^{k})$ , and a real $0 < ε < 1 / 2$ . Suppose a supplied exact decomposition of $U$ has $m \geq 1$ one-qubit $U (2)$ factors and $c \geq 0$ exact CNOT factors, with no ancillas. Compiling the special-unitary part of each one-qubit factor to error $ε / m$ gives a circuit $C$ such that $\min_{∣ λ ∣ = 1} ∥ U - λ C ∥ \leq ε .$ Its gate count is at most $c + O (m \log^{\log_{3 / 2} 5} (m / ε))$ for fixed $k$ and fixed base net. For every unit vector $ψ$ and every nonnegative contraction $E$ on the $2^{k}$ -dimensional space, the event value $p_{E} (V, ψ) : = ∥ E^{1 / 2} V ψ ∥^{2}$ changes by at most $2 ε$ between $V = U$ and $V = C$ . The phase guarantee is for the whole unconditional block. Here nonnegative contraction means $E = E^{*}$ , $⟨ E v, v ⟩ \geq 0$ for all $v$ , and $∥ E ∥ \leq 1$ .

Facts & Assumptions

Given: A fixed $k \geq 1$ , one exact no-ancilla factorization of $U \in U (2^{k})$ with $m \geq 1$ one-qubit $U (2)$ factors and $c \geq 0$ CNOT factors, and $0 < ε < 1 / 2$ .

[F1]

The SU(2) compiler gives an operator-norm approximation with word length $O (\log^{\log_{3 / 2} 5} (1 / δ))$ (Solovay–Kitaev Error and Resource Bound).

[F2]

The operator norm is submultiplicative (The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2).

[F3]

Nonnegative means self-adjoint with nonnegative quadratic form (Non-negative and positive operators).

[F4]

A normal finite-dimensional complex operator has an orthonormal eigenbasis (Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely).

[F5]

Every nonnegative real has a unique nonnegative square root (Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ ).

[F6]

The closed unit ball in finite-dimensional $C$ is compact (The closed unit ball is compact if and only if the normed space is finite-dimensional).

[F7]

Every unit-modulus complex number has the form $e^{i t}$ for a real $t$ ( $t \mapsto (\cos t, \sin t)$ is a bijection from $[0, 2 π)$ onto the real unit circle).

[F8]

The operator norm is the maximum over unit vectors (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

[F9]

The vector norm induced by an inner product satisfies the triangle inequality (The inner-product norm is definite, homogeneous, and satisfies the triangle inequality).

[F10]

The ordered tensor register has an orthonormal product basis, with the product inner product; wire permutations permute that basis (Ordered tensor registers, their inner product, and wire permutations).

Proof

1.1F7givenconstruct

For each one-qubit factor $G_{j} \in U (2)$ , determinant multiplicativity and $G_{j}^{*} G_{j} = I$ give $∣ \det G_{j} ∣^{2} = 1$ . Thus [F7] gives $\det G_{j} = e^{i θ_{j}}$ for a real $θ_{j}$ . Put $ϕ_{j} = θ_{j} / 2$ and $S_{j} = e^{- i ϕ_{j}} G_{j}$ . Then $\det S_{j} = e^{- 2 i ϕ_{j}} \det G_{j} = 1$ and $S_{j}$ is unitary, so $S_{j} \in S U (2)$ and $G_{j} = e^{i ϕ_{j}} S_{j}$ .

2.1F1step 1.1

Put $h = \min (η_{0}, ε / m) > 0$ . Let $r$ be the least nonnegative integer with $2^{- r} \leq h$ and put $δ = 2^{- r}$ . Such an $r$ exists since $2^{- r} \to 0$ ; since $h < 1$ , minimality gives $h / 2 < δ \leq h$ . Thus $δ$ is rational, satisfies $0 < δ \leq η_{0}$ and $δ \leq ε / m$ , and is a permitted input to the compiler in [F1]. Apply it to each $S_{j}$ . It gives a gate word $W_{j}$ with $∥ S_{j} - W_{j} ∥ \leq δ$ . The phase factors $e^{i ϕ_{j}}$ commute with all factors and multiply to one scalar for the entire circuit; after factoring it out, the exact and compiled products have the same CNOT slots and respectively $S_{j}$ and $W_{j}$ in each one-qubit slot.

3.1F2F8F9F10step 2.1algebra

First justify the full-register error at each local slot. Group its one-qubit support first and unused wires second, using the unitary wire permutation of [F10]. For a finite orthonormal basis $(e_{ℓ})$ of the unused register, every vector is uniquely $v = \sum_{ℓ} v_{ℓ} \otimes e_{ℓ}$ , and the product inner product gives $∥ v ∥^{2} = \sum_{ℓ} ∥ v_{ℓ} ∥^{2}$ . For a local difference $A$ , it also gives $∥ (A \otimes I) v ∥^{2} = \sum_{ℓ} ∥ A v_{ℓ} ∥^{2} \leq ∥ A ∥^{2} \sum_{ℓ} ∥ v_{ℓ} ∥^{2} = ∥ A ∥^{2} ∥ v ∥^{2}$ by [F8]. Thus $∥ A \otimes I ∥ \leq ∥ A ∥$ . Conjugation by the wire permutation preserves norm, since a unitary preserves vector norms and maps the unit sphere onto itself. This includes the empty unused register. Apply this to each $S_{j} - W_{j}$ from step 2.1, giving full-register slot error at most $δ$ . Index the full ordered circuit product by $q = m + c$ slots, so the two products are $A_{q} \dots A_{1}$ and $B_{q} \dots B_{1}$ . At a CNOT slot set $A_{r} = B_{r}$ to that exact gate; at a one-qubit slot use the exact $S_{j}$ and its compiled word $W_{j}$ . Insert one factor at a time to obtain $A_{q} \dots A_{1} - B_{q} \dots B_{1} = \sum_{r = 1}^{q} A_{q} \dots A_{r + 1} (A_{r} - B_{r}) B_{r - 1} \dots B_{1}$ . Every surrounding factor is unitary: exact factors, compiled words, and CNOTs are all unitary. For a unitary $Q$ , $∥ Q v ∥ = ∥ v ∥$ for every unit vector $v$ , so [F8] gives $∥ Q ∥ = 1$ . The operator-norm triangle inequality follows from [F8] by applying [F9] to each unit input and taking the maximum. Then [F2] bounds the product difference by the sum of the $q$ factor errors. The CNOT slots contribute zero, and the $m$ one-qubit slots each contribute at most $δ$ , giving $m δ \leq ε$ . The scalar from step 2.1 is a single whole-circuit phase, proving the projective operator bound.

4.1F2F3F4F5F6F8F9givenstep 3.1algebra

The unit circle is a closed subset of the closed unit ball in $C$ , so it is compact by [F6]. The continuous function $λ \mapsto ∥ U - λ C ∥$ therefore attains its minimum at some $∣ λ ∣ = 1$ . The phase from step 3.1 gives one value at most $ε$ , so this minimum is also at most $ε$ . By [F4], diagonalize $E$ in an orthonormal basis with eigenvalues $λ_{1}, \dots, λ_{2^{k}}$ . Nonnegativity [F3] makes each $λ_{i} \geq 0$ , and $∥ E ∥ \leq 1$ gives $λ_{i} \leq 1$ by applying the norm to a corresponding unit eigenvector. Define $E^{1 / 2}$ in this basis by diagonal entries $\sqrt{λ_{i}}$ , which exist by [F5]. Its square is $E$ , it is self-adjoint, and direct calculation on coordinates gives $∥ E^{1 / 2} ∥ = \max_{i} \sqrt{λ_{i}} \leq 1$ . The factors $U, C$ are unitary, so [F8] gives $∥ U ψ ∥ = ∥ C ψ ∥ = 1$ . The two vectors $E^{1 / 2} U ψ$ and $E^{1 / 2} λ C ψ$ have norms at most $1$ , and their distance is at most $ε$ by step 3.1 and [F2]. The reverse triangle inequality from [F9] gives $∣ ∥ x ∥ - ∥ y ∥ ∣ \leq ∥ x - y ∥$ for these vectors; factoring the difference of their squared norms therefore bounds it by $(1 + 1) ε = 2 ε$ . Since the scalar phase does not change a norm, this proves the event bound.

5.1F1step 2.1∎

Each one-qubit word uses $O (\log^{\log_{3 / 2} 5} (1 / δ))$ gates by [F1]. Since $1 / δ < 2 \max (1 / η_{0}, m / ε)$ and $m / ε > 2$ , this is $O (\log^{\log_{3 / 2} 5} (m / ε))$ , with constants depending on the fixed base-net radius. Summing over $m$ factors and adding the $c$ exact CNOTs gives the stated count. The factorization and all replacements use the same wires, so no ancillas are introduced.

Remarks

This item proves the error budget for any supplied exact factorization. To apply it uniformly to every fixed-arity unitary, the QC11 exact-synthesis supplier must provide such a factorization. Its separate improved numeric CNOT bound is not used in this conditional result.

TheoremStatement: AI-adaptedProof: AI-adaptedOpen item page →

Controlled-Phase Approximation and Global-Phase Boundary

Statement

For $θ \in R$ , let $P_{α} = diag (1, e^{i α})$ and $R_{z} (α) = diag (e^{- i α / 2}, e^{i α / 2})$ . Define $C P_{θ} = diag (1, 1, 1, e^{i θ})$ in the control-first basis $∣ 00 ⟩, ∣ 01 ⟩, ∣ 10 ⟩, ∣ 11 ⟩$ . Define CNOT by $∣ a, b ⟩ \mapsto ∣ a, b \oplus a ⟩$ , where $a, b \in {0, 1}$ and $\oplus$ is addition modulo two. The continuous phase-gate model permits each $P_{α}$ exactly for real $α$ . On an additional control qubit define $C (M) = diag (I_{4}, M)$ in control-first order. The two-qubit circuit that applies CNOT, then $P_{- θ / 2}$ to the target, then CNOT, then $P_{θ / 2}$ to each wire implements $C P_{θ}$ . Replacing the three $P$ gates by their $R_{z}$ representatives gives $e^{- i θ / 4} C P_{θ}$ ; here $P_{α} = e^{i α / 2} R_{z} (α)$ .

For the three-qubit factorization, use the lexicographically ordered basis $∣ a, b, c ⟩$ with $a, b, c \in {0, 1}$ . A gate $P_{α}^{(j)}$ multiplies this basis vector by $e^{i α x_{j}}$ , where $(x_{1}, x_{2}, x_{3}) = (a, b, c)$ ; ${CNOT}_{i \to j}$ toggles bit $x_{j}$ by $x_{i}$ and fixes the other bits. These explicit basis actions fix the wire order used below.

For $0 < ε < 1 / 2$ , the fixed-arity compiler gives a projective operator approximation within $ε$ when applied to the complete $C P_{θ}$ block. If this block is controlled by an additional qubit, one valid approach is to apply the compiler to the complete three-qubit controlled- $C P_{θ}$ matrix. A phase-minimized approximation to $C P_{θ}$ cannot in general be controlled without restoring its relative phase: if $∥ C P_{θ} - μ W ∥ \leq ε$ and $∣ μ ∣ = 1$ , then $∥ C (C P_{θ}) - (diag (1, μ) \otimes I_{4}) C (W) ∥ \leq ε .$ Thus phase restoration is another valid approach when $C (W)$ and the control phase are available. This identity alone assigns no finite-gate cost or controlled black-box access to those operations. In particular, controlling the $R_{z}$ circuit from the first paragraph gives $C (e^{- i θ / 4} C P_{θ}) = (diag (1, e^{- i θ / 4}) \otimes I_{4}) C (C P_{θ})$ ; applying $P_{θ / 4}$ to the added control restores the exact controlled target in the continuous phase-gate model.

Facts & Assumptions

Given: $θ \in R$ , the ordered basis $∣ 00 ⟩, ∣ 01 ⟩, ∣ 10 ⟩, ∣ 11 ⟩$ , and the continuous phase-gate model, and $0 < ε < 1 / 2$ for the approximation claims.

[F1]

Controlled Phase Rotation defines the exact phase gate $P_{θ} = diag (1, e^{i θ})$ and its control-first block $C P_{θ} = diag (1, 1, 1, e^{i θ})$ .

[F2]

Global Phase Under Control: for a unit scalar $λ$ , $C (λ U) = (P_{λ} \otimes I) C (U)$ ; the scalar becomes a relative phase on the active control block.

[F3]

Fixed-Arity Unitary Error Budget gives projective operator error at most $ε$ for a complete fixed-arity block when an exact factorization into one-qubit gates and CNOTs is supplied.

Proof

1.1givenF1algebra

On a basis vector $∣ a b ⟩$ , the first CNOT maps it to $∣ a, b \oplus a ⟩$ . The target phase contributes $e^{- i θ (b \oplus a) / 2}$ ; the second CNOT restores $∣ a b ⟩$ ; and the two final phase gates contribute $e^{i θ (a + b) / 2}$ . The product is $e^{i θ a b}$ , which is $1$ on $∣ 00 ⟩, ∣ 01 ⟩, ∣ 10 ⟩$ and $e^{i θ}$ on $∣ 11 ⟩$ . This is exactly $C P_{θ}$ from [F1].

2.1givenF1step 1.1algebra

Direct diagonal multiplication gives $P_{α} = e^{i α / 2} R_{z} (α)$ , hence $R_{z} (α) = e^{- i α / 2} P_{α}$ . Replacing $P_{- θ / 2}$ on the target contributes $e^{i θ / 4}$ , while replacing each of the two $P_{θ / 2}$ gates contributes $e^{- i θ / 4}$ . Their product is $e^{- i θ / 4}$ , so the resulting $R_{z}$ circuit is $e^{- i θ / 4} C P_{θ}$ .

2.2F2F3step 1.1algebra

The circuit in step 1.1 is an exact factorization of the two-qubit $C P_{θ}$ into three one-qubit phase gates and two CNOTs. Applying [F3] therefore gives a word $W$ and unit scalar $μ$ with $∥ C P_{θ} - μ W ∥ \leq ε$ . By [F2], $C (μ W) = (diag (1, μ) \otimes I_{4}) C (W)$ . The difference $C (C P_{θ}) - C (μ W) = diag (0, C P_{θ} - μ W)$ has norm exactly $∥ C P_{θ} - μ W ∥$ : on a vector $(x, y)$ it acts as $(0, (C P_{θ} - μ W) y)$ , giving the upper bound, and vectors $(0, y)$ give equality. Consequently the displayed phase-corrected controlled approximation has error at most $ε$ . If $μ \neq 1$ , the correction $diag (1, μ)$ is not a scalar on the control. Omitting it is not justified by the two-qubit projective bound; using it requires both the control phase and $C (W)$ to be available.

3.1F2step 2.1algebra

With $λ_{R} = e^{- i θ / 4}$ from step 2.1, [F2] gives $C (λ_{R} C P_{θ}) = (diag (1, λ_{R}) \otimes I_{4}) C (C P_{θ})$ . Applying $P_{θ / 4} = diag (1, \overline{λ_{R}})$ to the outer control restores the exact controlled target in the continuous phase-gate model.

4.1F3givenalgebraconstruct∎

The complete controlled target is the diagonal three-qubit matrix $D_{θ} = diag (1, 1, 1, 1, 1, 1, 1, e^{i θ})$ . For bits $a, b, c \in {0, 1}$ , put $p_{a b} = a \oplus b$ , $p_{a c} = a \oplus c$ , $p_{b c} = b \oplus c$ , and $p_{a b c} = a \oplus b \oplus c$ . Checking the four possible Hamming weights $0, 1, 2, 3$ makes the right side respectively $0, 0, 0, 4$ , so $4 a b c = a + b + c - p_{a b} - p_{a c} - p_{b c} + p_{a b c}$ . Apply $P_{θ / 4}$ to each single bit. To apply $P_{- θ / 4}$ to $p_{a b}$ , use a CNOT with control $b$ and target $a$ , apply $P_{- θ / 4}$ to wire $a$ , and undo that CNOT; the target wire then again contains $a$ . Use the corresponding pairs for $p_{a c}$ and $p_{b c}$ . To apply $P_{θ / 4}$ to $p_{a b c}$ , use two CNOTs into wire $a$ , apply $P_{θ / 4}$ there, and undo both CNOTs. On each basis state these circuits restore the original bits and contribute exactly the indicated signed parity phase. The resulting phase is $e^{i θ a b c}$ , so this is an exact factorization of $D_{θ}$ with seven one-qubit phase gates and ten CNOTs. Applying [F3] to this complete three-qubit factorization gives a projective operator approximation to $D_{θ}$ itself; its scalar is global on the three-qubit block. This supplies the complete-block compilation option in the statement.

5 · Examples, counterexamples and false statements

None yet.

Approximate Universality and Solovay–Kitaev

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Effective Unitary Matrix Input

Definition

Inverse-Closed Dense SU(2) Gate Set

Definition

Fixed-Dimension Dyadic Matrix Routines Have Polynomial Bit Cost

Statement

Facts & Assumptions

Proof

Powers of an Irrational Rotation Are Dense on the Circle

Statement

Facts & Assumptions

Proof

A Quantitative Logarithm Near the Identity in SU(2)

Statement

Facts & Assumptions

Proof

Compactness Gives a Finite SU(2) Base Net

Statement

Facts & Assumptions

Proof

Pauli Vector Multiplication and Commutator Formula

Statement

Facts & Assumptions

Proof

A Quantitative Balanced Commutator in SU(2)

Statement

Facts & Assumptions

Proof

Two Nonparallel One-Parameter Subgroups Generate SU(2) After Closure

Statement

Facts & Assumptions

Proof

Clifford+T Is Dense Projectively on One Qubit

Statement

Facts & Assumptions

Proof

Error Cancellation in an SU(2) Commutator

Statement

Facts & Assumptions

Proof

Solovay–Kitaev Unitary Compiler for SU(2)

Definition

Well-definedness

Solovay–Kitaev Error and Resource Bound

Statement

Facts & Assumptions

Proof

Finite-Precision Bit Complexity of the SU(2) Solovay–Kitaev Compiler

Statement

Facts & Assumptions

Proof

Fixed-Arity Unitary Error Budget

Statement

Facts & Assumptions

Proof

Remarks

Controlled-Phase Approximation and Global-Phase Boundary

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources