Fault-tolerant quantum computation requires compiling arbitrary one-qubit unitaries into short words over a fixed gate library. For arithmetic libraries such as the $p=5$ Lubotzky--Phillips--Sarnak, or Clifford$+V$, gate set, this problem is governed by quaternionic lattice points on $S^3\cong \SU(2)$. We study the complete norm shells \[ P_k=\{x/5^k\in S^3:x\in\ZZ^4,\ |x|^2=5^{2k}\} \] and the associated projective gate set $T\subset PSU(2)$. The main worst-case quantity is Sarnak's covering exponent $K(T)$, for which the classical range is $4/3\le K(T)\le2$. We show that any positive localized cap-kernel certificate using only the Deligne--LPS square-root spectral estimate reaches only the volume-squared threshold $|V_T(t)|\gg μ(B(\varepsilon))^{-2}$, hence only exponent $2$. Thus any unconditional improvement requires arithmetic cancellation in localized off-diagonal counting. We also record the conditional benchmark that twisted Linnik gives $K(T)=4/3$, matching Harman's obstruction. We prove the shell-to-gate implication $ρ(P_k)\le C5^{-αk}\Rightarrow K(T)\le4/(3α)$, so $α>2/3$ is exactly the threshold for improving the unconditional bound. Finally, exact enumeration of $P_1,P_2,P_3,P_4$ and Haar-random tests show median trace-defect error at the optimal $N^{-2/3}$ scale, while high quantiles remain separated. This gives a sharp distinction between strong typical-case performance and rare arithmetic holes controlling worst-case synthesis.
Fault-tolerant quantum computation requires compiling arbitrary one-qubit unitaries into short words over a fixed gate library. For arithmetic libraries such as the p=5 Lubotzky--Phillips--Sarnak, or Clifford+V, gate set, this problem is governed by quaternionic lattice points on S3≅\SU(2). We study the complete norm shells [ P_k={x/5^k\in S^3:x\in\ZZ^4,\ |x|^2=5^{2k}} ] and the associated projective gate set T⊂PSU(2). The main worst-case quantity is Sarnak's covering exponent K(T), for which the classical range is 4/3≤K(T)≤2. We show that any positive localized cap-kernel certificate using only the Deligne--LPS square-root spectral estimate reaches only the volume-squared threshold ∣VT(t)∣≫μ(B(ε))−2, hence only exponent 2. Thus any unconditional improvement requires arithmetic cancellation in localized off-diagonal counting. We also record the conditional benchmark that twisted Linnik gives K(T)=4/3, matching Harman's obstruction. We prove the shell-to-gate implication ρ(Pk)≤C5−αk⇒K(T)≤4/(3α), so α>2/3 is exactly the threshold for improving the unconditional bound. Finally, exact enumeration of P1,P2,P3,P4 and Haar-random tests show median trace-defect error at the optimal N−2/3 scale, while high quantiles remain separated. This gives a sharp distinction between strong typical-case performance and rare arithmetic holes controlling worst-case synthesis.
The Pythagorean Angle Lattice produces exact spinor-norm and continuity no-go theorems for single-qubit gate synthesis, free and dense groups of difference gates, and exponent walls at positive distance from the Clifford group. Let θ be the smaller acute angle of a primitive Pythagorean triangle (a, b, c) and z = e^{iθ} = (b + ia)/c. The rational norm-one phases form the Pythagorean angle lattice P ⊂ ℚ(i). We study the exact arithmetic of the associated single-qubit rotations and of the difference angle Δ = π/2 − 2θ, whose spin rotation is U_n(Δ) = (A I − i B n · σ)/(√2 c) with A = a + b, B = b − a. Within the sector of rational rotation matrices, Gaussian rational eigenphases occur exactly for rational Bloch axes, and the obstruction to an exact rational spin lift is the spinor squareclass, which on these phases is the halving class [N(1 + z)]. Every Pythagorean difference gate has spinor norm [2] and factors exactly as a quarter-turn times the rational spin gate defined by the triple. This gives a spinor-norm obstruction to exact synthesis with forced length parity, an obstruction to synthesising the rotation by θ from difference and Clifford gates unless c is a perfect square, and an exact criterion for rational fourth roots; difference gates about orthogonal axes generate a free group, and about non-parallel axes a dense group with approximating words of logarithmic length. For pairs of gates we prove exact commutator identities, including a relation between the commutator scalar and the Born overlap of PAL-internal axis states; nested commutators obey an exact logistic recurrence for their transverse intensity, with a transition at θ = π/12 and a 2-adic filtration of their spectral discriminants. In odd prime-power dimensions, suitable Weil operators admit exponent intertwiners U ↦ U^{−2} at projective distance at least 1/(2√2) and diamond distance at least √(1 − p^{−k}) from the Clifford group, with Weyl spreading at least 1/360. Finally, density of the dyadic classes gives a continuity obstruction: without an a priori height bound, no fixed finite-copy continuous protocol separates them with a uniform margin. All results concern exact arithmetic structures inside ordinary quantum mechanics; no modification of its postulates is proposed.
We study the Clifford+T synthesis of quantum multiplexers U=⨁i=12nUi: an n-qubit control register selects which single-qubit gate Ui∈SU(2) acts on the target qubit. For each block Ui, consider the minimum even T-count needed to approximate it within diamond distance ε without ancillae, and let m be the largest of these costs. For an arbitrary multiplexer U, we construct an approximation of U within the same distance using at most m+O(2n(m+1))T gates. With one control qubit, the cost is m+O(1) and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed n and independent Haar-random blocks, the minimum T-count among these circuits lies between (3−δ)log2(1/ε) and (3+δ)log2(1/ε) for every fixed δ>0, except with probability O(εcn,δ) as ε→0. The optimal leading coefficient is therefore the same as for a single Haar-random SU(2) gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order ε2. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random SU(4) gates within diamond distance ε, using at most (9+δ)log2(1/ε)T gates for every fixed δ>0, except with probability O(εcδ) with cδ>0.
We determine the non-Clifford T-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an n-qubit operator with a clean ancillas and at most sT gates can be compressed to use at most min{a,n+2s} ancillas, without increasing the absolute error or T-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error ε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log(n4/ε)), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on n spins, we obtain independent lower bounds Ω(n) from stabilizer nullity and Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log(1/ε)). As an application, we evaluate the T-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation T-count scales as the query count times the optimal T-count per query.
Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I provide number-theoretic characterizations for certain restricted Clifford+T circuits by considering unitary matrices over subrings of Z[1/√2, i]. We focus on the subrings Z[1/2], Z[1/√2], Z[1/√−2], and Z[1/2, i], and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X, CX, CCX} with an analogue of the Hadamard gate and an optional phase gate. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.
We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works \cite{Hastings2017} and \cite{Campbell2017}, we show that taking probabilistic mixtures of channels to solve fallback \cite{BRS2015} and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+ T gate set we achieve an average non-Clifford gate count of 0.23 log 2 ( 1 / ε ) + 2.13 and T-count 0.56 log 2 ( 1 / ε ) + 5.3 with mixed fallback approximations for diamond norm accuracy ε .This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+ T ). We also provide detailed numerical results for Clifford+T and Clifford+ T gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.
Approximate synthesis of general single-qubit unitaries over the Clifford+T gate set
For the standard Clifford+T gate set, deterministic, ancilla-free synthesis now attains the minimal T-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T gate rotates by half the angle of T, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3 to 10−8, the cost of Clifford+T circuits scales as 2.4log2(1/ε) compared to 3.0log2(1/ε) for T-count-optimal Clifford+T circuits. Once a one-time catalyst state is amortized, the Clifford+T circuits are never costlier than their Clifford+T counterparts.