Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.06909

Arithmetic Depth, Minimal Gate Alphabets, and Exact Program-State Resources for Single-Qubit Dyadic Programs

Tony Newton, Dan-Adrian German

Published Nov 4, 2026• 0 citations
arXivHTMLPDF

Abstract

Resource analyses for quantum programs commonly provide safe upper bounds on qubits, gates, or non-Clifford operations. We study a single-qubit dyadic fragment in which the deepest exact resource layer can instead be inferred exactly. Starting from the normalized-midpoint misty-state syntax, we define dyadic program states and the real cyclotomic tower $K_D=\mathbb Q(2\cos(π/2^D))$. For the projective single-qubit Clifford-cyclotomic tower $\widehat G_D\subseteq SO(3)$, we prove the relative intersection law $\widehat G_D\cap SO(3,K_d)=\widehat G_d$ for $d\le D$. Combining this descent theorem with an arithmetic-closure invariant for adaptive stabilizer processing yields $\mathrm{Fdepth}(U)=\mathrm{Adepth}(U)=\mathrm{Rdepth}(U)$: the smallest real cyclotomic field containing the Bloch matrix of an exactly synthesizable channel, the shallowest dyadic gate alphabet realizing it up to global phase, and the shallowest dyadic program-state layer sufficient for exact stabilizer-assisted implementation coincide. At that common minimum, known fixed-alphabet synthesis gives minimum primitive-rotation count. We package the result as an exact static resource effect and outline a certificate-producing compiler.

DOI
10.48550/arxiv.2611.06909

Related papers

Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets

Simon Forest, David Gosset, Vadym Kliuchnikov +1 more

We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.

arXiv:1501.04944•Journal of Mathematical Physics•Aug 1, 2015•57 citations

A Finite F5 Qupit Layer in TWIST-J: Integer Clifford, Cubic Magic, and Born Minimality

A. M. Thorn

A finite, auditable, five-state qupit computation layer derived from the single cyclotomic axiom J = 1 + ζ₅² of the TWIST-J framework. Main results: • Integer Clifford generation over 𝔽₅ for X_a, Z_b, F, P_α, CX, with Weyl phase ω = (J - 1)³ internal to the axiom. • Born minimality lemma forcing F(z) = |z|² from three finite-checkable axioms (phase blindness, Pythagorean additivity, normalization), without invoking Gleason. • Cubic magic boundary M₅ of order 5, lifting to M_{5^r} of order 5^r in the cyclotomic tower ℚ(ζ_{5^r}), with explicit conjugation formula M_{5^r} X_a M_{5^r}⁻¹ = ω_r^(a³) X_a Q_{3a} Z_{3a²}. • Algebraic exact Grover on 𝔽₅^k via phase-matched amplification with algebraic unit phases μ, ν in the algebraic closure of ℚ. The standard unphased Grover iterate is proved never to reach ±|w⟩ exactly on 5^k. • Probabilities in ℚ(√5) by a character-sum probability field lemma; stabilizer outcomes rational. • Eight selectors and witnesses fix p = 5: the Diophantine lock p² + p + 2 = 2^p, the half-ratio identity (p - 2)/(p + 1) = 1/2, the icosahedral coincidence A₅ ≅ PSL(2, 𝔽₅), and a binary-cyclotomic wall convergence 1/ρ₀ = d(d + 1)/2 = 6. Integer-complete on 8-bit registers. State indexing, phase exponents, and 5×5 lookup tables implement every Clifford tableau step. No floating-point state evolution, no asymptotic limit, no fitted dimensionless constant. A companion verification script reproduces every theorem of the paper. Project: https://twistj.com

•May 18, 2026•0 citations

Numerical Evaluation of ZX Calculus Optimization for Solovay Kitaev Quantum Circuit Synthesis

Dulari De Silva, Anuradha Mahasinghe, Chon-Fai Kam +3 more

Fault-tolerant architectures implement non-Clifford T gates through magic-state distillation, so the T-count of a synthesized circuit dominates its physical cost. The Solovay-Kitaev algorithm approximates any single-qubit unitary from a finite gate set with a sequence length that grows only polylogarithmically in the inverse target error, but it optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see. We report a measurement of what diagrammatic post-processing recovers from that redundancy. Twelve hundred random single-qubit targets, spanning the three Pauli rotation families and the general gate U(theta, phi, lambda), are synthesized over Clifford+T at three recursion depths, translated into graph-like ZX-diagrams, simplified by automated rewriting, and extracted back to circuits. Post-processing removes 26.6-30.1% of the total gate count and 18.5-22.2% of the T-count. The absolute saving grows with recursion depth, from about 60 to about 1600 gates, while the fractional saving does not: it rises slightly from the shallowest setting and is then flat across a twenty-five-fold change in circuit length, and by the deepest setting the four target families are no longer distinguishable from one another. Because the rewrite rules preserve the implemented linear map, the approximation error is unchanged. The compile-time cost of the rewriting layer, by contrast, grows sharply with depth and comes to dominate the synthesis itself.

quant-pharXiv:2608.22810•Aug 25, 2026•0 citations

Lower bounds on the non-Clifford resources for quantum computations

Michael E. Beverland, Earl T. Campbell, Mark Howard +1 more

Abstract Treating stabilizer operations as free, we establish lower bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks. Our bounds apply to adaptive computations using measurements with an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational subroutines including the quantum adder and the multiply-controlled Z gate. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision ɛ requires at least 1/7 ⋅ log 2 (1/ ɛ ) − 4/3 T -states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on ɛ . Up to multiplicative factors, we optimally lower bound the number of T or CCZ states needed to implement the ubiquitous modular adder and multiply-controlled- Z operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.

arXiv:1904.01124•Quantum Science and Technology•Apr 15, 2020•192 citations

Synthesis and Arithmetic of Single Qutrit Circuits

Amolak Ratan Kalra, Michele Mosca, Dinesh Valluri

In this paper we study single qutrit circuits consisting of words over the Clifford +D cyclotomic gate set, where D=diag(±ξa,±ξb,±ξc) , ξ is a primitive 9 -th root of unity and a,b,c are integers. We characterize classes of qutrit unit vectors z with entries in Z[ξ,1χ] based on the possibility of reducing their smallest denominator exponent (sde) with respect to χ:=1–ξ, by acting an appropriate gate in Clifford +D . We do this by studying the notion of `derivatives mod 3 ' of an arbitrary element of Z[ξ] and using it to study the smallest denominator exponent of HDz where H is the qutrit Hadamard gate and D . In addition, we reduce the problem of finding all unit vectors of a given sde to that of finding integral solutions of a positive definite quadratic form along with some additional constraints. As a consequence we prove that the Clifford +D gates naturally arise as gates with sde 0 and 3 in the group U(3,Z[ξ,1χ]) of 3×3 unitaries with entries in Z[ξ,1χ] . We illustrate the general applicability of these methods to obtain an exact synthesis algorithm for Clifford +R and recover the previously known exact synthesis algorithm of Kliuchnikov, Maslov, Mosca (2012). The framework developed to formulate qutrit gate synthesis for Clifford +D extends to qudits of arbitrary prime power.

arXiv:2311.08696•Quantum•Feb 26, 2025•10 citations

An Exactness Barrier for ZX-Calculus Optimization of Synthesized Clifford+T Circuits

Chon-Fai Kam, Anuradha Mahasinghe, Kaushika De Silva +2 more

Gate synthesis and circuit optimization are usually studied separately, and evidence on their interaction is contradictory: ZX-calculus rewriting removes a stable fraction of Solovay-Kitaev circuits, yet almost nothing from number-theoretically synthesized circuits. We show both behaviours follow from a single bound. For any optimizer that preserves the implemented element exactly--including all sound ZX rewriting with extraction--the achievable T-count is bounded below by the denominator exponent of the synthesized ring element. This exactness barrier is computable per instance and separates exact post-processing from approximation-aware resynthesis by a certified factor reaching 101x at recursion depth five. The two behaviours are then the barrier operating at different distances from the floor. For Solovay-Kitaev circuits we prove that the local ZX simplification layer (spider fusion and identity removal) computes exactly the free-product normal form of Z_2 * Z_8, giving exact per-instance compression and, under a calibrated ergodicity hypothesis, a depth-independent limit law confirmed on two independently constructed nets. For number-theoretically synthesized circuits the floor is already saturated: on single-qubit words automated ZX simplification attains it exactly, via a closed-form formula for minimal T-count in terms of phase linkage through the Z-axis normalizer. At two qubits and beyond the same valuation yields unconditional rigidity certificates, which on the quantum-Shannon-decomposition plus gridsynth pipeline certify 99.4-99.9% of the synthesized T-count as incompressible, with rigidity strengthening as accuracy tightens. This explains, and predicts the size of, the near-null optimization recently reported for that pipeline.

quant-pharXiv:2608.22801•Aug 25, 2026•1 citation
Resource analyses for quantum programs commonly provide safe upper bounds on qubits, gates, or non-Clifford operations. We study a single-qubit dyadic fragment in which the deepest exact resource layer can instead be inferred exactly. Starting from the normalized-midpoint misty-state syntax, we define dyadic program states and the real cyclotomic tower KD=Q(2cos⁡(π/2D))K_D=\mathbb Q(2\cos(π/2^D))KD​=Q(2cos(π/2D)). For the projective single-qubit Clifford-cyclotomic tower G^D⊆SO(3)\widehat G_D\subseteq SO(3)GD​⊆SO(3), we prove the relative intersection law G^D∩SO(3,Kd)=G^d\widehat G_D\cap SO(3,K_d)=\widehat G_dGD​∩SO(3,Kd​)=Gd​ for d≤Dd\le Dd≤D. Combining this descent theorem with an arithmetic-closure invariant for adaptive stabilizer processing yields Fdepth(U)=Adepth(U)=Rdepth(U)\mathrm{Fdepth}(U)=\mathrm{Adepth}(U)=\mathrm{Rdepth}(U)Fdepth(U)=Adepth(U)=Rdepth(U): the smallest real cyclotomic field containing the Bloch matrix of an exactly synthesizable channel, the shallowest dyadic gate alphabet realizing it up to global phase, and the shallowest dyadic program-state layer sufficient for exact stabilizer-assisted implementation coincide. At that common minimum, known fixed-alphabet synthesis gives minimum primitive-rotation count. We package the result as an exact static resource effect and outline a certificate-producing compiler.
We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.
A finite, auditable, five-state qupit computation layer derived from the single cyclotomic axiom J = 1 + ζ₅² of the TWIST-J framework. Main results: • Integer Clifford generation over 𝔽₅ for X_a, Z_b, F, P_α, CX, with Weyl phase ω = (J - 1)³ internal to the axiom. • Born minimality lemma forcing F(z) = |z|² from three finite-checkable axioms (phase blindness, Pythagorean additivity, normalization), without invoking Gleason. • Cubic magic boundary M₅ of order 5, lifting to M_{5^r} of order 5^r in the cyclotomic tower ℚ(ζ_{5^r}), with explicit conjugation formula M_{5^r} X_a M_{5^r}⁻¹ = ω_r^(a³) X_a Q_{3a} Z_{3a²}. • Algebraic exact Grover on 𝔽₅^k via phase-matched amplification with algebraic unit phases μ, ν in the algebraic closure of ℚ. The standard unphased Grover iterate is proved never to reach ±|w⟩ exactly on 5^k. • Probabilities in ℚ(√5) by a character-sum probability field lemma; stabilizer outcomes rational. • Eight selectors and witnesses fix p = 5: the Diophantine lock p² + p + 2 = 2^p, the half-ratio identity (p - 2)/(p + 1) = 1/2, the icosahedral coincidence A₅ ≅ PSL(2, 𝔽₅), and a binary-cyclotomic wall convergence 1/ρ₀ = d(d + 1)/2 = 6. Integer-complete on 8-bit registers. State indexing, phase exponents, and 5×5 lookup tables implement every Clifford tableau step. No floating-point state evolution, no asymptotic limit, no fitted dimensionless constant. A companion verification script reproduces every theorem of the paper. Project: https://twistj.com
Fault-tolerant architectures implement non-Clifford T gates through magic-state distillation, so the T-count of a synthesized circuit dominates its physical cost. The Solovay-Kitaev algorithm approximates any single-qubit unitary from a finite gate set with a sequence length that grows only polylogarithmically in the inverse target error, but it optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see. We report a measurement of what diagrammatic post-processing recovers from that redundancy. Twelve hundred random single-qubit targets, spanning the three Pauli rotation families and the general gate U(theta, phi, lambda), are synthesized over Clifford+T at three recursion depths, translated into graph-like ZX-diagrams, simplified by automated rewriting, and extracted back to circuits. Post-processing removes 26.6-30.1% of the total gate count and 18.5-22.2% of the T-count. The absolute saving grows with recursion depth, from about 60 to about 1600 gates, while the fractional saving does not: it rises slightly from the shallowest setting and is then flat across a twenty-five-fold change in circuit length, and by the deepest setting the four target families are no longer distinguishable from one another. Because the rewrite rules preserve the implemented linear map, the approximation error is unchanged. The compile-time cost of the rewriting layer, by contrast, grows sharply with depth and comes to dominate the synthesis itself.
Abstract Treating stabilizer operations as free, we establish lower bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks. Our bounds apply to adaptive computations using measurements with an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational subroutines including the quantum adder and the multiply-controlled Z gate. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision ɛ requires at least 1/7 ⋅ log 2 (1/ ɛ ) − 4/3 T -states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on ɛ . Up to multiplicative factors, we optimally lower bound the number of T or CCZ states needed to implement the ubiquitous modular adder and multiply-controlled- Z operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.
In this paper we study single qutrit circuits consisting of words over the Clifford +D cyclotomic gate set, where D=diag(±ξa,±ξb,±ξc) , ξ is a primitive 9 -th root of unity and a,b,c are integers. We characterize classes of qutrit unit vectors z with entries in Z[ξ,1χ] based on the possibility of reducing their smallest denominator exponent (sde) with respect to χ:=1–ξ, by acting an appropriate gate in Clifford +D . We do this by studying the notion of `derivatives mod 3 ' of an arbitrary element of Z[ξ] and using it to study the smallest denominator exponent of HDz where H is the qutrit Hadamard gate and D . In addition, we reduce the problem of finding all unit vectors of a given sde to that of finding integral solutions of a positive definite quadratic form along with some additional constraints. As a consequence we prove that the Clifford +D gates naturally arise as gates with sde 0 and 3 in the group U(3,Z[ξ,1χ]) of 3×3 unitaries with entries in Z[ξ,1χ] . We illustrate the general applicability of these methods to obtain an exact synthesis algorithm for Clifford +R and recover the previously known exact synthesis algorithm of Kliuchnikov, Maslov, Mosca (2012). The framework developed to formulate qutrit gate synthesis for Clifford +D extends to qudits of arbitrary prime power.
Gate synthesis and circuit optimization are usually studied separately, and evidence on their interaction is contradictory: ZX-calculus rewriting removes a stable fraction of Solovay-Kitaev circuits, yet almost nothing from number-theoretically synthesized circuits. We show both behaviours follow from a single bound. For any optimizer that preserves the implemented element exactly--including all sound ZX rewriting with extraction--the achievable T-count is bounded below by the denominator exponent of the synthesized ring element. This exactness barrier is computable per instance and separates exact post-processing from approximation-aware resynthesis by a certified factor reaching 101x at recursion depth five. The two behaviours are then the barrier operating at different distances from the floor. For Solovay-Kitaev circuits we prove that the local ZX simplification layer (spider fusion and identity removal) computes exactly the free-product normal form of Z_2 * Z_8, giving exact per-instance compression and, under a calibrated ergodicity hypothesis, a depth-independent limit law confirmed on two independently constructed nets. For number-theoretically synthesized circuits the floor is already saturated: on single-qubit words automated ZX simplification attains it exactly, via a closed-form formula for minimal T-count in terms of phase linkage through the Z-axis normalizer. At two qubits and beyond the same valuation yields unconditional rigidity certificates, which on the quantum-Shannon-decomposition plus gridsynth pipeline certify 99.4-99.9% of the synthesized T-count as incompressible, with rigidity strengthening as accuracy tightens. This explains, and predicts the size of, the near-null optimization recently reported for that pipeline.