A Memory-Magic Exchange Law in Streaming Clifford+T Compilation
Abstract
A phase that reaches a fault-tolerant processor in additive pieces can be remembered until the last piece arrives, or executed on arrival: the first option costs classical memory carried across rounds, the second costs magic states committed before the phase is known. We determine the exchange rate α, committed T gates per bit of memory forgone, for ancilla-free coordinatewise Clifford+T compilation. The Ramanujan bound gives α≥2 with explicit constants, the square-root barrier of the spectral method. An elementary determinant method, using that quaternion numerators lie on spheres in both real embeddings of ℚ(√2), counts words near any rotation coset below that barrier. With a height dichotomy for the sphere sections it produces and a fibration over rational projections, it gives every α<5/2 unconditionally and uniformly over frames, by an exact SMT check of its continuum case analysis; 5/2 is where this method stops. At Clifford-framed cosets the volume law holds up to subexponential factors: all but a vanishing fraction of z-rotations need T-count (3−o(1))log2(1/ε), and processes whose committed pieces are near Clifford-framed z-rotations, including per-rotation pipelines, have α≥3−o(1), which a fractional-passthrough family attains under the Ross-Selinger typical-cost hypothesis. Under an equidistribution conjecture supported by exhaustive enumeration to T-count 22, α=3 in general and memory should be shed in whole rotations. The bounds hold even when the phases cancel to the identity; side information enters through a conditional entropy; probabilistic mixing halves the costs but not the rate. With clean ancillas and a phase-gradient catalyst, table lookups batched over coordinates drive the rate to O(1/loglog(1/ε)), so the constant-rate law is specific to coordinatewise synthesis.
Related
- DELUGE: Decomposed Entropy-coded Live Unstructured Geometry Exchange for Real-time Particle Streaming
- The Cost of Working Memory in Streaming Mean Estimation
- Streaming Hypergraph Coloring via Palette Sparsification
- Estimation and Inference for One-pass Streaming Function-on-Function Regression
- Bandit Process Inference for Streaming Functional Data
BibTeX
@misc{yang2026memorymagic,
title = {{A Memory-Magic Exchange Law in Streaming Clifford+T Compilation}},
author = {Jinze Yang and Yangyang Li and Xiu-Hao Deng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37368},
eprint = {2609.37368},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37368},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Memory-Magic Exchange Law in Streaming Clifford+T Compilation
AU - Jinze Yang
AU - Yangyang Li
AU - Xiu-Hao Deng
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.37368
UR - https://arxiv.org/abs/2609.37368
AB - A phase that reaches a fault-tolerant processor in additive pieces can be remembered until the last piece arrives, or executed on arrival: the first option costs classical memory carried across rounds, the second costs magic states committed before the phase is known. We determine the exchange rate α, committed T gates per bit of memory forgone, for ancilla-free coordinatewise Clifford+T compilation. The Ramanujan bound gives α≥2 with explicit constants, the square-root barrier of the spectral method. An elementary determinant method, using that quaternion numerators lie on spheres in both real embeddings of ℚ(√2), counts words near any rotation coset below that barrier. With a height dichotomy for the sphere sections it produces and a fibration over rational projections, it gives every α<5/2 unconditionally and uniformly over frames, by an exact SMT check of its continuum case analysis; 5/2 is where this method stops. At Clifford-framed cosets the volume law holds up to subexponential factors: all but a vanishing fraction of z-rotations need T-count (3−o(1))log_2(1/ε), and processes whose committed pieces are near Clifford-framed z-rotations, including per-rotation pipelines, have α≥3−o(1), which a fractional-passthrough family attains under the Ross-Selinger typical-cost hypothesis. Under an equidistribution conjecture supported by exhaustive enumeration to T-count 22, α=3 in general and memory should be shed in whole rotations. The bounds hold even when the phases cancel to the identity; side information enters through a conditional entropy; probabilistic mixing halves the costs but not the rate. With clean ancillas and a phase-gradient catalyst, table lookups batched over coordinates drive the rate to O(1/loglog(1/ε)), so the constant-rate law is specific to coordinatewise synthesis.
ER -