Source-linked AI summary
Efficient Clifford+T approximation of single-qubit operators
Peter Selinger
TL;DR
Approximating arbitrary single-qubit operators with a discrete Clifford+T set requires efficient algorithms with near-optimal gate scaling. The paper gives a randomized, ancilla-free algorithm whose expected runtime is polynomial in log(1/ε), achieving linear-logarithmic T-counts and near-optimal z-rotation counts, while relying on a prime-distribution hypothesis and remaining specialized to Clifford+T.
Problem
The paper addresses efficient approximation of arbitrary single-qubit operators using Clifford+T without ancillas, extending beyond prior approaches that used ancillas or had worse asymptotic scaling.
Method
The paper presents an efficient randomized algorithm that approximates arbitrary SU(2) elements with products of Clifford+T operators.
Results
For z-rotations the T-count is K + 4 log2(1/ε), for arbitrary SU(2) it is K + 12 log2(1/ε), and the exponent improves from Solovay–Kitaev’s c approximately 3.97 to c = 1.
Takeaways & Limitations
The algorithm provides asymptotically optimal logarithmic gate-complexity scaling and is within an additive constant of optimal for certain z-rotations.
Takeaways & Limitations
Expected polynomial runtime depends on an unproven prime-distribution hypothesis, and the algorithm is specialized to Clifford+T; the z-rotation lower bound assumes single-qubit Clifford+T synthesis without auxiliary techniques.
Abstract
from arXiv · showhide
We give an efficient randomized algorithm for approximating an arbitrary element of $SU(2)$ by a product of Clifford+$T$ operators, up to any given error threshold $ε>0$. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in $\log(1/ε)$. If the operator to be approximated is a $z$-rotation, the resulting gate sequence has $T$-count $K+4\log_2(1/ε)$, where $K$ is approximately equal to $10$. We also prove a worst-case lower bound of $K+4\log_2(1/ε)$, where $K=-9$, so that our algorithm is within an additive constant of optimal for certain $z$-rotations. For an arbitrary member of $SU(2)$, we achieve approximations with $T$-count $K+12\log_2(1/ε)$. By contrast, the Solovay-Kitaev algorithm achieves $T$-count $O(\log^c(1/ε))$, where $c$ is approximately $3.97$.
1 Introduction
The paper develops an efficient randomized, ancilla-free Clifford+T approximation algorithm for single-qubit operators, improving on Solovay–Kitaev scaling and approaching optimal T-counts for z-rotations. Its expected polynomial runtime depends on an unproven hypothesis about prime distributions, and its scope is specialized to Clifford+T.
- Problem and setting: The paper targets approximate decomposition of arbitrary single-qubit operators using the fault-tolerant Clifford+T universal gate set.The approximation is required because discrete universal gate sets cannot generally represent arbitrary operators exactly.
- Main results: K + 4 log2(1/ε) T-count is achieved for z-rotations, with K approximately 10, matching a worst-case lower bound up to an additive constant.The lower bound has K = −9 for certain z-rotations.
- Main results: K + 12 log2(1/ε) T-count is achieved for arbitrary members of SU(2).The algorithm applies to any requested error threshold ε > 0.
- Comparison with prior work: The method reduces the gate-complexity exponent from Solovay–Kitaev’s c approximately 3.97 to c = 1.Solovay–Kitaev produces T-count O(log^c(1/ε)).
- Prior work and scope: The paper addresses the open question of whether asymptotically optimal efficient approximation can be achieved without ancillas.Earlier Kliuchnikov–Maslov–Mosca results used a fixed, small number of ancillas initialized and returned to |0⟩.
- Limitations: The number-theoretic algorithm is specialized to Clifford+T rather than arbitrary universal gate sets.The paper notes that the approach is unlikely to work for arbitrary universal gate sets.
- Limitations: The expected polynomial runtime is contingent on an unproven hypothesis about the distribution of primes.The hypothesis is described as heuristically true but not proven to the author’s knowledge.
- Limitations: The z-rotation lower bound applies only to products of single-qubit Clifford+T operators, since ancillas, resource states, or online measurement can yield smaller T-counts.This boundary concerns the specific synthesis model studied in the paper.
2 Overview of the algorithm
The algorithm samples algebraic candidates in a ring that characterizes exactly synthesizable Clifford+T operators, then constructs an ε-close unitary and exactly synthesizes it. The resulting T-count is controlled by the denominator exponent selected for the approximation.
- Algebraic representation: The algorithm works with elements of the ring 2^k(aω^3 + bω^2 + cω + d), where k is natural and a, b, c, d are integers.This ring provides the algebraic representation used to construct candidate approximations.
- Exact synthesis: A unitary is exactly synthesizable over Clifford+T without ancillas if and only if all matrix entries belong to D[ω].The required T-count is at most 2k, where k is the minimal exponent representing all entries in the relevant ring form.
- Approximation construction: For a target z-rotation, the method chooses k and randomized u ∈ Z[ω] so that a suitable algebraic approximation can be found with relatively high probability.The construction also involves solving a Diophantine equation for the required coefficients.
- Approximation construction: The constructed unitary satisfies ||U − R_z(θ)|| ≤ ε and has coefficients in D[ω], enabling exact Clifford+T synthesis.The exact synthesis step gives a T-count of at most 2k.
3 Some number theory
This section introduces the algebraic-number rings and operations used by the approximation algorithm. It establishes Euclidean-domain structure, divisibility and norm properties, and square criteria for units.
- Algebraic rings: The paper works with the rings Z, Z[√2], Z[i], and Z[ω], with Z[ω] containing the others.Z[ω] is the ring of cyclotomic integers of degree 8.
- Conjugation: Conjugation provides automorphisms of Z[ω], including complex conjugation and a second map acting nontrivially on Z[ω] and Z[√2].These maps are used to define the relevant norms and conjugates.
- Norms: The norms N_i and N_ω are nonnegative, multiplicative, and characterize units through values ±1.The cyclotomic norm is expressed using the coefficients of an element of Z[ω].
- Euclidean domains: These rings are Euclidean domains, so greatest common divisors can be computed by Euclid’s algorithm in O(log |N(t)|) divisions.Divisibility is independent of the chosen ring among the rings considered.
- Units: A unit in Z[√2] is a square exactly when it and its conjugate are both nonnegative.The criterion follows from the sign characterization of the unit exponents.
4 A Diophantine equation
The paper reduces a norm equation in Z[ω] to algebraic constructions based on prime splitting and greatest common divisors. Under explicit positivity and parity conditions, it proves existence and efficient randomized computability of a solution.
- Equation: The central task is solving a relative norm equation in Z[ω], and the paper develops the solution method in detail.The equation is connected to splitting fully split primes in Z[ω].
- Existence theorem: Under the stated conditions on ξ and p=ξ•ξ, there exists t∈Z[ω] satisfying the equation, and an efficient randomized algorithm computes it.The conditions include x odd, y even, and nonnegative ξ and ξ•.
- Proof: The proof eliminates the cases s†s∼1 and s†s∼ξ^2, leaving s†s∼ξ as the required case.The excluded cases contradict divisibility or norm properties.
- Final construction: After obtaining s†s∼ξ, the argument shows the remaining unit is a square and constructs t by multiplying s by its square root.The resulting element satisfies t†t=ξ.
- Algorithmic properties: Only the computation of h is randomized; the remaining arithmetic, including gcd, division, square-root, and multiplication steps, is deterministic.The square-root computation reduces to solving a quadratic equation over the integers.
5 Approximations in Z[
This section proves that algebraic integers in Z[√2] can be found inside prescribed regions of the two-dimensional conjugate embedding. The coverage results provide existence and efficient computation, including parity-controlled solutions.
- Uniqueness: If the product of interval widths is below 1, a region contains at most one element of Z[√2].The result bounds the number of algebraic-integer solutions in a conjugate-coordinate rectangle.
- Existence: If the product of interval widths is at least (1+√2)^2, every such rectangle contains an element of Z[√2].The proof defines a coverage property and constructs a solution algorithmically.
- Geometry: The geometric interpretation places conjugate pairs on a nonuniform grid and searches for grid points inside rotated rectangles.The two coordinates correspond to an element and its conjugate.
- Coverage proof: The proof uses symmetry, rescaling by powers of λ=1+√2, and a finite candidate check to establish coverage.The construction transforms interval widths while preserving the existence property.
- Efficiency: The coverage construction is efficient because it uses no iterative search beyond computing a power of λ in O(|log(δ)|) steps.The stated computational effort is at most O(log^2(δ)).
- Sharpness: The bounds are sharp, with examples attaining the uniqueness and existence thresholds.The examples show regions containing exactly two or four solutions at the relevant boundaries.
- Parity control: A rescaled corollary guarantees solutions with either even or odd first coefficient, while retaining efficient computability.This parity control is obtained by transformations of the coverage result.
6 Approximation up to ε
The approximation problem is reduced to finding algebraic candidates inside an ε-region and then solving a norm equation for the remaining matrix entry. Geometric coverage supplies many candidates once k is large enough.
- Approximation setup: For fixed θ and ε, the goal is to choose k, u, and t so that a Clifford+T-form matrix is unitary and ε-close to R_z(θ).Unitarity requires u†u+t†t=2^k.
- ε-region: The ε-region has width proportional to ε^2, so approximation becomes a constrained search in the unit disk.The region is represented geometrically as a subset of the disk.
- ε-region: The operator-norm error condition is equivalent to requiring the normalized u to lie in the ε-region R_ε.The reduction uses the dot product between the normalized u and z=e^{-iθ/2}.
- Two-step reduction: After selecting u, the second step is to find t∈Z[ω] satisfying t†t+u†u=2^k.The remaining norm equation is handled by the Diophantine solver from the preceding section.
- Candidates: A candidate normalized u lies in R_ε and satisfies parity and nonnegativity conditions on the associated ξ and ξ•.A prime candidate additionally requires p=ξ•ξ to be prime.
- Candidate generation: If k≥C+2 log_2(1/ε), with C=5, the construction produces at least floor(4^k ε^2) candidates efficiently.The candidates are obtained by partitioning a parallelogram inside R_ε and applying the Z[√2] coverage results.
- Geometric construction: The parallelogram used for candidate selection is contained within R_ε, ensuring that every selected point meets the approximation constraint.Its boundaries are defined by two dot-product lines and two horizontal lines.
7 The main algorithm
The algorithm constructs Clifford+T approximations to z-rotations and extends them to arbitrary SU(2) operators by decomposing them into three rotations. It includes randomized candidate generation, exact synthesis, and a determinant-based scope limitation for U(2).
- Approximating a z-rotation: The algorithm combines candidate generation with Theorem 12 to search for a ring element satisfying the required norm equation.Candidates are tried until a valid solution is found; random generation is also permitted.
- Approximating a z-rotation: A successful solution yields an ε-approximation of Rz(θ), which is converted into Clifford+T gates using exact synthesis.The sequence may optionally be reduced to Matsumoto-Amano normal form.
- Approximating arbitrary gates: An arbitrary U ∈ SU(2) is decomposed as Rz(β) H Rz(γ) H Rz(δ), with each rotation approximated separately to error ε/3.This reduces arbitrary single-qubit approximation to three z-rotation approximations connected by Clifford gates.
- Scope: The method directly targets SU(2); for U(2), arbitrary determinants are approximable only when the determinant is a power of ω unless arbitrary global phases are included.Otherwise, approximation is possible only up to a global phase.
8 Complexity analysis
The analysis relates denominator exponent to T-count, obtains logarithmic gate complexity, and bounds runtime under a prime-distribution hypothesis. Randomization also permits parallel execution and theoretical seeding safeguards termination.
- Gate complexity: 2k − 3 ≤ n ≤ 2k bounds the minimal T-count n for a Clifford+T operator with denominator exponent k.This relation converts the algorithm’s denominator choice into a circuit-length bound.
- Gate complexity: K + 4 log2(1/ε) bounds the T-count for z-rotations, while arbitrary SU(2) operators require K + 12 log2(1/ε).The constants are approximately 10.09 for z-rotations and 30.26 for arbitrary SU(2).
- Time complexity: Under Hypothesis 29, the expected runtime is O(k^4) = O(log^4(1/ε)).The assumption states that candidate primality is at least as likely as primality among comparable odd numbers.
- Time complexity: The randomized algorithm can be parallelized because candidates are chosen independently.Independent candidate trials provide a direct source of parallelism.
- Seeding: Seeding can theoretically avoid unlucky candidate sets, but for z-rotations it approximately doubles the T-count to K + 8 log2(1/ε).For arbitrary gates, a different seed leaves the asymptotic T-count unchanged up to a small additive constant; in practice, seeding appears unnecessary.
9 Lower bounds
Counting arguments give a general lower bound, while a sharper construction establishes a worst-case bound for z-rotations. The z-rotation result places the algorithm within an additive constant of optimal for selected angles.
- General lower bound: K + 3 log2(1/ε) is a general lower bound derived from counting Clifford+T circuits against the ε-ball covering number of SU(2).The argument uses the three-dimensional structure of SU(2) and the number of circuits available at T-count n.
- General lower bound: Most operators require T-counts close to or above the general lower bound, although the bound does not automatically apply to z-rotations.Z-rotations form a one-dimensional submanifold rather than the full three-dimensional SU(2) space.
- Z-rotation lower bound: K′ + 4 log2(1/ε), with K′ = −9, is a worst-case lower bound for ε-approximating some z-rotation.The proof constructs an angle whose ε-region excludes the relevant boundary points.
- Scope of the lower bound: The sharper z-rotation lower bound applies only to carefully chosen worst-case operators, while achieving the typical lower-bound order remains plausible rather than proved.A proposed algorithmic variation is sketched, but its details are left for future work.
10 Overclocking
Overclocking lowers the algorithm’s parameter k to seek shorter circuits. A fixed additive reduction increases runtime only by a constant factor, whereas multiplicative overclocking remains an unresolved optimization.
- Overclocking: Overclocking decreases the prescribed value of k, and practical estimates suggest that smaller k can still produce valid decompositions.The paper names this practice by analogy with running processors above their designed clock speed.
- Additive overclocking: A fixed additive reduction of C increases runtime by a fixed factor without affecting validity or big-O time complexity.The success probability decreases by a factor independent of ε, while the asymptotic complexity remains unchanged.
- Multiplicative overclocking: Multiplicative overclocking may target K + 3 log2(1/ε) for most angles, but the current algorithm cannot efficiently exploit the resulting thin ε-regions.The paper leaves refinement for sparsely populated regions to future work.
11 Experimental results
Experiments demonstrate practical high-precision decompositions, including ε = 10^-100 with 1338 T-gates, while runtime and candidate processing grow polynomially as ε decreases.
- The experiments include approximating Rz(π/128) for several ε values on one 3.40GHz Intel i5-3570 CPU core.
- Runtime per candidate increases polynomially as ε decreases because the algorithm processes larger integers and real numbers.
- The number of candidates tried per run is approximately proportional to k, consistent with the prediction in equation (34).This provides empirical evidence supporting Hypothesis 29.
- ε = 10^-100 was achieved using only 1338 T-gates, outperforming Solovay-Kitaev at comparable T-count.Solovay-Kitaev with comparable T-count achieves less than ε = 10^-10.
12 Conclusions
The paper presents an efficient Clifford+T decomposition algorithm that performs well theoretically and practically, producing shorter circuits than the comparable ancilla-based approach by a constant factor.
- The algorithm is reported as the most efficient to date for decomposing SU(2) elements into Clifford+T gates at arbitrarily small ε.
- ε = 10^-100 decompositions use fewer than 1400 T-counts in practice.
- The resulting decompositions are shorter by a constant, non-negligible factor than those from the ancilla-based Kliuchnikov–Maslov–Mosca algorithm.Both algorithms have the same optimal asymptotic big-O complexity and are based on solving a Diophantine equation.