pith. machine review for the scientific record. sign in

arxiv: 2605.13929 · v1 · submitted 2026-05-13 · 💻 cs.PL · quant-ph

Recognition: no theorem link

Linear-Time T-Gate Optimization via Random Abstraction

Aws Albarghouthi
Authors on Pith no claims yet

Pith reviewed 2026-05-15 02:50 UTC · model grok-4.3

classification 💻 cs.PL quant-ph
keywords T-gate optimizationphase foldingquantum circuitsstatic analysisrandomized algorithmsfault-tolerant quantum computingT-count minimization
0
0 comments X

The pith

A linear-time randomized algorithm optimizes T gates by propagating constant-width bitstrings to approximate reachable quantum states.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a randomized static analysis for phase folding that runs in linear time. It approximates the set of reachable quantum states with arbitrarily high probability by propagating constant-width bitstrings down the circuit instead of tracking symbolic expressions. This approach addresses the central bottleneck of T-gate count in fault-tolerant quantum computing, where each T gate requires costly magic-state distillation. The resulting implementation scales to circuits with millions of gates while matching the T-count reductions of prior tools.

Core claim

We give a linear-time randomized algorithm for phase folding, based on a novel randomized static analysis. Our static analysis soundly approximates the set of reachable quantum states with an arbitrarily high probability. Our key insight is a static analysis that does not track symbolic expressions, but propagates constant-width bitstrings down the circuit.

What carries the argument

Randomized static analysis that propagates constant-width bitstrings down the circuit to approximate reachable quantum states for phase folding.

If this is right

  • T-count minimization becomes feasible for circuits with millions of gates on ordinary hardware.
  • Optimization time drops by multiple orders of magnitude relative to existing symbolic tools.
  • Phase folding can be integrated into compilation pipelines without becoming the dominant cost.
  • Large-scale fault-tolerant quantum algorithms can be resource-optimized before execution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same constant-width abstraction technique could be adapted to other quantum-circuit analyses that currently rely on expensive symbolic tracking.
  • Hybrid exact-randomized pipelines might further improve precision on critical subcircuits while retaining overall linear scaling.
  • The approach suggests a general template for lightweight static analyses in quantum compilers that trade bounded error for speed.

Load-bearing premise

Bitstring propagation soundly approximates the reachable quantum states with arbitrarily high probability for identifying foldable phases.

What would settle it

A concrete circuit instance where the randomized analysis produces a strictly higher T-count than an exact phase-folding method on the same input.

Figures

Figures reproduced from arXiv: 2605.13929 by Aws Albarghouthi.

Figure 1
Figure 1. Figure 1: Gate semantics as weighted input/output relations. Each gate [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Results on the Feynman benchmark suite. The circuits are sorted by total gate count. Missing bars [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: 𝑇 -count reduction and runtime on the Cobble benchmark suite. The circuits are sorted by total gate count. Missing bars indicate that the tool crashed or timed out (> 1 hour) on that circuit. For Feynman, this one-shot configuration is roughly 2× faster on average than the default compilation passes, with a negligible drop in 𝑇 -count reduction. The number of timeouts and the order-of-magnitude gap from tz… view at source ↗
Figure 4
Figure 4. Figure 4: Runtime of tzap on increasingly large circuits (log–log scale). Left: Hamiltonian simulation & matrix inversion. Right: Tower benchmarks (data structures). 7.2 RQ2: Scalability Summary. tzap scales linearly over four orders of magnitude in circuit size, matching the 𝑂(𝑛 +𝑚) analysis of § 6. It optimizes a 148 million-gate Cobble instance in under a minute and a ∼500 million-gate Tower instance in about two… view at source ↗
read the original abstract

Quantum computers promise exponential speedups for problems in cryptography, chemistry, and optimization. Realizing this promise requires fault tolerance: physical qubits are noisy, so logical qubits must be encoded redundantly across many physical ones using quantum error-correcting codes. In most practical fault-tolerance schemes, T gates cannot be implemented transversally and instead require costly magic-state distillation protocols involving a complex set of operations. As a result, T-gate count can dominate the resource budget of large-scale quantum computations, making T-count minimization a central bottleneck on the path to quantum advantage. Existing T-count optimization tools, however, do not scale to the circuits that quantum advantage demands. We present theoretical and practical results on T-gate optimization. On the theoretical side, we give a linear-time randomized algorithm for phase folding, based on a novel randomized static analysis. Our static analysis soundly approximates the set of reachable quantum states with an arbitrarily high probability. Our key insight is a static analysis that does not track symbolic expressions, but propagates constant-width bitstrings down the circuit. On the practical side, our implementation, TZAP, is multiple orders of magnitude faster than state-of-the-art tools -- such as PyZX, VOQC, and Feynman -- closely matches their T-count reductions on standard benchmarks, and within seconds on a laptop computer can optimize circuits with millions of gates.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims a linear-time randomized algorithm for phase folding in T-gate optimization, based on a novel randomized static analysis that propagates constant-width bitstrings to soundly approximate the set of reachable quantum states with arbitrarily high probability. The practical contribution is an implementation TZAP that is orders of magnitude faster than PyZX, VOQC, and Feynman while achieving comparable T-count reductions on benchmarks and scaling to million-gate circuits.

Significance. If the probabilistic soundness argument holds with fixed constant width and without super-linear overhead, the result would enable practical optimization of circuits at the scale required for quantum advantage demonstrations, addressing a key scalability bottleneck in fault-tolerant quantum compilation.

major comments (2)
  1. [Abstract and §3] Abstract and §3 (randomized static analysis): the claim that constant-width bitstring propagation yields arbitrarily high success probability must be accompanied by an explicit global failure-probability bound. If each gate has local success probability p < 1 bounded away from 1 by a constant depending only on width, then over m gates the overall success probability is at most p^m, which tends to zero for large m and contradicts the linear-time claim unless width or trials grow with m or 1/ε.
  2. [§4] §4 (algorithm description): the linear-time claim requires that the number of trials or the bitstring width remain independent of circuit size m and target ε. The manuscript must show either that the randomization is global (e.g., via a single random seed affecting all gates) or provide a concrete recurrence relating width, trials, m, and ε that preserves O(m) total work.
minor comments (2)
  1. [Figure 2] Figure 2 caption: the legend for the three compared tools is missing; add explicit labels for PyZX, VOQC, and TZAP.
  2. [§5.2] §5.2: the benchmark table reports wall-clock times but omits the number of random trials used per circuit; this datum is needed to verify the linear-time claim in practice.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the probabilistic analysis. We address the two major points below, clarifying that the randomization is global (a single seed for the entire circuit), which yields a failure probability depending only on width and independent of circuit size m.

read point-by-point responses

  1. Referee: [Abstract and §3] Abstract and §3 (randomized static analysis): the claim that constant-width bitstring propagation yields arbitrarily high success probability must be accompanied by an explicit global failure-probability bound. If each gate has local success probability p < 1 bounded away from 1 by a constant depending only on width, then over m gates the overall success probability is at most p^m, which tends to zero for large m and contradicts the linear-time claim unless width or trials grow with m or 1/ε.

    Authors: The bitstring abstraction uses a single global random seed chosen once at the beginning of the analysis; this defines a fixed random linear projection applied uniformly to all gates. The failure event is therefore global rather than per-gate, with probability at most 2^{-w} (or an analogous function of width w alone). This bound is independent of m, so constant w suffices for any target success probability. We will add the explicit global bound and its derivation to the revised abstract and §3. revision: yes

  2. Referee: [§4] §4 (algorithm description): the linear-time claim requires that the number of trials or the bitstring width remain independent of circuit size m and target ε. The manuscript must show either that the randomization is global (e.g., via a single random seed affecting all gates) or provide a concrete recurrence relating width, trials, m, and ε that preserves O(m) total work.

    Authors: As explained above, a single global seed is used. For any fixed target ε we select a constant width w = O(log(1/ε)) once; each of the m gates then performs O(1) work on the w-bit strings, for total O(m) time. No per-circuit trials or m-dependent growth in w is required. We will insert the corresponding recurrence and complexity argument into the revised §4. revision: yes

Circularity Check

0 steps flagged

No circularity detected in derivation chain

full rationale

The paper presents a linear-time randomized algorithm for phase folding via a static analysis that propagates constant-width bitstrings to approximate reachable states with arbitrarily high probability. This is described as a self-contained randomized procedure whose probabilistic soundness is asserted directly rather than derived from fitted parameters, self-referential definitions, or load-bearing self-citations. No equations or steps in the abstract or described approach reduce the claimed result to its inputs by construction. The skeptic concern addresses potential accumulation of failure probability (a correctness issue) but does not exhibit a definitional or self-citation reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on a domain assumption that constant-width bitstrings suffice for high-probability approximation of reachable states; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption Randomized propagation of constant-width bitstrings soundly approximates reachable quantum states with arbitrarily high probability
    This is the load-bearing premise stated in the abstract for the linear-time guarantee.

pith-pipeline@v0.9.0 · 5530 in / 1131 out tokens · 33000 ms · 2026-05-15T02:50:05.767028+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · 4 internal anchors

  1. [1]

    Matthew Amy. 2018. Towards Large-Scale Functional Verification of Universal Quantum Circuits. InProceedings of the 15th International Conference on Quantum Physics and Logic (QPL 2018) (Electronic Proceedings in Theoretical Computer Science, Vol. 287). 1–21. doi:10.4204/EPTCS.287.1

    work page doi:10.4204/eptcs.287.1 2018

  2. [2]

    Matthew Amy and Joseph Lunderville. 2025. Linear and non-linear relational analyses for quantum program optimization.Proceedings of the ACM on Programming Languages9, POPL, Article 37 (2025), 1072–1103 pages. doi:10.1145/3704873

    work page doi:10.1145/3704873 2025

  3. [3]

    Matthew Amy, Dmitri Maslov, and Michele Mosca. 2014. Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems33, 10 (2014), 1476–1489. doi:10.1109/TCAD.2014.2341953

    work page doi:10.1109/tcad.2014.2341953 2014

  4. [4]

    Matthew Amy and Michele Mosca. 2019. T-count optimization and Reed–Muller codes.IEEE Transactions on Information Theory65, 8 (2019), 4771–4784. doi:10.1109/TIT.2019.2906374

    work page doi:10.1109/tit.2019.2906374 2019

  5. [5]

    Benjamin Bichsel, Anouk Paradis, Maximilian Baader, and Martin Vechev. 2023. Abstraqt: Analysis of Quantum Circuits via Abstract Stabilizer Simulation.Quantum7 (2023), 1185. doi:10.22331/q-2023-11-20-1185

    work page doi:10.22331/q-2023-11-20-1185 2023

  6. [6]

    Sergey Bravyi and David Gosset. 2016. Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates.Physical Review Letters116 (2016), 250501. doi:10.1103/PhysRevLett.116.250501

    work page doi:10.1103/physrevlett.116.250501 2016

  7. [7]

    Sergey Bravyi and Jeongwan Haah. 2012. Magic-state distillation with low overhead.Physical Review A86, 5 (2012), 052329

    work page 2012

  8. [8]

    Sergey Bravyi and Alexei Kitaev. 2005. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A71, 2 (2005), 022316

    work page 2005

  9. [9]

    Bob Coecke and Ross Duncan. 2011. Interacting quantum observables: categorical algebra and diagrammatics.New Journal of Physics13, 4 (2011), 043016. doi:10.1088/1367-2630/13/4/043016

    work page doi:10.1088/1367-2630/13/4/043016 2011

  10. [10]

    Patrick Cousot and Radhia Cousot. 1977. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. InProceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. ACM, 238–252. doi:10.1145/512950.512973

    work page doi:10.1145/512950.512973 1977

  11. [11]

    Open Quantum Assembly Language

    Andrew W. Cross, Lev S. Bishop, John A. Smolin, and Jay M. Gambetta. 2017. Open Quantum Assembly Language. arXiv:1707.03429 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  12. [12]

    Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. 2020. Graph-theoretic simplification of quantum circuits with the ZX-calculus.Quantum4 (2020), 279. doi:10.22331/q-2020-06-04-279

    work page doi:10.22331/q-2020-06-04-279 2020

  13. [13]

    Fowler, Matteo Mariantoni, John M

    Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. 2012. Surface Codes: Towards Practical Large-Scale Quantum Computation.Physical Review A86, 3 (2012), 032324. doi:10.1103/PhysRevA.86.032324

    work page doi:10.1103/physreva.86.032324 2012

  14. [14]

    Craig Gidney, Noah Shutty, and Cody Jones. 2024. Magic state cultivation: growing T states as cheap as CNOT gates. arXiv:2409.17595 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  15. [15]

    Daniel Gottesman. 1999. The Heisenberg Representation of Quantum Computers. InGroup22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics. International Press, 32–43. arXiv:quant-ph/9807006

    work page internal anchor Pith review Pith/arXiv arXiv 1999

  16. [16]

    2005.Program Analysis using Random Interpretation

    Sumit Gulwani. 2005.Program Analysis using Random Interpretation. Ph. D. Dissertation. University of California, Berkeley

    work page 2005

  17. [17]

    Sumit Gulwani and George C. Necula. 2003. Discovering affine equalities using random interpretation. InProceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM, 74–84. doi:10. 1145/604131.604138 25

    work page arXiv 2003

  18. [18]

    Sumit Gulwani and George C. Necula. 2004. Global value numbering using random interpretation. InProceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM, 342–352. doi:10. 1145/964001.964030

    work page arXiv 2004

  19. [19]

    Sumit Gulwani and George C. Necula. 2005. Precise interprocedural analysis using random interpretation. InProceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM, 324–337. doi:10.1145/1040305.1040332

    work page doi:10.1145/1040305.1040332 2005

  20. [20]

    Luke E Heyfron and Earl T Campbell. 2019. An efficient quantum compiler that reduces T count.Quantum Science and Technology4, 1 (2019), 015004. doi:10.1088/2058-9565/aad604

    work page doi:10.1088/2058-9565/aad604 2019

  21. [21]

    Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. 2021. A verified optimizer for quantum circuits.Proceedings of the ACM on Programming Languages5, POPL, Article 37 (2021), 29 pages. doi:10.1145/3434318

    work page doi:10.1145/3434318 2021

  22. [22]

    James C King. 1976. Symbolic execution and program testing.Commun. ACM19, 7 (1976), 385–394. doi:10.1145/ 360248.360252

    work page arXiv 1976

  23. [23]

    Aleks Kissinger. 2021. QuiZX: A Rust port of PyZX. https://github.com/zxcalc/quizx

    work page 2021

  24. [24]

    Aleks Kissinger and John van de Wetering. 2020. PyZX: Large scale automated diagrammatic reasoning. InProceedings 16th International Conference on Quantum Physics and Logic (QPL 2019) (Electronic Proceedings in Theoretical Computer Science (EPTCS), Vol. 318). Open Publishing Association, 229–241. doi:10.4204/EPTCS.318.14

    work page doi:10.4204/eptcs.318.14 2020

  25. [25]

    Aleks Kissinger and John van de Wetering. 2020. Reducing the number of non-Clifford gates in quantum circuits. Physical Review A102, 2 (2020), 022406. doi:10.1103/PhysRevA.102.022406

    work page doi:10.1103/physreva.102.022406 2020

  26. [26]

    Ross, Yuan Su, Andrew M

    Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. 2018. Automated optimization of large quantum circuits with continuous parameters.npj Quantum Information4, 1 (2018), 23. doi:10.1038/s41534-018-0072-4

    work page doi:10.1038/s41534-018-0072-4 2018

  27. [27]

    Ross and Peter Selinger

    Neil J. Ross and Peter Selinger. 2016. Optimal ancilla-free Clifford+T approximation of z-rotations.Quantum Information & Computation16, 11&12 (2016), 901–953

    work page 2016

  28. [28]

    Peter Selinger. 2013. Quantum circuits of T-depth one.Physical Review A87, 4 (2013), 042302. doi:10.1103/PhysRevA. 87.042302

    work page doi:10.1103/physreva 2013

  29. [29]

    Koushik Sen, Darko Marinov, and Gul Agha. 2005. CUTE: a concolic unit testing engine for C. InProceedings of the 10th European Software Engineering Conference held jointly with the 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE ’05). ACM, 263–272. doi:10.1145/1081706.1081750

    work page doi:10.1145/1081706.1081750 2005

  30. [30]

    Peter W. Shor. 1994. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. InProceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 124–134. doi:10.1109/SFCS.1994.365700

    work page doi:10.1109/sfcs.1994.365700 1994

  31. [31]

    Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. 2021. t |ket⟩: a retargetable compiler for NISQ devices.Quantum Science and Technology6, 1 (2021), 014003. doi:10.1088/2058- 9565/ab8e92

    work page doi:10.1088/2058- 2021

  32. [32]

    John van de Wetering. 2020. ZX-calculus for the working quantum computer scientist.arXiv preprint arXiv:2012.13966 (2020)

    work page arXiv 2020

  33. [33]

    John van de Wetering and Matt Amy. 2024. Optimising Quantum Circuits is Generally Hard. arXiv:2310.05958 [quant- ph]

    work page arXiv 2024

  34. [34]

    Vivien Vandaele. 2025. Lower T-count with faster algorithms.Quantum9 (2025), 1860. arXiv:2407.08695 doi:10.22331/q- 2025-09-16-1860

    work page doi:10.22331/q- 2025

  35. [35]

    Amanda Xu, Abtin Molavi, Lauren Pick, Swamit Tannu, and Aws Albarghouthi. 2023. Synthesizing quantum-circuit optimizers.Proceedings of the ACM on Programming Languages7, PLDI, Article 140 (2023), 835–859 pages. doi:10.1145/ 3591254

    work page 2023

  36. [36]

    Amanda Xu, Abtin Molavi, Swamit Tannu, and Aws Albarghouthi. 2025. Optimizing Quantum Circuits, Fast and Slow. InProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Vol. 1. doi:10.1145/3669940.3707240

    work page doi:10.1145/3669940.3707240 2025

  37. [37]

    Acar, and Zhihao Jia

    Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar, and Zhihao Jia. 2022. Quartz: Superoptimization of Quantum Circuits. InProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI). ACM, 625–640. doi:10.1145/3519939.3523433

    work page doi:10.1145/3519939.3523433 2022

  38. [38]

    Ed Younis and Costin Iancu. 2022. Quantum Circuit Optimization and Transpilation via Parameterized Circuit Instantiation. In2022 IEEE International Conference on Quantum Computing and Engineering (QCE). 465–475. doi:10. 1109/QCE53715.2022.00068

    work page arXiv 2022

  39. [39]

    Nengkun Yu and Jens Palsberg. 2021. Quantum abstract interpretation. InProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI). ACM, 542–558. doi:10.1145/ 3453483.3454061

    work page arXiv 2021

  40. [40]

    Charles Yuan. 2024. Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra. arXiv:2511.01736 [quant-ph] 26

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  41. [41]

    Charles Yuan and Michael Carbin. 2022. Tower: Data Structures in Quantum Superposition.Proceedings of the ACM on Programming Languages6, OOPSLA2, Article 134 (2022). doi:10.1145/3563297

    work page doi:10.1145/3563297 2022

  42. [42]

    Charles Yuan and Michael Carbin. 2024. The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation.Proceedings of the ACM on Programming Languages8, PLDI (2024). doi:10.1145/3656397

    work page doi:10.1145/3656397 2024

  43. [43]

    1970.A new hashing method with application for game playing

    Albert L Zobrist. 1970.A new hashing method with application for game playing. Technical Report. University of Wisconsin-Madison. 27

    work page 1970