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

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

1. Problem Statement

Fault-tolerant quantum programming typically treats non-Clifford computation through two distinct lenses: exact synthesis (constructing circuits over a fixed gate alphabet like Clifford+T) and magic-state resource theories (consuming specific quantum states to inject non-Clifford gates). While these fields are often studied separately, there is a lack of a unified framework that assigns a single resource effect which is simultaneously:

1. A static property of the source syntax.
2. A lower bound on physical resources.
3. An exact predictor of the minimal gate alphabet required for compilation.

Specifically, for single-qubit programs within the dyadic Clifford-cyclotomic union (unitaries generated by Clifford gates and rotations $U_z(\pi/2^D)$), it is unclear how the arithmetic depth of the underlying number field relates to the minimal gate alphabet depth and the minimal depth of required resource states (program states). Furthermore, existing resource monotones (e.g., stabilizer nullity) often provide scalar lower bounds that do not capture the specific algebraic structure required for exact synthesis.

2. Methodology

The paper develops a unified resource semantics by integrating three distinct theoretical components:

• Dyadic Mist-State Semantics: The authors utilize a "normalized mist-state" formalism where program states are generated by repeated averaging (geodesic midpoints) of basis states. They establish that a primitive dyadic source state with coordinate $m/2^D$ has a minimum "normalized-midpoint depth" of $D$ and is Clifford-equivalent to the standard phase-program state for the rotation $U_z(m\pi/2^D)$.
• Stabilizer Arithmetic Closure: Instead of using scalar magic monotones, the authors introduce a field-theoretic invariant. They prove that finite adaptive stabilizer protocols (using Clifford unitaries, Pauli measurements, and classical feed-forward) are arithmetically closed over the number field generated by the Pauli expectation values of the input resource states. Consequently, such protocols cannot generate a channel whose Pauli transfer matrix entries lie outside the field generated by the resources.
• Relative Descent in Cyclotomic Towers: The core mathematical innovation is a relative intersection theorem. By combining the denominator-exponent canonical form (from Forest et al.) with a new "even-denominator lemma" for the real cyclotomic tower, the authors prove that within the dyadic synthesizable union, descending the arithmetic field depth is exactly equivalent to descending the gate-alphabet depth.

3. Key Contributions and Results

A. The Equality of Depths
The central result establishes the equality of three a priori distinct quantities for any non-Clifford channel $U$ in the dyadic Clifford-cyclotomic union:

1. Field Depth ($F_{depth}$): The smallest real cyclotomic field $K_D = \mathbb{Q}(2\cos(\pi/2^D))$ containing the Bloch matrix of $U$.
2. Alphabet Depth ($A_{depth}$): The smallest $D$ such that $U$ belongs to the projective group $\hat{G}_D$ generated by Clifford gates and $U_z(\pi/2^D)$.
3. Resource Depth ($R_{depth}$): The minimum depth $D$ of dyadic program states required to implement $U$ exactly via a finite adaptive stabilizer protocol.

The paper proves:
$$F_{depth}(U) = A_{depth}(U) = R_{depth}(U)$$

B. The Relative Intersection Theorem
The authors prove that for the nested dyadic tower $\hat{G}_D$ and associated fields $K_D$:
$$\hat{G}_D \cap SO(3, K_d) = \hat{G}_d \quad \text{for } 1 \le d \le D$$
This theorem demonstrates that if a unitary synthesizable at level $D$ has all its Bloch matrix entries in a shallower field $K_d$, it is necessarily synthesizable using only the shallower gate alphabet $\hat{G}_d$. This relies on a parity lemma showing that elements in the base field $K_{D-1}$ cannot have odd reduced denominator exponents in the generator $\beta_D$ of the extension $K_D$.

C. Lexicographically Optimal Resource Effect
Combining the depth equality with the fixed-alphabet optimal synthesis results of Forest et al., the paper defines an Exact Dyadic Resource Effect:
$$QEff(U) = (D^*, T_{2D^*}(U))$$
where $D^*$ is the common minimal depth and $T_{2D^*}(U)$ is the minimum number of primitive rotations required at that depth. This pair is lexicographically optimal: no exact implementation exists with a smaller depth $D$, and among those with depth $D^*$, none uses fewer primitive rotations.

D. Operational Obstruction
The paper proves that finite adaptive stabilizer processing cannot enlarge the field generated by resource-state Pauli expectations. Therefore, a finite collection of resource states from depths $d < D^*$ cannot exactly implement a target with depth $D^*$, regardless of the number of copies used. This provides an exact arithmetic obstruction to exact synthesis that is insensitive to the quantity of resources, only their algebraic depth.

4. Significance and Claims

The paper claims to provide a static resource effect that is exact, operational, and meaningful even for programs that fall outside the finite levels of the Clifford hierarchy (where gate-hierarchy membership is not compositional).

• Unification: It bridges the gap between arithmetic synthesis (number fields) and operational resource theories (program states), showing they are governed by the same invariant.
• Exactness: Unlike approximate synthesis bounds, this framework provides exact lower bounds for exact implementation.
• Compiler Optimization: The result enables a compilation pipeline where the minimal gate alphabet and resource depth are determined by computing the field depth of the Bloch matrix, eliminating the need to search through shallower gate alphabets.
• Scope Limitation: The authors explicitly state that this result is specific to single-qubit dyadic programs within a declared stabilizer-plus-dyadic-program-state model. They do not claim that field depth measures the "amount" of magic (in a scalar sense) or that these equalities hold for arbitrary multiqubit resources or approximate synthesis.

In summary, the paper establishes that for single-qubit dyadic programs, the arithmetic depth of the Bloch matrix is the precise determinant of both the minimal gate alphabet and the minimal resource state depth required for exact implementation, yielding a lexicographically optimal resource signature.