Memory magic trade off quantified in quantum gate compilation
A Memory-Magic Exchange Law in Streaming Clifford+T Compilation
Information Theory
Summary
This paper studies a trade-off in building quantum computers: you can either use memory to wait before executing certain quantum operations or commit special resources in advance without waiting. The authors find precise ratios describing how many special quantum gates (called T gates) you need to pay to save a bit of memory under certain compilation methods. Their mathematical analysis uses number theory and geometry to improve known bounds and suggests that saving memory by batching operations is best done in whole chunks. This gives insights on how to optimize resource use in fault-tolerant quantum computing.
What this means in practice
- •For quantum hardware engineers: Optimize use of memory and special quantum gates in error-corrected quantum processors by applying exact trade-offs from this work.
- •For quantum software developers: Design quantum compilers that balance memory usage and gate costs effectively by following the authors' rate bounds for Clifford+T circuit synthesis.
A theory result. No direct application yet.
Authors
Jinze Yang, Yangyang Li, Xiu-Hao Deng
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 for the Clifford+$T$ lattice gives $α\ge2$ with explicit constants, the square-root barrier of the spectral method. An elementary determinant method, using that quaternion numerators are lattice points on spheres in both real embeddings of $\mathbb{Q}(\sqrt2)$, counts words near an arbitrary rotation coset below that barrier and gives $α\ge11/5$ asymptotically and unconditionally, and a height dichotomy for the resulting sphere sections raises this to $α\ge17/7$. 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 close to 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 across coordinates drive the rate to $O(1/\log\log(1/\varepsilon))$, so the constant-rate law is specific to coordinatewise synthesis.