A Memory-Magic Exchange Law in Streaming Clifford+T Compilation

AI summary

Overview

• Research area: Quantum compilation and fault-tolerant quantum computing, specifically the resource trade-off between classical memory and magic-state consumption in Clifford+T circuit synthesis, analysed with tools from number theory (quaternion algebras, Hecke operators, Ramanujan bounds) and the geometry of numbers.
• Technical level: Advanced. The paper assumes familiarity with fault-tolerant quantum architectures, single-qubit Clifford+T synthesis, and analytic number theory (automorphic forms, equidistribution, lattice-point counting). The introductory framing is accessible; the results are not.
• Scope (one sentence): The paper proves that in streaming, ancilla-free, per-rotation Clifford+T compilation, classical memory bits and committed T gates are convertible at a problem-size-independent exchange rate, establishes rigorous lower bounds on that rate (2, then 11/5, then 17/7, then every rate below 5/2), matches it with an explicit construction reaching 3 under a synthesis hypothesis, and identifies the remaining gap as an arithmetic equidistribution question.

What This Paper Is About

When a rotation angle arrives at a fault-tolerant quantum processor split into pieces across several rounds, the compiler must either remember the earlier pieces in classical memory until the full angle is known, or synthesize each piece immediately and spend magic states before the total is known. The paper turns this informal trade-off into a theorem: it defines the committed magic (T gates executed before the last share arrives) and proves how many T gates must be paid per classical bit of memory that the compiler chooses not to hold. The goal is to determine the exact exchange rate, which the authors argue is a property of irreversible commitment rather than of the target unitary.

Key Contributions

1. A new equidistribution estimate for Clifford+T words near rotation cosets. Theorem 2 bounds the number of words of T-count ≤ k within projective distance ε of any coset G₁R_z(θ)G₂ by C₁2^kε² + C₂(k+1)2^{k/2}, with explicit constants C₁ ≤ 408 and C₂ ≤ 232. Its only external input is the Ramanujan bound of Lubotzky–Phillips–Sarnak and Parzanchevski–Sarnak.
2. An unconditional rate-two law. Theorem 3 converts that count into T_pre ≥ 2(r−1)(m log₂K − S − mA₂) up to O(δ) corrections, where A₂ = log₂C₂ + 2log₂(2log₂K) + O(1) bits per coordinate. This is stated as the natural threshold of the spectral method, not a geometric constant.
3. Bounds that break the square-root barrier of the spectral method. A determinant method with no automorphic input (Theorem 4) gives exponent 0.4513 for t ≤ (20/9)L, raising the floor to 11/5; a height dichotomy (Theorems 6–7) lowers the exponent to 0.4111 for t ≤ (17/7)(L+2), raising it to 17/7; fibring over rational planes and projections with an SMT-checked continuum case analysis (Theorem 8) gives every rate below 5/2.
4. An achievability construction and a conditional exact rate. Theorem 9 gives a fractional passthrough scheme attaining rate → 3 whenever the mean single-rotation synthesis cost is (3+o(1))L, as Ross–Selinger synthesis gives for typical angles. Theorem 10 shows that under Conjecture 1 (exponent β = 2, the codimension of a rotation coset in SU(2)) the rate is exactly 1+β = 3, and commitment is quantized.

Main Findings

• The rate is at least 2, unconditionally. Every bit of memory forgone costs at least two committed T gates once the first A₂ bits of each coordinate are given away. The paper contrasts this with the baseline rate of 1 that follows from the Matsumoto–Amano count (a single T gate carries at most log₂2 = 1 bit), showing the geometric confinement of the committed word to a tube around a coset is what raises it.
• The bound is not tight at 2. The 2^{k/2} remainder is a limit of the Hecke-operator method (Remark 2): it exceeds the main term for k < 4L + 2log₂(k+1) − 2log₂(C₁/C₂), which includes the whole range k ≤ 4L and in particular k ∈ [2L, 3L] where synthesized rotations live.
• Improved floors of 11/5 and 17/7 follow without any automorphic input. The determinant method bounds the tube by 2^{0.4513t + o(t)} for every coset and every t ≤ (20/9)L, and the height dichotomy lowers the exponent to 0.4111 for t ≤ (17/7)(L+2).
• Every rate below 5/2 is reached, and that is where the method stops. At 5/2 the boxes of the five-point determinant shrink to ε-cubes. A tube carrying words of T-count (5/2 + o(1))L with gaps of at most 2^{o(L)} grid steps along its core would make 5/2 sharp (Proposition 1).
• Rate 3 − o(1) holds unconditionally for rotation-segmented processes. At Clifford-framed cosets the volume law holds up to 2^{O(τ/log τ)} (Theorems 11–12, Corollary 4), so all but a vanishing fraction of z-rotations need T-count 3L − O(L/log L), and processes whose every committed segment is within ε of a Clifford-framed z-rotation achieve rate at least 3 − o(1).
• Explicit numbers at ε = 10⁻¹⁰. The rigorous floor is 0.78 committed T gates per bit against 3.20 achieved by passthrough at the certified share accuracy. The rate-two additive term A₂ is 20.0 bits out of the log₂K = 32.9 bits a coordinate carries, and the rate-two bound with explicit constants is the larger of the two only where fewer than 3.7 bits per coordinate are retained.
• Conditional exactness and quantization. Under Conjecture 1 the rate is exactly 1+β = 3, and a committed word carries at most O(log L) bits about its coordinate unless it costs at least 2L − O(1) gates: 7 bits at ε = 10⁻¹⁰ against the 33 a coordinate carries. The conjecture is supported by exhaustive enumeration to T-count 22 on Haar-random and arithmetic cosets, with exponents matching to three decimals and constants matching the Haar prediction to a few per cent.
• Commitment is independent of whether the phases cancel. Corollary 1 shows all the lower bounds hold conditionally on X = 0, where the target unitary is the identity; a universally correct process spends the same expected magic whether or not the aggregate vanishes.
• Side information enters as a conditional entropy. With a λ-bit seed independent of the aggregate, as in randomized compiling, the information a seedless compiler is missing is at most λ rather than mL (Theorem 13; Theorem 14 gives a one-shot smooth-entropy version).
• The law is specific to coordinatewise synthesis. With clean ancillas, a phase-gradient catalyst and table lookups batched across coordinates, the committed cost per share drops to O(L/log L) (Proposition 3), and with O(log log(1/ε)) coordinates batched the rate falls to O(1/log log(1/ε)).
• Probabilistic mixing halves the law but does not remove it. Under mixing, all but the top ½L + O(log L) bits of every share are free; the remaining bits are charged at the same rate, with asymptotic rigorous floor L committed T gates per share against ½L achievable under a synthesis hypothesis and ½L with fee L under the conjecture (Theorems 15, Corollary 7).
• Measurement adaptivity lowers the rate but not the order. On n qubits an Ω(L/n) floor holds for the sum of T gates plus measurements (Proposition 5).
• Scale of the trade. The paper notes that at m = 10⁴ coordinates and log₂K = 33 the entire aggregate snapshot is 41 kB, against the 10⁶ magic states on the other side of the trade.

Methodology in Plain English

The authors model compilation as a one-pass streaming process that reads shares of a phase round by round, may use unlimited RAM and randomness, and must produce a correct circuit with probability at least 1 − δ. They measure two quantities at each cut between rounds: the size of the snapshot the process carries forward, and the number of T gates already emitted. The argument is information-theoretic. Because the last round's share is determined once the aggregate and the earlier shares are fixed, the process must extract nearly m log₂K bits about each round's share; those bits can come only from the snapshot or from the gates already committed. Fano's inequality converts the correctness requirement into a lower bound on mutual information, and the snapshot's entropy is capped by its byte size. The only remaining question is how many bits a committed Clifford+T word can carry about its coordinate — and that is a counting problem.

For the counting, the authors exploit a classical identification: single-qubit Clifford+T gates modulo phase form a lattice in a quaternion algebra over ℚ(√2), T-count equals distance in a 3-regular tree, and the sphere of radius t has 3·2^{t−1} vertices, recovering the Matsumoto–Amano count 36·2^t. Words near a rotation coset correspond to lattice points near a curve of codimension two in the three-dimensional group. The authors first bound this tube by mapping it to a spherical cap via the Hopf fibration, majorizing the cap by a Poisson kernel, and applying Hecke operators whose size is controlled by the Ramanujan bound — this yields the 2^{k/2} error barrier. To get past that barrier they switch to an elementary determinant (Bombieri–Pila / Heath-Brown style) argument that uses only the fact that the numerators are lattice points on a sphere in both real embeddings, with no automorphic input, then refine it by sorting the sphere sections according to the height of their hyperplane and by fibring numerators over rational planes and their projections. The final case analysis is checked exactly on a continuum form by an SMT solver.

For the upper bounds, they construct an explicit fractional passthrough family and measure its synthesis cost on a grid, comparing against the Ross–Selinger cost for typical angles. A separate exhaustive enumeration to T-count 22 tests the equidistribution conjecture on Haar-random and arithmetic cosets.

Why This Matters

Impact on research. The paper converts an empirical observation from the authors' earlier work — that synthesizing shares on arrival costs roughly 3log₂(1/ε) T gates per rotation — into a theorem with explicit constants, and in doing so opens a two-way bridge between quantum compilation and the arithmetic of quaternion lattices. It also isolates a clean open problem in the geometry of numbers (closing the gap from 5/2 to 3), and shows that the constant-rate law is not universal: it disappears under batching, is halved under mixing, and weakens under measurement adaptivity, which delineates exactly which compilation architectures the law constrains.

Real-world applications (as framed by the paper):

• Real-time control stacks for fault-tolerant processors, where the stream is append-only and the scheduler emits with bounded lookahead, so any rotation not held must be committed; the paper prices lookahead depth and snapshot size as distinct resources.
• Randomized compiling, where shares are generated by agents other than the compiler; Theorem 13 quantifies the charge as at most λ bits for a λ-bit seed rather than mL.
• Trotter steps and layerwise parametrized ansätze, where the angle of a given rotation is naturally presented as a sum of shares delivered in different rounds.
• Phase-polynomial scheduling from a compiler, where the same decomposition into per-coordinate shares arises.
• Magic-state budget and factory sizing, since the committed magic T_pre is the number of magic states that must be available before the last share arrives.

Industry relevance. For any organisation building a fault-tolerant stack, the result gives a quantitative rule for deciding how much classical buffering to buy: at ε = 10⁻¹⁰, the rigorous floor is 0.78 committed T gates per bit and passthrough achieves 3.20, so memory is cheap relative to magic on a per-bit basis, while the batching result (O(L/log L) per share with ancillas and a phase-gradient catalyst) shows when the trade disappears entirely. The paper's remark on scale — 41 kB of classical snapshot against 10⁶ magic states — is a direct architectural statement about where the bottleneck lies.

Future Directions

• Closing the gap between 5/2 and 3. The authors explicitly frame this as an arithmetic question rather than a compilation one: proving Conjecture 1, whose exponent β = 2 is fixed by the codimension of a rotation coset in SU(2) and which carries a linear additive term forced by powers of infinite-order words (Proposition 2). Exhaustive enumeration currently reaches only T-count 22.
• Quantum-side angle generation. The proof applies Fano's inequality to a classical stream, so it does not reach qubitization, QROM-loaded phase tables, or adaptive QSVT phases, where no classical snapshot exists to trade away. The authors state this as the natural target for this line of work (Sec. XI).
• The quasi-probabilistic case, which the paper lists as open.
• Extending beyond coordinatewise synthesis. The constant-rate law is specific to the ancilla-free per-rotation model; characterising the law for batching, catalytic phase-gradient registers, and adaptive measurement schemes with more ancillas remains to be done beyond the specific bounds given.

Target Audience

• Quantum compilation and fault-tolerant architecture researchers who need provable resource trade-offs rather than empirical synthesis-cost estimates.
• Theoretical computer scientists working on quantum lower bounds, particularly those comfortable with information-theoretic arguments (Fano, smooth entropies) applied to streaming models.
• Number theorists interested in arithmetic lattices and equidistribution, for whom the tube-counting problem near rotation cosets and the 5/2 barrier are concrete geometric questions.
• Hardware and control-stack architects deciding how much classical memory and lookahead to provision against magic-state budgets.
• Graduate students in quantum information with a strong mathematical background who want an example of number theory directly determining a compilation cost.

Authors’ 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 $α\ge2$ 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 $\mathbb{Q}(\sqrt2)$, 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 $α&lt;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/\varepsilon)$, and processes whose committed pieces are near Clifford-framed $z$-rotations, including per-rotation pipelines, have $α\ge3-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/\log\log(1/\varepsilon))$, so the constant-rate law is specific to coordinatewise synthesis.