Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.37368

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

Jinze Yang, Yangyang Li, Xiu-Hao Deng

quant-phcs.ITmath.NTSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations
v1 · Sep 29, 2026v2 · Sep 30, 2026
arXivHTMLPDF

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.

Related papers

Representation-Dependent Recoverability in Quantum Compilation

Jinze Yang, Yangyang Li, Xiu-Hao Deng

Fault-tolerant compilation can disperse high-level structure: schedules split an accumulated phase across rounds, gate synthesis replaces an angle by a Clifford+$T$ word, and randomized compiling spreads rotations over sign-randomized fragments. They preserve the computation but change how cheaply a downstream compiler can recover the aggregate phase data. We formalize this representation-dependent recoverability by charging two channels: output committed before the suffix arrives, and a serialized restart state crossing the cut. For an $r$-round accumulation of a commuting layer with $m$ generators at accuracy $ε$ ($K_ε=Θ(1/ε)$), any $p$-pass compiler correct on every valid stream with failure probability at most $δ$ obeys $\overline{A}_p+(2p-1)S\geq(1-δ)m\log_2 K_ε-h_2(δ)$, where $\overline{A}_p$ is committed output and $S$ is the crossing-state cap. The bound covers compile-time randomized compiling; a memory-capped block compiler attains it within a constant factor, and direct semantic aggregation reaches compact output with logarithmic state. The two channels are not always interchangeable. A compiler whose committed prefix is executed at the cut pays a toll the state channel never pays: the entropy $\log_2\binom{m}{k}$ of the mask naming which $k$ coordinates it commits early. Compilers that defer or buffer pay none of it. We prove both directions and, with instrumented compilers under a preregistered protocol, measure a per-generator toll matching $\log_2\binom{m}{k}/k$ that vanishes for a public mask and a buffered control. Under a disclosed fixed-total-error Clifford+$T$ and surface-code model, a materialize-first pipeline costs orders of magnitude more logical $T$ states and spacetime volume than a semantic-first one. Phase semantics should therefore be preserved until aggregation whenever the interface permits.

quant-pharXiv:2609.29210•Sep 25, 2026•0 citations

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

For the standard Clifford+$T$ gate set, deterministic, ancilla-free synthesis now attains the minimal $T$-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The $\sqrt{T}$ gate rotates by half the angle of $T$, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+$\sqrt{T}$ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations

Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians

Jiaxin Ma, Kevin J. Joven, Yuan Liu

We determine the non-Clifford $T$-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an $n$-qubit operator with $a$ clean ancillas and at most $s$ $T$ gates can be compressed to use at most $\min\{a,n+2s\}$ ancillas, without increasing the absolute error or $T$-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error $ε$, a volume-covering argument combined with circuit counting gives the worst-case lower bound $Ω(n^2\sqrt{\log(n^4/ε)})$, matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on $n$ spins, we obtain independent lower bounds $Ω(n)$ from stabilizer nullity and $Ω(\log(1/ε))$ from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling $Θ(n+\log(1/ε))$. As an application, we evaluate the $T$-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation $T$-count scales as the query count times the optimal $T$-count per query.

quant-pharXiv:2609.11153•Sep 11, 2026•0 citations

More efficient Clifford+T synthesis for small-angle rotations and application to Trotterization

Marius Bothe, Christoph Sünderhauf, Michael J. Witham +2 more

Clifford+T synthesis of rotation gates is an important routine in fault-tolerant quantum compilation. While Clifford+T synthesis is scalable, it has a high overhead of tens of T gates per rotation in practice, translating to high resource estimates for many fault-tolerant algorithms. However, these well-known results, including those using probabilistic mixtures [Quantum 7, 1208 (2023)], are independent of the rotation angle $θ$, requiring $O(\log 1/δ)$ T gates. We show that it is possible to do much better for small angles, reducing the T cost to $\tilde{O}(θ^2/δ)$, and returning to existing $O(\log1/δ)$ results in the worst case. This is particularly important since many algorithms, such as Trotterization, are dominated by small-angle rotations. Further, we perform a detailed theoretical and numerical study of quasi-probabilities, which can further reduce the total T cost of large circuits by orders of magnitude with only a small overhead in sample complexity. We also develop a scheme based on quasi-probability mixtures of Clifford+T fallback channels. We derive new $θ$-dependent formulas that can be used for resource estimation of fault-tolerant quantum algorithms. As an application of our results, we show that the gate cost of Trotterization circuits compiled to a Clifford+T gate set is constant in the small Trotter step size limit, and can be reduced by orders of magnitude even for large step sizes. The cost of fault-tolerant Trotterization for a variety of applications should be re-examined in light of these results. Our work dispels the widely-stated claim that Clifford+T rotation synthesis has a high cost independent of $θ$, and further develops a scalable quasi-probability method for rotation synthesis. We also expect our results to bring forward useful early fault-tolerant quantum computing by reducing required magic state resources.

quant-pharXiv:2605.31544•Jun 1, 2026•0 citations

Typical-Case Gate Approximation and Arithmetic Obstructions in Quaternionic Single-Qubit Compilation

Kingsley Yeon, Steven B. Damelin, Greene, Alec

Fault-tolerant quantum computation requires compiling arbitrary one-qubit unitaries into short words over a fixed gate library. For arithmetic libraries such as the $p=5$ Lubotzky--Phillips--Sarnak, or Clifford$+V$, gate set, this problem is governed by quaternionic lattice points on $S^3\cong \SU(2)$. We study the complete norm shells \[ P_k=\{x/5^k\in S^3:x\in\ZZ^4,\ |x|^2=5^{2k}\} \] and the associated projective gate set $T\subset PSU(2)$. The main worst-case quantity is Sarnak's covering exponent $K(T)$, for which the classical range is $4/3\le K(T)\le2$. We show that any positive localized cap-kernel certificate using only the Deligne--LPS square-root spectral estimate reaches only the volume-squared threshold $|V_T(t)|\gg μ(B(\varepsilon))^{-2}$, hence only exponent $2$. Thus any unconditional improvement requires arithmetic cancellation in localized off-diagonal counting. We also record the conditional benchmark that twisted Linnik gives $K(T)=4/3$, matching Harman's obstruction. We prove the shell-to-gate implication $ρ(P_k)\le C5^{-αk}\Rightarrow K(T)\le4/(3α)$, so $α>2/3$ is exactly the threshold for improving the unconditional bound. Finally, exact enumeration of $P_1,P_2,P_3,P_4$ and Haar-random tests show median trace-defect error at the optimal $N^{-2/3}$ scale, while high quantiles remain separated. This gives a sharp distinction between strong typical-case performance and rare arithmetic holes controlling worst-case synthesis.

arXiv:1506.05785•Jun 18, 2015•0 citations

Exact TTT-counts of CCZ layers from an isotropy bound

Arul Rhik Mazumder

The $T$-count is a dominant cost of fault-tolerant Clifford$+T$ computation. We prove that every Hadamard-free Clifford$+T$ circuit with clean ancillas for a layer of $m$ disjoint CCZ gates, the diagonal core of a parallel Toffoli layer, uses at least $6m+1$ $T$ gates. Campbell and Howard gave a circuit with $6m+1$, and to our knowledge this is the first proof that it is optimal for general $m$. The proof combines Campbell and Howard's self-orthogonality of the columns of the parity matrix with a rank (flattening) bound, sharpened by one. More generally, the argument gives a lower bound on the $T$-count of every diagonal gate in the third level of the Clifford hierarchy, the isotropy floor, computable by Gaussian elimination. It is never below the stabilizer nullity $ν$ and reaches $2ν+1$ on non-Clifford gates whose phase is purely cubic. No bound that also holds for circuits with measurement and feedforward can do this, since such circuits implement CCZ ($ν=3$) with four $T$ gates and the layer with $4m$, where the floor gives seven and $6m+1$. The floor also recovers Campbell and Howard's count $4m+3$ for a fan-out of Toffolis. On the output of PyZX's TODD-based optimizer, relative to its Hadamard placement, it certifies $193$ of $311$ phase-polynomial blocks $T$-optimal once repeated parities are merged (at the best of five optimizer seeds), against $113$ for nullity, including $37$ of the $72$ blocks too large for exhaustive search.

quant-pharXiv:2610.01024•Oct 2, 2026•0 citations
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 TTT gates per bit of memory forgone, for ancilla-free coordinatewise Clifford+TTT compilation. The Ramanujan bound for the Clifford+TTT lattice gives α≥2α\ge2α≥2 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 Q(2)\mathbb{Q}(\sqrt2)Q(2​), counts words near an arbitrary rotation coset below that barrier and gives α≥11/5α\ge11/5α≥11/5 asymptotically and unconditionally, and a height dichotomy for the resulting sphere sections raises this to α≥17/7α\ge17/7α≥17/7. At Clifford-framed cosets the volume law holds up to subexponential factors: all but a vanishing fraction of zzz-rotations need TTT-count (3−o(1))log⁡2(1/ε)(3-o(1))\log_2(1/\varepsilon)(3−o(1))log2​(1/ε), and processes whose committed pieces are close to Clifford-framed zzz-rotations, including per-rotation pipelines, have α≥3−o(1)α\ge3-o(1)α≥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 TTT-count 22, α=3α=3α=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/ε))O(1/\log\log(1/\varepsilon))O(1/loglog(1/ε)), so the constant-rate law is specific to coordinatewise synthesis.
Fault-tolerant compilation can disperse high-level structure: schedules split an accumulated phase across rounds, gate synthesis replaces an angle by a Clifford+TTT word, and randomized compiling spreads rotations over sign-randomized fragments. They preserve the computation but change how cheaply a downstream compiler can recover the aggregate phase data. We formalize this representation-dependent recoverability by charging two channels: output committed before the suffix arrives, and a serialized restart state crossing the cut. For an rrr-round accumulation of a commuting layer with mmm generators at accuracy εεε (Kε=Θ(1/ε)K_ε=Θ(1/ε)Kε​=Θ(1/ε)), any ppp-pass compiler correct on every valid stream with failure probability at most δδδ obeys A‾p+(2p−1)S≥(1−δ)mlog⁡2Kε−h2(δ)\overline{A}_p+(2p-1)S\geq(1-δ)m\log_2 K_ε-h_2(δ)Ap​+(2p−1)S≥(1−δ)mlog2​Kε​−h2​(δ), where A‾p\overline{A}_pAp​ is committed output and SSS is the crossing-state cap. The bound covers compile-time randomized compiling; a memory-capped block compiler attains it within a constant factor, and direct semantic aggregation reaches compact output with logarithmic state. The two channels are not always interchangeable. A compiler whose committed prefix is executed at the cut pays a toll the state channel never pays: the entropy log⁡2(mk)\log_2\binom{m}{k}log2​(km​) of the mask naming which kkk coordinates it commits early. Compilers that defer or buffer pay none of it. We prove both directions and, with instrumented compilers under a preregistered protocol, measure a per-generator toll matching log⁡2(mk)/k\log_2\binom{m}{k}/klog2​(km​)/k that vanishes for a public mask and a buffered control. Under a disclosed fixed-total-error Clifford+TTT and surface-code model, a materialize-first pipeline costs orders of magnitude more logical TTT states and spacetime volume than a semantic-first one. Phase semantics should therefore be preserved until aggregation whenever the interface permits.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T\sqrt{T}T​ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.
We determine the non-Clifford TTT-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T+T+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an nnn-qubit operator with aaa clean ancillas and at most sss TTT gates can be compressed to use at most min⁡{a,n+2s}\min\{a,n+2s\}min{a,n+2s} ancillas, without increasing the absolute error or TTT-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error εεε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log⁡(n4/ε))Ω(n^2\sqrt{\log(n^4/ε)})Ω(n2log(n4/ε)​), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on nnn spins, we obtain independent lower bounds Ω(n)Ω(n)Ω(n) from stabilizer nullity and Ω(log⁡(1/ε))Ω(\log(1/ε))Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log⁡(1/ε))Θ(n+\log(1/ε))Θ(n+log(1/ε)). As an application, we evaluate the TTT-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation TTT-count scales as the query count times the optimal TTT-count per query.
Clifford+T synthesis of rotation gates is an important routine in fault-tolerant quantum compilation. While Clifford+T synthesis is scalable, it has a high overhead of tens of T gates per rotation in practice, translating to high resource estimates for many fault-tolerant algorithms. However, these well-known results, including those using probabilistic mixtures [Quantum 7, 1208 (2023)], are independent of the rotation angle θθθ, requiring O(log⁡1/δ)O(\log 1/δ)O(log1/δ) T gates. We show that it is possible to do much better for small angles, reducing the T cost to O~(θ2/δ)\tilde{O}(θ^2/δ)O~(θ2/δ), and returning to existing O(log⁡1/δ)O(\log1/δ)O(log1/δ) results in the worst case. This is particularly important since many algorithms, such as Trotterization, are dominated by small-angle rotations. Further, we perform a detailed theoretical and numerical study of quasi-probabilities, which can further reduce the total T cost of large circuits by orders of magnitude with only a small overhead in sample complexity. We also develop a scheme based on quasi-probability mixtures of Clifford+T fallback channels. We derive new θθθ-dependent formulas that can be used for resource estimation of fault-tolerant quantum algorithms. As an application of our results, we show that the gate cost of Trotterization circuits compiled to a Clifford+T gate set is constant in the small Trotter step size limit, and can be reduced by orders of magnitude even for large step sizes. The cost of fault-tolerant Trotterization for a variety of applications should be re-examined in light of these results. Our work dispels the widely-stated claim that Clifford+T rotation synthesis has a high cost independent of θθθ, and further develops a scalable quasi-probability method for rotation synthesis. We also expect our results to bring forward useful early fault-tolerant quantum computing by reducing required magic state resources.
Fault-tolerant quantum computation requires compiling arbitrary one-qubit unitaries into short words over a fixed gate library. For arithmetic libraries such as the p=5p=5p=5 Lubotzky--Phillips--Sarnak, or Clifford+V+V+V, gate set, this problem is governed by quaternionic lattice points on $S^3\cong \SU(2)$. We study the complete norm shells \[ P_k=\{x/5^k\in S^3:x\in\ZZ^4,\ |x|^2=5^{2k}\} \] and the associated projective gate set T⊂PSU(2)T\subset PSU(2)T⊂PSU(2). The main worst-case quantity is Sarnak's covering exponent K(T)K(T)K(T), for which the classical range is 4/3≤K(T)≤24/3\le K(T)\le24/3≤K(T)≤2. We show that any positive localized cap-kernel certificate using only the Deligne--LPS square-root spectral estimate reaches only the volume-squared threshold ∣VT(t)∣≫μ(B(ε))−2|V_T(t)|\gg μ(B(\varepsilon))^{-2}∣VT​(t)∣≫μ(B(ε))−2, hence only exponent 222. Thus any unconditional improvement requires arithmetic cancellation in localized off-diagonal counting. We also record the conditional benchmark that twisted Linnik gives K(T)=4/3K(T)=4/3K(T)=4/3, matching Harman's obstruction. We prove the shell-to-gate implication ρ(Pk)≤C5−αk⇒K(T)≤4/(3α)ρ(P_k)\le C5^{-αk}\Rightarrow K(T)\le4/(3α)ρ(Pk​)≤C5−αk⇒K(T)≤4/(3α), so α>2/3α>2/3α>2/3 is exactly the threshold for improving the unconditional bound. Finally, exact enumeration of P1,P2,P3,P4P_1,P_2,P_3,P_4P1​,P2​,P3​,P4​ and Haar-random tests show median trace-defect error at the optimal N−2/3N^{-2/3}N−2/3 scale, while high quantiles remain separated. This gives a sharp distinction between strong typical-case performance and rare arithmetic holes controlling worst-case synthesis.
The TTT-count is a dominant cost of fault-tolerant Clifford+T+T+T computation. We prove that every Hadamard-free Clifford+T+T+T circuit with clean ancillas for a layer of mmm disjoint CCZ gates, the diagonal core of a parallel Toffoli layer, uses at least 6m+16m+16m+1 TTT gates. Campbell and Howard gave a circuit with 6m+16m+16m+1, and to our knowledge this is the first proof that it is optimal for general mmm. The proof combines Campbell and Howard's self-orthogonality of the columns of the parity matrix with a rank (flattening) bound, sharpened by one. More generally, the argument gives a lower bound on the TTT-count of every diagonal gate in the third level of the Clifford hierarchy, the isotropy floor, computable by Gaussian elimination. It is never below the stabilizer nullity ννν and reaches 2ν+12ν+12ν+1 on non-Clifford gates whose phase is purely cubic. No bound that also holds for circuits with measurement and feedforward can do this, since such circuits implement CCZ (ν=3ν=3ν=3) with four TTT gates and the layer with 4m4m4m, where the floor gives seven and 6m+16m+16m+1. The floor also recovers Campbell and Howard's count 4m+34m+34m+3 for a fan-out of Toffolis. On the output of PyZX's TODD-based optimizer, relative to its Hadamard placement, it certifies 193193193 of 311311311 phase-polynomial blocks TTT-optimal once repeated parities are merged (at the best of five optimizer seeds), against 113113113 for nullity, including 373737 of the 727272 blocks too large for exhaustive search.