betaFeedback

WorksPhysics and Astronomy

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

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 KD=Q(2cos⁡(π/2D))K_D=\mathbb Q(2\cos(π/2^D)). For the projective single-qubit Clifford-cyclotomic tower G^D⊆SO(3)\widehat G_D\subseteq 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_d for d≤Dd\le 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): 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.

Introduction

Fault-tolerant quantum programming uses two descriptions of non-Clifford computation that are usually studied separately. In one description a program is a circuit over a gate alphabet, such as Clifford+TT or a finer Clifford-cyclotomic alphabet. In the other, non-Clifford gates are supplied by consumable quantum states and measurement-based injection. The first viewpoint leads naturally to exact synthesis; the second to magic-state resource theories. A programming language that exposes both views should ideally assign a resource effect that is simultaneously a static property of source syntax, a lower bound on physical resources, and an exact predictor of the smallest gate alphabet required by the compiled program.

Projective convention. All compilation and resource claims in this paper concern quantum channels, so global phase is physically irrelevant. Accordingly, gate-alphabet depth is defined through the Bloch image in SO(3)SO(3) (equivalently in PU(2)PU(2)), not through literal membership of a particular phase representative in U(2)U(2). This convention is essential in the relative-descent argument below and matches the phase-insensitive cost convention of exact single-qubit synthesis.

The starting point here is the mist-state rewriting formalism developed in [1, 2]. Its certified version separates raw amplitude collection from normalization, gives a canonical amplitude normal form, and proves that nested equal-weight normalized mists generate dyadic geodesic barycenters [2]. In particular, the nested state at angle π/8\pi/8 is the positive Hadamard eigenstate. Rather than treating this state as an isolated fixed point, we use the dyadic-geodesic theorem as a source language for program states.

The paper then leaves the pedagogical setting. The target is the exact single-qubit dyadic Clifford-cyclotomic union. Forest, Gosset, Kliuchnikov and McKinnon proved a unique canonical form and an optimal exact synthesis algorithm for every fixed Clifford-cyclotomic alphabet [3]. Their denominator-exponent theorem contains enough arithmetic information to answer a different question: given a unitary known to lie somewhere in the nested dyadic tower, what is the smallest alphabet in which it can live? We prove that this minimum is determined exactly by the smallest real cyclotomic field containing the Bloch matrix.

The second ingredient is operational. Beverland, Campbell, Howard and Kliuchnikov established powerful non-Clifford lower bounds using stabilizer nullity and a dyadic monotone, including adaptive stabilizer computations [6]. We use a complementary invariant: not a scalar amount of magic, but the number field generated by Pauli expectation values. Stabilizer processing is arithmetically closed over that field. This produces an exact field-reachability obstruction that is insensitive to how many shallower resource states are supplied.

Main result. For D≥1D \ge1 let

GD:=⟨C,UZ(π2D)⟩,KD:=Q(2cos⁡π2D),G_D := \left\langle C, U_Z\left(\frac{\pi}{2^D}\right)\right\rangle,\qquad K_D := \mathbb{Q}\left(2\cos\frac{\pi}{2^D}\right),

with K1=QK_1 = \mathbb{Q} and with unitaries identified up to global phase through their Bloch representations. For a non-Clifford channel U(ρ)=UρU†U(\rho)=U\rho U^\dagger with U^∈G^D\widehat{U}\in\widehat{G}_D, define

Fdepth⁡(U):=min⁡{D:U^∈SO(3,KD)},\operatorname{Fdepth}(U):=\min\{D:\widehat{U}\in SO(3,K_D)\},
Adepth⁡(U):=min⁡{D:U^∈G^D},\operatorname{Adepth}(U):=\min\{D:\widehat{U}\in\widehat{G}_D\},

and let Rdepth⁡(U)\operatorname{Rdepth}(U) be the minimum possible maximum depth of dyadic program states in any finite adaptive stabilizer protocol implementing UU exactly. We prove

Fdepth⁡(U)=Adepth⁡(U)=Rdepth⁡(U).(1)\operatorname{Fdepth}(U)=\operatorname{Adepth}(U)=\operatorname{Rdepth}(U). \tag*{(1)}

This equality remains meaningful for programs outside every finite level of the Clifford hierarchy: gate-hierarchy membership is not compositional above the Clifford group, whereas the arithmetic resource depth remains finite and exact.

At the common minimum D∗D_\ast, the canonical synthesis of [3] minimizes the number T2D∗(U)\mathcal{T}_{2^{D_\ast}}(U) of primitive π/2D∗\pi/2^{D_\ast} rotations. Hence

QEff⁡(U):=(D∗,T2D∗(U))\operatorname{QEff}(U):=\left(D_\ast,\mathcal{T}_{2^{D_\ast}}(U)\right)

is a lexicographically optimal resource signature: first it minimizes the deepest dyadic resource layer, then it minimizes primitive-rotation count within that layer.

The proof architecture

Figure 1. The proof architecture. The source language supplies dyadic program states; arithmetic closure gives an operational lower bound; relative cyclotomic descent identifies that lower bound with the smallest exact gate alphabet.

Relation to prior work. Magic-state injection and small-angle resource states are established tools [4, 5]. Complete one-qubit Clifford-hierarchy structure is now known [7], and dyadic quantum fragments have complete rewriting systems in other formalisms [8]. Quantum type systems already reason about Clifford structure, TT gates and selected injection circuits [9], while resource-aware languages infer quantitative upper bounds such as circuit width [10]. The contribution here is narrower: an exact equality between arithmetic field depth, minimum dyadic gate-alphabet depth and minimum dyadic program-state depth, together with an exact static resource effect that remains meaningful beyond the finite Clifford hierarchy. Earlier rotation-group structure goes back to Radin–Sadun, and later arithmetic-group work studies the ambient Clifford-cyclotomic groups; recent multiqubit synthesis results show that ancillas can change ambient ring-synthesis questions. Our theorem is instead a relative single-qubit descent statement inside the nested dyadic tower.

Dyadic mist states as program states

We first isolate the fragment of mist-state semantics needed later. Let

q(x):=cos⁡(πx2)∣0⟩+sin⁡(πx2)∣1⟩,0≤x≤1.q(x) := \cos\left(\frac{\pi x}{2}\right)|0\rangle+ \sin\left(\frac{\pi x}{2}\right)|1\rangle,\qquad0 \le x \le1.

For equal-norm real states on the shorter arc, normalized addition is the geodesic midpoint [2]:

μ(q(x),q(y)):=N(q(x)+q(y))=q(x+y2).\mu(q(x),q(y)) := N(q(x)+q(y)) = q\left(\frac{x+y}{2}\right).

Definition 2.1 (Normalized-midpoint depth). A normalized-midpoint term is generated from endpoint leaves 0,10,1 and the binary constructor μ\mu. Its denotation is the dyadic coordinate obtained from 0,10,1 by repeated averaging. The minimum depth of any term denoting xx is denoted mdepth⁡(x)\operatorname{mdepth}(x).

Theorem 2.2 (Exact dyadic depth). Let x=m/2D∈(0,1)x = m/2^{D} \in(0,1) be in lowest dyadic form, so mm is odd. Then

mdepth⁡(x)=D.\operatorname{mdepth}(x) = D.

Proof. By induction, every midpoint tree of maximum depth dd evaluates to a rational whose reduced denominator divides 2d2^{d}. Hence m/2Dm/2^{D} cannot occur below depth DD. Conversely, use a complete binary tree with 2D2^{D} leaves, label exactly mm leaves by 1 and the remainder by 0, and average level by level. The root evaluates to m/2Dm/2^{D}.

The relevant source state is therefore

qm,D:=q(m/2D)=cos⁡(mπ2D+1)∣0⟩+sin⁡(mπ2D+1)∣1⟩.(2)q_{m,D} := q(m/2^{D}) = \cos\left(\frac{m\pi}{2^{D+1}}\right)|0\rangle+ \sin\left(\frac{m\pi}{2^{D+1}}\right)|1\rangle. \tag*{(2)}

For m=1,D=2m=1,D=2 this is the positive Hadamard eigenstate highlighted in [1, 2].

Uniform state–gate conversion

Define the standard phase-program state

∣Aθ⟩:=∣0⟩+eiθ∣1⟩2,UZ(θ):=diag⁡(1,eiθ).\lvert A_\theta\rangle:= \frac{\lvert0\rangle+ e^{i\theta}\lvert1\rangle}{\sqrt{2}}, \qquad U_Z(\theta) := \operatorname{diag}(1,e^{i\theta}).

A single fixed Clifford relates the two encodings.

Lemma 2.3 (Uniform Clifford equivalence). For every real θ\theta,

SH∣Aθ⟩=eiθ/2(cos⁡θ2∣0⟩+sin⁡θ2∣1⟩).SH\lvert A_\theta\rangle= e^{i\theta/2}\left(\cos\frac{\theta}{2}\lvert0\rangle+ \sin\frac{\theta}{2}\lvert1\rangle\right).

In particular, with θ=mπ/2D\theta= m\pi/2^D, qm,Dq_{m,D} is Clifford-equivalent to ∣Aθ⟩\lvert A_\theta\rangle.

Proof. Expand H∣Aθ⟩H\lvert A_\theta\rangle and use 1+eiθ=2eiθ/2cos⁡(θ/2)1+e^{i\theta}=2e^{i\theta/2}\cos(\theta/2) and 1−eiθ=−2ieiθ/2sin⁡(θ/2)1-e^{i\theta}=-2ie^{i\theta/2}\sin(\theta/2). The phase gate S=diag⁡(1,i)S=\operatorname{diag}(1,i) removes the factor −i-i from the second component.

The standard one-bit injection circuit then makes the program-state interpretation operational. For ∣ψ⟩=a∣0⟩+b∣1⟩\lvert\psi\rangle=a\lvert0\rangle+b\lvert1\rangle, use the data qubit as control of a CNOT whose target is ∣Aθ⟩\lvert A_\theta\rangle, then measure the ancilla in the computational basis. The two unnormalized data branches are

0:UZ(θ)∣ψ⟩/2,(3)0:\quad U_Z(\theta)\lvert\psi\rangle/\sqrt{2}, \tag*{(3)}
1:eiθUZ(−θ)∣ψ⟩/2.(4)1:\quad e^{i\theta}U_Z(-\theta)\lvert\psi\rangle/\sqrt{2}. \tag*{(4)}

Thus the second branch is corrected by UZ(2θ)U_Z(2\theta). This doubled-angle feed-forward is the familiar small-angle magic-state cascade [4].

For the primitive dyadic phase x=0.b1⋯bDx=0.b_1\cdots b_D, doubling removes the first binary digit:

2x=b1+0.b2⋯bD.2x=b_1+0.b_2\cdots b_D.

Since UZ(π)=ZU_Z(\pi)=Z is Clifford,

UZ(πx)2=Zb1UZ(π 0.b2⋯bD)up to global phase.(5)U_Z(\pi x)^2=Z^{b_1}U_Z(\pi\,0.b_2\cdots b_D)\quad\text{up to global phase}. \tag*{(5)}

Hence a failed injection consumes one bit of the canonical dyadic source word while emitting only a free Pauli correction. The worst-case number of non-Clifford injection stages is D−1D-1, whereas the expected number is

1+12+⋯+12D−2=2−2−(D−2)<2.1+\frac{1}{2}+\cdots+\frac{1}{2^{D-2}}=2-2^{-(D-2)}<2.

We use this axial compiler later only for the upper-bound direction of the resource theorem; the main arithmetic result applies to arbitrary multiaxis words in the dyadic Clifford-cyclotomic group.

Arithmetic closure of stabilizer protocols

We next give the operational lower-bound mechanism. The invariant is field-valued rather than a scalar magic monotone.

For an nn-qubit state ρ\rho and Pauli P∈PnP\in\mathcal{P}_n, write

rP(ρ):=Tr⁡(Pρ).r_P(\rho):=\operatorname{Tr}(P\rho).

For a finite resource family R={ρ1,…,ρs}\mathcal{R}=\{\rho_1,\ldots,\rho_s\} define

A(R):=Z[12,{rP(ρj)}j,P],(6)A(\mathcal{R}) := \mathbb{Z}\left[\frac{1}{2},\{r_P(\rho_j)\}_{j,P}\right], \tag*{(6)}
K(R):=Frac⁡A(R).(7)K(\mathcal{R}) := \operatorname{Frac} A(\mathcal{R}). \tag*{(7)}

Theorem 3.1 (Stabilizer arithmetic closure). Consider any finite adaptive protocol generated by Clifford unitaries, stabilizer ancillas, Pauli measurements, deterministic classical feed-forward and discarding, with nonfree input resources R\mathcal{R}. No external operation carrying additional real or algebraic parameters is supplied for free. For every measurement history ss, every Pauli coordinate of the unnormalized branch ρ~s\widetilde{\rho}_s lies in A(R)A(\mathcal{R}). If ps=Tr⁡ρ~s≠0p_s=\operatorname{Tr}\widetilde{\rho}_s\ne0, then every Pauli coordinate of the normalized branch ρs=ρ~s/ps\rho_s=\widetilde{\rho}_s/p_s lies in K(R)K(\mathcal{R}).

Proof. The claim is preserved by each primitive operation. Clifford conjugation sends a Pauli to ±\pm another Pauli and therefore only permutes and signs coordinates. Stabilizer ancillas have Pauli expectations in {0,±1}\{0,\pm1\}. Tensor products multiply Pauli coordinates. If MM is the measured Pauli and Πb=(I+(−1)bM)/2\Pi_b=(I+(-1)^bM)/2, then for any Pauli QQ,

ΠbQΠb={12(Q+(−1)bQM),[Q,M]=0,0,{Q,M}=0.\Pi_b Q\Pi_b = \begin{cases} \frac{1}{2}\left(Q+(-1)^bQM\right), & [Q,M]=0,\\ 0, & \{Q,M\}=0. \end{cases}

up to the harmless Pauli sign in the commuting product. Thus branch coordinates are dyadic-rational linear combinations of previous coordinates. Partial trace selects the coordinates with identity on the discarded subsystem. Induction over a branch proves the ring statement. Normalization divides all coordinates by psp_s, itself a branch coordinate in A(R)A(\mathcal{R}), and therefore stays in the fraction field. □

The same statement applies to exact channels.

Corollary 3.2 (Channel field obstruction). Let an adaptive stabilizer protocol with resources R\mathcal{R} implement a deterministic channel E\mathcal{E}. Every entry of the Pauli transfer matrix of E\mathcal{E} lies in A(R)A(\mathcal{R}). For a heralded exact implementation whose nonzero success probability is independent of the input, the normalized success channel has Pauli transfer entries in K(R)K(\mathcal{R}).

Proof. Apply the protocol to one half of the normalized maximally entangled stabilizer state ∣Φ⟩|\Phi\rangle. By Theorem 3.1, the Choi state J(E)=(E⊗I)(∣Φ⟩⟨Φ∣)J(\mathcal{E})=(\mathcal{E}\otimes I)(|\Phi\rangle\langle\Phi|) has Pauli coordinates in the stated ring or field. With d=2nd=2^n,

2−nTr⁡[PE(Q)]=Tr⁡[(P⊗QT)J(E)],2^{-n}\operatorname{Tr}[P\mathcal{E}(Q)]=\operatorname{Tr}\left[(P\otimes Q^{\mathsf{T}})J(\mathcal{E})\right],

so each Pauli-transfer entry is itself one of these Pauli coordinates up to the conventional Pauli transpose sign. □

This result is complementary to scalar resource monotones such as stabilizer extent, nullity and the dyadic monotone of [6]. It does not count copies. Instead, it states that a finite stabilizer protocol cannot adjoin a number absent from the field generated by its supplied resources.

The dyadic Clifford-cyclotomic tower

Let C\mathcal{C} be the single-qubit Clifford group. Following [3], define

GD:=⟨C,UZ(π2D)⟩,D≥1.(8)\mathcal{G}_D:=\left\langle\mathcal{C},U_Z\left(\frac{\pi}{2^D}\right)\right\rangle,\qquad D\ge1. \tag*{(8)}
Nested gate and field towers

Figure 2. The nested gate and field towers. The relative intersection theorem proved below says that, inside the dyadic synthesizable union, descending the arithmetic field is exactly the same as descending the gate alphabet.

Since Uz(π/2)U_z(\pi/2) is Clifford, G1=C\mathcal{G}_1=\mathcal{C}. Modulo global phase, the Bloch representation maps these groups into SO(3)SO(3); we write G^D\widehat{\mathcal{G}}_D for the image. The projective groups form a strict tower

G^1⊊G^2⊊G^3⊊⋯ ,\widehat{\mathcal{G}}_1 \subsetneq\widehat{\mathcal{G}}_2 \subsetneq\widehat{\mathcal{G}}_3 \subsetneq\cdots,

with strictness following, for example, from the fixed-axis rotation characterization in the canonical synthesis theory.

The associated real cyclotomic fields are

KD:=Q(βD),βD:=2cos⁡π2D,D≥2,(9)K_D := \mathbb{Q}(\beta_D), \qquad\beta_D := 2\cos\frac{\pi}{2^D}, \qquad D \ge2, \tag*{(9)}

with K1:=QK_1 := \mathbb{Q}. They form a quadratic tower

K1⊊K2⊊K3⊊⋯ ,[KD:KD−1]=2,(10)K_1 \subsetneq K_2 \subsetneq K_3 \subsetneq\cdots, \qquad[K_D:K_{D-1}] = 2, \tag*{(10)}

with

βD2=βD−1+2.(11)\beta_D^2 = \beta_{D-1}+2. \tag*{(11)}

The ring of integers of KDK_D is Z[βD]\mathbb{Z}[\beta_D]; this is the standard maximal-real-subfield description for power-of-two cyclotomic fields [16].

Imported fixed-alphabet structure

For n=2Dn=2^D, Forest et al. [3] give a unique canonical form for every U∈GDU\in\mathcal{G}_D and an optimal synthesis algorithm [3]. In the Bloch representation a non-Clifford element has a canonical decomposition

U^=Rp1a1Rp2a2⋯RpmamC^,(12)\widehat{U}=R_{p_1}^{a_1}R_{p_2}^{a_2}\cdots R_{p_m}^{a_m}\widehat{C}, \tag*{(12)}

where pi∈{x,y,z}p_i\in\{x,y,z\}, adjacent axes differ, 1≤ai<2D−11\le a_i<2^{D-1}, and C^\widehat{C} is Clifford. Let

qa=2D−1−2twhen a=2tu with u odd.(13)q_a=2^{D-1}-2^t \quad\text{when } a=2^t u\text{ with }u\text{ odd}. \tag*{(13)}

This is the specialization of Eq. (23) in [3] to n=2Dn=2^D.

If N=∑iqaiN=\sum_i q_{a_i}, their denominator-exponent theorem states that the largest βD\beta_D-denominator exponent appearing in U^\widehat{U} is NN, while the unique exceptional row has largest exponent N−qa1N-q_{a_1}. Their Corollary 4.2 proves uniqueness of the canonical form and minimum primitive-rotation cost at the fixed alphabet. We use these results as imported ingredients; the new step is relative descent between consecutive dyadic alphabets.

Cyclotomic parity and relative descent

The key arithmetic observation is that an element of the shallower field cannot have an odd reduced denominator exponent in the deeper generator. We use the standard facts that OKD=Z[βD]\mathcal{O}_{K_D}=\mathbb{Z}[\beta_D], that KD/KD−1K_D/K_{D-1} is quadratic, and that its nontrivial automorphism sends βD↦−βD\beta_D\mapsto-\beta_D.

Lemma 5.1 (Even-denominator lemma). Let D≥2D \ge2. Suppose x∈KD−1x \in K_{D-1} can be written

x=wβDr,w∈Z[βD],x = \frac{w}{\beta_D^r}, \qquad w \in\mathbb{Z}[\beta_D],

where ww is not divisible by βD\beta_D. Then rr is even.

Proof. The nontrivial element σD∈Gal⁡(KD/KD−1)\sigma_D \in\operatorname{Gal}(K_D/K_{D-1}) satisfies σD(βD)=−βD\sigma_D(\beta_D)=-\beta_D. Since xx is fixed by σD\sigma_D,

σD(w)=(−1)rw.\sigma_D(w)=(-1)^r w.

If rr were odd, then σD(w)=−w\sigma_D(w)=-w. Let sD=[KD:Q]s_D=[K_D:\mathbb{Q}] and write the unique integral power-basis expression

w=c0+c1βD+⋯+csD−1βDsD−1,cj∈Z.w=c_0+c_1\beta_D+\cdots+c_{s_D-1}\beta_D^{s_D-1}, \qquad c_j\in\mathbb{Z}.

Applying σD\sigma_D and comparing coefficients shows that all even-power coefficients vanish. Hence w=βDvw=\beta_Dv for some v∈Z[βD]v\in\mathbb{Z}[\beta_D], contradicting the reduced-denominator assumption.

Remark 5.2. The lemma also has a valuation proof. The unique prime above 22 is totally ramified along the power-of-two real cyclotomic tower; the valuation of an element from KD−1K_{D-1} doubles upon extension to KDK_D. The Galois proof above is shorter and keeps the argument self-contained once the integral power basis is fixed.

Theorem 5.3 (One-step relative intersection). For every D≥2D \ge2,

G^D∩SO(3,KD−1)=G^D−1.\widehat{\mathcal{G}}_D \cap SO(3,K_{D-1})=\widehat{\mathcal{G}}_{D-1}.

Proof. The inclusion G^D−1⊆G^D∩SO(3,KD−1)\widehat{\mathcal{G}}_{D-1}\subseteq\widehat{\mathcal{G}}_D\cap SO(3,K_{D-1}) is immediate. For the reverse inclusion, let U^∈G^D\widehat{U}\in\widehat{\mathcal{G}}_D have all entries in KD−1K_{D-1} and take its Forest canonical form (12). If UU is Clifford there is nothing to prove. Otherwise let N=∑iqaiN=\sum_iq_{a_i}. By the denominator-exponent theorem of [3], some entry has reduced βD\beta_D-denominator exponent NN, and an entry in the exceptional row has reduced exponent N−qa1N-q_{a_1}. Both entries lie in KD−1K_{D-1}, so Theorem 5.1 forces both exponents to be even. Therefore qa1q_{a_1} is even.

Write a1=2tua_1=2^tu with uu odd. By (13), qa1=2D−1−2tq_{a_1}=2^{D-1}-2^t. Since 1≤a1<2D−11\le a_1<2^{D-1}, t≤D−2t\le D-2, and qa1q_{a_1} is even if and only if t≥1t\ge1. Thus a1a_1 is even. The first syllable is therefore already a shallower rotation:

Rp1(a1π2D)=Rp1((a1/2)π2D−1)∈G^D−1.R_{p_1}\left(\frac{a_1\pi}{2^D}\right)=R_{p_1}\left(\frac{(a_1/2)\pi}{2^{D-1}}\right)\in\widehat{\mathcal{G}}_{D-1}.

Multiply its inverse into U^\widehat{U}. Because the removed factor itself has entries in KD−1K_{D-1}, the remaining suffix still has entries in KD−1K_{D-1}; because the original Forest word was canonical, that suffix is again a canonical word at level DD. Induction on the number of non-Clifford syllables therefore forces every aia_i to be even. Hence every non-Clifford syllable belongs to G^D−1\widehat{\mathcal{G}}_{D-1}, as does the final Clifford, so U^∈G^D−1\widehat{U}\in\widehat{\mathcal{G}}_{D-1}.

Corollary 5.4 (Full relative intersection). For 1≤d≤D1\le d\le D,

G^D∩SO(3,Kd)=G^d.\widehat{\mathcal{G}}_D\cap SO(3,K_d)=\widehat{\mathcal{G}}_d.

Proof. Iterate Theorem 5.3 from DD down to dd.

The statement is deliberately relative. Forest et al. show that for most even nn, the Clifford-cyclotomic group is strictly smaller than the ambient group of all ring-valued unitaries [3]. We do not assert that field membership alone characterizes arbitrary SO(3,KD)SO(3,K_D) matrices. Rather, Theorem 5.4 states that within the already-synthesizable dyadic union, a fall in field depth is exactly a fall in gate-alphabet depth.

Field depth, alphabet depth and resource depth

We can now state the principal theorem precisely.

Definition 6.1 (Field and alphabet depth). For a projective unitary with U^∈UDG^D\hat{U} \in\mathsf{U}_D \widehat{\mathcal{G}}_D, define

Fdepth⁡(U):=min⁡{D≥1:U^∈SO⁡(3,KD)}.(14)\operatorname{Fdepth}(U) := \min\{D \ge1 : \hat{U} \in\operatorname{SO}(3,K_D)\}. \tag*{(14)}
Adepth⁡(U):=min⁡{D≥1:U^∈G^D}.(15)\operatorname{Adepth}(U) := \min\{D \ge1 : \hat{U} \in\widehat{\mathcal{G}}_D\}. \tag*{(15)}

Both quantities depend only on the channel ρ↦UρU†\rho\mapsto U\rho U^\dagger.

Theorem 6.2 (Arithmetic alphabet theorem). For every U^∈UDG^D\hat{U} \in\mathsf{U}_D \widehat{\mathcal{G}}_D,

Fdepth⁡(U)=Adepth⁡(U).\operatorname{Fdepth}(U) = \operatorname{Adepth}(U).

Proof. Every generator of G^D\widehat{\mathcal{G}}_D has entries in KDK_D, so Fdepth⁡(U)≤Adepth⁡(U)\operatorname{Fdepth}(U) \le\operatorname{Adepth}(U). Let D=Adepth⁡(U)D = \operatorname{Adepth}(U) and d=Fdepth⁡(U)d = \operatorname{Fdepth}(U). If d<Dd < D, then U^∈G^D∩SO⁡(3,Kd)\hat{U} \in\widehat{\mathcal{G}}_D \cap\operatorname{SO}(3,K_d). By Theorem 5.4, U^∈G^d\hat{U} \in\widehat{\mathcal{G}}_d, contradicting the minimality of the projective alphabet depth DD.

Dyadic program-state resource depth

For D≥2D \ge2, let MD\mathcal{M}_D denote the set of one-qubit dyadic program states qm,Dq_{m,D} of (2) with mm odd, together with their Clifford images. Their Pauli coordinates generate exactly KDK_D: indeed

⟨X⟩=sin⁡mπ2D,⟨Z⟩=cos⁡mπ2D,\langle X\rangle= \sin\frac{m\pi}{2^D}, \qquad\langle Z\rangle= \cos\frac{m\pi}{2^D},

and for odd mm these values are Galois conjugates of the primitive real cyclotomic generators.

Definition 6.3 (Dyadic program-state resource depth). For a non-Clifford channel with U^∈UDG^D\hat{U} \in\mathsf{U}_D \widehat{\mathcal{G}}_D, let Rdepth⁡(U)\operatorname{Rdepth}(U) be the least D≥2D \ge2 for which there exists a finite adaptive stabilizer protocol that implements ρ↦UρU†\rho\mapsto U\rho U^\dagger exactly using an arbitrary finite number of resource states from ⋃d≤DMd\bigcup_{d\le D}\mathcal{M}_d. Stabilizer ancillas, adaptive Pauli measurement, classical feed-forward, discarding, and catalytic use of states from the same declared resource family are allowed.

Theorem 6.4 (Exact resource-depth theorem). For every non-Clifford channel with U^∈UDG^D\hat{U} \in\mathsf{U}_D \widehat{\mathcal{G}}_D,

Fdepth⁡(U)=Adepth⁡(U)=Rdepth⁡(U).\operatorname{Fdepth}(U) = \operatorname{Adepth}(U) = \operatorname{Rdepth}(U).

Proof. Set D∗=Fdepth⁡(U)=Adepth⁡(U)D_* = \operatorname{Fdepth}(U) = \operatorname{Adepth}(U) by Theorem 6.2. For the lower bound, suppose UU had an exact stabilizer implementation whose every dyadic resource state had depth at most d<D∗d < D_*. All resource Pauli coordinates would then lie in KdK_d, and because the fields are nested, the field generated by any finite collection of them is still contained in KdK_d. By Theorem 3.2, every Pauli-transfer entry of the implemented channel would lie in KdK_d. The Pauli transfer matrix of a unitary channel is its Bloch rotation, contradicting the definition of D∗D_*. Thus Rdepth⁡(U)≥D∗\operatorname{Rdepth}(U) \ge D_*.

For the upper bound, U^∈G^D∗\hat{U} \in\widehat{\mathcal{G}}_{D_*} has a finite exact decomposition, up to global phase, into Clifford gates and primitive UZ(π/2D∗)U_Z(\pi/2^{D_*}) rotations. By Theorem 2.3 each primitive rotation has a Clifford-equivalent dyadic program state of depth D∗D_*. The injection rule (3)–(4) implements the rotation exactly; every failed branch requests only a doubled-angle correction, hence a strictly shallower dyadic layer until the correction is Clifford. Therefore depth D∗D_* resources suffice, and Rdepth⁡(U)≤D∗\operatorname{Rdepth}(U) \le D_*.

This theorem should not be confused with a statement that resource count equals arithmetic depth. The count is a separate optimization problem. The theorem identifies the deepest algebraic layer that must appear somewhere in an exact implementation.

Exact resource effects and optimal compilation

At a fixed alphabet n=2Dn = 2^D, Forest et al. define Tn(U)T_n(U) as the minimum number of primitive UZ(π/n)U_Z(\pi/n) gates required to implement UU up to global phase and prove that their canonical decomposition attains this minimum [3]. Combining their fixed-level theorem with Theorem 6.4 yields a two-component exact resource signature. We call it a resource effect rather than a full type system: the present paper does not supply general typing rules for an arbitrary higher-order quantum language.

Definition 7.1 (Exact dyadic resource effect). For non-Clifford U∈⋃DGDU \in\bigcup_D \mathcal{G}_D, let

D∗(U):=Fdepth⁡(U)=Adepth⁡(U)=Rdepth⁡(U)D_*(U) := \operatorname{Fdepth}(U) = \operatorname{Adepth}(U) = \operatorname{Rdepth}(U)

and define

QEff⁡(U):=(D∗(U),T2D∗(U)(U)).\operatorname{QEff}(U) := (D_*(U), T_{2^{D_*(U)}}(U)).

Theorem 7.2 (Lexicographic optimality). Order exact dyadic gate implementations first by alphabet depth DD and then by primitive-rotation count TT. The pair QEff⁡(U)=(D∗,T∗)\operatorname{QEff}(U) = (D_*, T_*) is the unique lexicographic optimum: no exact implementation exists with depth D<D∗D < D_*, and among depth-D∗D_* implementations none uses fewer than T∗T_* primitive rotations.

Proof. The first claim is the definition of Adepth together with Theorem 6.4. The second is the fixed-alphabet optimality theorem of [3] applied at n=2D∗n = 2^{D_*}.

The result gives a static effect analysis familiar from resource-aware programming languages, but with a stronger guarantee than an upper bound: the first component is an exact operational minimum, not merely a conservative estimate. This complements quantum type systems that track stabilizer structure, TT gates and injection patterns [9], and resource type-and-effect systems that infer quantitative circuit bounds [10].

Exact field-depth analysis

Suppose a source circuit gives an a priori alphabet bound Dmax⁡D_{\max}, so its exact Bloch matrix lies in SO⁡(3,KDmax⁡)\operatorname{SO}(3, K_{D_{\max}}). Field depth can then be computed by fixed-field descent rather than by searching gate alphabets. Starting from j=Dmax⁡j = D_{\max}, apply the nontrivial involution σj:Kj→Kj\sigma_j: K_j \to K_j with σj(βj)=−βj\sigma_j(\beta_j) = -\beta_j entrywise. If every Bloch entry is fixed, then the matrix lies in SO⁡(3,Kj−1)\operatorname{SO}(3, K_{j-1}) and one decrements jj; otherwise the current jj is the field depth. Because the source supplies a finite upper bound and exact algebraic representations, this process terminates. By Theorems 6.2 and 6.4, its output is simultaneously the minimum projective gate alphabet and the minimum dyadic program-state layer.

Compilation pipeline

An exact compiler for the dyadic single-qubit language can therefore be organized as follows.

Stage 1. Compute the Bloch matrix U~\widetilde{U} exactly from the source program.

Stage 2. Starting from the source-level upper bound, descend the cyclotomic tower by the fixed-field test above. The first non-fixed level is the exact field depth; by Theorems 6.2 and 6.4, it is also the minimum projective gate alphabet and minimum dyadic program-state resource depth.

Stage 3. Run the fixed-alphabet canonical synthesis of [3] once at n=2Dn = 2^D to obtain minimum primitive-rotation count.

Stage 4. Replace primitive rotations, if a measurement-based backend is requested, by the depth-DD program states of § 2 and their adaptive correction cascades.

Stage 5. Verify the emitted program by exact algebraic channel semantics, for example through an exact Choi representation. No search through all shallower gate alphabets is required once field depth has been identified.

Faithful axial embedding and a universal separating test

The main theorem concerns the entire dyadic Clifford-cyclotomic union. The original mist syntax gives a particularly simple source-to-target semantics on the axial fragment. Let source terms be normalized-midpoint expressions with denotation x∈Z[1/2]∩[0,1]x \in\mathbb{Z}[1/2] \cap[0,1], and compile

Compile⁡(x)≔Ux,Ux(ρ)=Uz(πx)ρUz(πx)†.\operatorname{Compile}(x) \coloneqq U_x,\qquad U_x(\rho)=U_z(\pi x)\rho U_z(\pi x)^\dagger.

By Theorem 2.3, the source state q(x)q(x) is a free-Clifford transform of the phase-program state that injects Uz(πx)U_z(\pi x).

Theorem 8.1 (Semantic faithfulness on the axial fragment). For dyadic x,y∈[0,1]x,y \in[0,1],

q(x)=q(y)⟺Ux=Uy.q(x)=q(y)\Longleftrightarrow U_x=U_y.

Moreover, one fixed stabilizer observation separates every inequivalent pair: prepare ∣+⟩\lvert+\rangle, apply the compiled channel, and measure X.

Proof. The parametrization q(x)q(x) is injective on [0,1][0,1], and Uz(πx)U_z(\pi x) and Uz(πy)U_z(\pi y) define the same channel on that interval only when x=yx=y. For the separating experiment, the probability of the +1+1 outcome after applying Uz(πx)U_z(\pi x) to ∣+⟩\lvert+\rangle is

p+(x)=1+cos⁡(πx)2,p_+(x)=\frac{1+\cos(\pi x)}{2},

which is strictly decreasing on [0,1][0,1].

This theorem is intentionally stated as faithfulness rather than as a general full-abstraction result: the midpoint source fragment used here has no independently developed contextual operational semantics. Fully abstract quantum models are established prior art [11]; the present point is the exact, experimentally separable embedding of this particular source notation into channel semantics.

Examples and structural consequences

The Hadamard magic state

For x=1/4x=1/4, Theorem 2.2 gives source depth D=2D=2 and

q1,2=cos⁡π8∣0⟩+sin⁡π8∣1⟩.q_{1,2}=\cos\frac{\pi}{8}\lvert0\rangle+\sin\frac{\pi}{8}\lvert1\rangle.

The corresponding phase gate is Uz(π/4)U_z(\pi/4), i.e. the T gate up to the conventional choice of global phase. Thus the nested Hadamard eigenstate from [1, 2] is the first primitive non-Clifford dyadic program state in this hierarchy.

Unlimited shallower states cannot cross an exact field boundary

Let D≥3D \ge3. Any finite collection of program states of depths at most D−1D-1 has Pauli coordinates in KD−1K_{D-1}. By Theorem 3.1, an adaptive stabilizer protocol using any finite number of such states still produces only channels with Pauli-transfer entries in KD−1K_{D-1}. Therefore it cannot exactly implement a target UU with Fdepth(U)=DF_{\mathrm{depth}}(U)=D. This is an exact-arithmetic obstruction, not a statement about approximate synthesis: approximation can of course approach finer rotations using a fixed universal alphabet.

Resource depth survives Clifford-hierarchy escape

The Clifford hierarchy is not closed under multiplication above its second level. For example, products of noncommuting dyadic axial rotations may leave every finite hierarchy level even though they remain exactly synthesizable in a finite Clifford-cyclotomic alphabet. The complete one-qubit hierarchy classification in [7] makes the distinction explicit. Our type D∗(U)D_*(U) remains finite because it is defined by exact arithmetic/gate-alphabet reachability rather than finite-hierarchy membership. Thus “Clifford level” and “resource depth” agree on primitive axial rotations but are different invariants for compositional programs.

Scope, claim boundary and related work

The paper deliberately separates imported results from new deductions.

Imported ingredients. The mist-state language and its fixed-point examples originate in [1]; the certified semantics, explicit normalization discipline, CANF and dyadic-geodesic closure are from [2]. Magic-state injection and small-angle rotation resources are established technology [4]; the recent general magic-gate-teleportation framework of Zheng, Zang and Kubica gives a broad structural account of useful resource states and feed-forward [5]. Forest et al. supply the fixed-alphabet canonical form, denominator-exponent pattern and rotation-count optimality [3], building on earlier structure theory for discrete rotation groups such as Radin–Sadun [12]. Arithmetic-group work studies the ambient Clifford-cyclotomic groups and their indices [13], while recent multiqubit work characterizes power-of-two ring synthesis with ancillas [14, 15]. Number-theoretic resource lower bounds for stabilizer computation, including a dyadic monotone, are established in [6]. Dyadic rewriting/completeness is also known in sum-over-paths form [8]. None of those results is re-claimed here.

Contribution isolated here. The mathematical step specific to this paper is the relative descent theorem Theorems 5.3 and 5.4, obtained by combining the fixed-alphabet denominator pattern with the even-denominator lemma for the power-of-two real cyclotomic tower. Its principal consequence is the equality between field depth and minimum gate-alphabet depth, Theorem 6.2. Combining that equality with the stabilizer arithmetic-closure theorem yields the program-state resource equality Theorem 6.4. Finally, fixed-alphabet optimality converts the common depth into the lexicographically optimal resource effect of Theorem 7.2.

Limitations. The resource equality is an exact, single-qubit, dyadic statement in a declared stabilizer-plus-dyadic-program-state model. It does not claim that field depth measures the amount of magic, that it determines approximate synthesis cost, or that the same equality holds for arbitrary multiqubit magic resources. It also does not replace existing complete rewriting calculi or general type systems, and QEff should not be read as a principal type theorem for a higher-order language. The result instead identifies an exact arithmetic layer that controls reachability and a certifiable static resource effect in one nested single-qubit resource family.

Conclusion

A simple dyadic source syntax leads to a stronger invariant than its educational origin suggests. Normalized midpoint depth identifies a canonical hierarchy of one-qubit program states; those states inject exact dyadic phase rotations; and their Pauli expectations generate the same real cyclotomic tower that appears in Clifford-cyclotomic synthesis. The stabilizer arithmetic-closure theorem turns this field tower into an operational obstruction. The relative intersection theorem then supplies the missing converse: within the exactly synthesizable dyadic union, descending the arithmetic field is precisely descending the gate alphabet.

The resulting identity

Fdepth⁡(U)=Adepth⁡(U)=Rdepth⁡(U)\operatorname{Fdepth}(U)=\operatorname{Adepth}(U)=\operatorname{Rdepth}(U)

provides an exact resource effect for non-Clifford single-qubit dyadic programs in the declared program-state model. It remains meaningful after composition leaves the finite Clifford hierarchy, and when paired with fixed-alphabet optimal synthesis it yields a lexicographically optimal compiler objective. The next natural question is whether an analogous relative-descent theorem survives in selected multiqubit Clifford-cyclotomic or commuting-Pauli fragments, where field composita, stabilizer codes and nontrivial gate-teleportation structure interact.

Exact channel normal form for adaptive branches

For completeness we record a representation suitable for an independent verifier. Let a finite adaptive program have externally visible classical outcome oo and internal measurement history ss, with branch Kraus operator Ko,sK_{o,s}. Define

Jo:=∑s∣vec⁡Ko,s⟩⟨vec⁡Ko,s∣J_o := \sum_s \lvert\operatorname{vec} K_{o,s}\rangle\langle\operatorname{vec} K_{o,s}\rvert

The family {o↦Jo}\{o \mapsto J_o\} is the Choi representation of the externally visible quantum instrument after internal transcripts have been hidden. Equality of these Choi operators is equivalent to equality of the induced completely positive maps. In the dyadic fragment all entries lie in an explicitly generated cyclotomic number field, so equivalence is an exact algebraic decision rather than a floating-point comparison.

For the injection circuit of § 2, each terminal branch is proportional to the same target unitary after the prescribed feed-forward. Summing branch Choi matrices therefore gives the Choi matrix of the target unitary channel exactly. This supplies a convenient backend certificate for the compiler pipeline of § 7.

A second proof of the parity lemma

The Galois proof of Theorem 5.1 can be replaced by a valuation argument. Let pD\mathfrak p_D be the unique prime of KDK_D over 2. In the power-of-two cyclotomic tower the extension KD/KD−1K_D/K_{D-1} is quadratic and pD−1\mathfrak p_{D-1} is totally ramified, so for x∈KD−1x \in K_{D-1},

νpD(x)=2νpD−1(x).\nu_{\mathfrak p_D}(x)=2\nu_{\mathfrak p_{D-1}}(x).

The principal ideal generated by βD\beta_D is supported at pD\mathfrak{p}_D; hence the reduced βD\beta_D-denominator exponent of an element from the base field is even. This proves Theorem 5.1 independently of coefficient parity. Standard facts about cyclotomic ramification may be found in [16]; related denominator arithmetic is developed in the appendices of [3].

Dependency map

The proof dependencies are deliberately short:

dyadic midpoint theorem⇒program-state depth⇒injection upper bound,stabilizer arithmetic closure⇒field lower bound,Forest denominator pattern+even-denominator lemma⇒relative intersection,relative intersection⇒Fdepth=Adepth,field lower bound+injection upper bound⇒Rdepth=Fdepth,fixed-alphabet optimality⇒lexicographically optimal resource effect.\begin{aligned} &\text{dyadic midpoint theorem} \Rightarrow\text{program-state depth} \Rightarrow\text{injection upper bound},\\ &\text{stabilizer arithmetic closure} \Rightarrow\text{field lower bound},\\ &\text{Forest denominator pattern} + \text{even-denominator lemma} \Rightarrow\text{relative intersection},\\ &\text{relative intersection} \Rightarrow\mathrm{Fdepth} = \mathrm{Adepth},\\ &\text{field lower bound} + \text{injection upper bound} \Rightarrow\mathrm{Rdepth} = \mathrm{Fdepth},\\ &\text{fixed-alphabet optimality} \Rightarrow\text{lexicographically optimal resource effect}. \end{aligned}

This organization also marks the prior-art boundary: only the implications stated in the present paper depend on the new relative-descent argument; the fixed-alphabet synthesis theorem itself is imported from [3].

References

  1. [1]D.-A. German, A term-rewriting semantics for pure quantum states, arXiv:2607.06584, 2026.arxiv.org/abs/2607.06584
  2. [2]T. Newton and D.-A. German, Certified misty-state rewriting: A question-and-answer guide, arXiv:2608.10024, 2026.arxiv.org/abs/2608.10024
  3. [3]S. Forest, D. Gosset, V. Kliuchnikov, and D. McKinnon, Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets, Journal of Mathematical Physics 56, 082201 (2015), doi:10.1063/1.4927100; arXiv:1501.04944.DOI
  4. [4]E. T. Campbell and J. O’Gorman, An efficient magic state approach to small angle rotations, Quantum Science and Technology 1, 015007 (2016), arXiv:1603.04230.DOI
  5. [5]Y. Zheng, A. Zang, and A. Kubica, Magic gate teleportation: Structure, useful resource states, and simpler feedforward, arXiv:2607.08508, 2026.arxiv.org/abs/2607.08508
  6. [6]M. Beverland, E. Campbell, M. Howard, and V. Kliuchnikov, Lower bounds on the non-Clifford resources for quantum computations, Quantum Science and Technology 5, 035009 (2020), arXiv:1904.01124.DOI
  7. [7]N. de Silva and O. Lautsch, The Clifford hierarchy for one qubit or qudit, Proceedings of the Royal Society A 481, 20250035 (2025), arXiv:2501.07939.arxiv.org/abs/2501.07939
  8. [8]R. Vilmart, Rewriting and completeness of sum-over-paths in dyadic fragments of quantum computing, Logical Methods in Computer Science 20(1):20 (2024), arXiv:2307.14223.DOI
  9. [9]A. Sundaram, R. Rand, K. Singhal, and B. Lackey, A rich type system for quantum programs, arXiv:2101.08939, version 3, 2022.
  10. [10]A. Colledan, U. Dal Lago, and N. Vazou, Circuit width estimation via effect typing and linear dependency, ACM Transactions on Programming Languages and Systems 47(3), 2025, doi:10.1145/3737282.DOI
  11. [11]P. Selinger and B. Valiron, On a fully abstract model for a quantum linear functional language, Electronic Notes in Theoretical Computer Science 210, 123–137 (2008), doi:10.1016/j.entcs.2008.04.022.DOI
  12. [12]C. Radin and L. Sadun, Subgroups of SO(3) associated with tilings, Journal of Algebra 202, 611–633 (1998), arXiv:math/9601202.arxiv.org/abs/math/9601202
  13. [13]C. J. Ingalls, B. W. Jordan, A. Keeton, A. Logan, and Y. Zaytman, The Clifford-cyclotomic group and Euler–Poincaré characteristics, arXiv:1903.09497, 2019.arxiv.org/abs/1903.09497
  14. [14]M. Amy, A. N. Glaudell, S. Kelso, W. Maxwell, S. S. Mendelson, and N. J. Ross, Exact synthesis of multiqubit Clifford-cyclotomic circuits, arXiv:2311.07741, revised 2024.arxiv.org/abs/2311.07741
  15. [15]L. Dinh and N. J. Ross, Contributions to the theory of Clifford-cyclotomic circuits, Electronic Proceedings in Theoretical Computer Science 426, 231–246 (2025), arXiv:2508.14674.DOI
  16. [16]L. C. Washington, Introduction to Cyclotomic Fields, 2nd ed., Springer, 1997.

Paper details

vlnc:W_ubhfvt5s
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents