Lower T-count with faster algorithms

Vivien Vandaele

doi:10.22331/q-2025-09-16-1860

Lower T-count with faster algorithms

Vivien Vandaele

Eviden Quantum Lab, Les Clayes-sous-Bois, France
Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Published:	2025-09-16, volume 9, page 1860
Editor:	John van de Wetering
Eprint:	arXiv:2407.08695v2
Doi:	https://doi.org/10.22331/q-2025-09-16-1860
Citation:	Quantum 9, 1860 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Among the cost metrics characterizing a quantum circuit, the $T$-count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the $T$-count reduction problem by proposing efficient $T$-count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of $T$ gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated. We also prove that the number of $T$ gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of $n$ qubits is upper bounded by $n(n + 1)/2 + 1$, which improves on the worst-case $T$-count of existing optimization algorithms. From this we derive an upper bound of $(n + 1)(n + 2h)/2 + 1$ for the number of $T$ gates in a Clifford$+T$ circuit where $h$ is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last $T$ gate of the circuit.

► BibTeX data

@article{Vandaele2025lowertcountfaster,
  doi = {10.22331/q-2025-09-16-1860},
  url = {https://doi.org/10.22331/q-2025-09-16-1860},
  title = {Lower {T}-count with faster algorithms},
  author = {Vandaele, Vivien},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1860},
  month = sep,
  year = {2025}
}

► References

[1] Robert Raussendorf, Jim Harrington, and Kovid Goyal. ``Topological fault-tolerance in cluster state quantum computation''. New Journal of Physics 9, 199 (2007).
https://doi.org/10.1088/1367-2630/9/6/199

[2] Austin G Fowler, Ashley M Stephens, and Peter Groszkowski. ``High-threshold universal quantum computation on the surface code''. Physical Review A 80, 052312 (2009).
https://doi.org/10.1103/physreva.80.052312

[3] Michael E Beverland, Aleksander Kubica, and Krysta M Svore. ``Cost of universality: A comparative study of the overhead of state distillation and code switching with color codes''. PRX Quantum 2, 020341 (2021).
https://doi.org/10.1103/prxquantum.2.020341

[4] Austin G. Fowler. ``Time-optimal quantum computation'' (2013). arXiv:1210.4626.
arXiv:1210.4626

[5] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. ``A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 818–830 (2013).
https://doi.org/10.1109/tcad.2013.2244643

[6] Peter Selinger. ``Quantum circuits of T-depth one''. Physical Review A 87, 042302 (2013).
https://doi.org/10.1103/PhysRevA.87.042302

[7] Matthew Amy, Dmitri Maslov, and Michele Mosca. ``Polynomial-time T-depth optimization of Clifford+ T circuits via matroid partitioning''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476–1489 (2014).
https://doi.org/10.1109/tcad.2014.2341953

[8] Nabila Abdessaied, Mathias Soeken, and Rolf Drechsler. ``Quantum circuit optimization by Hadamard gate reduction''. In Reversible Computation: 6th International Conference, RC 2014, Kyoto, Japan, July 10-11, 2014. Proceedings 6. Pages 149–162. Springer (2014).

[9] Philipp Niemann, Anshu Gupta, and Rolf Drechsler. ``T-depth optimization for fault-tolerant quantum circuits''. In 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL). Pages 108–113. IEEE (2019).
https://doi.org/10.1109/ismvl.2019.00027

[10] Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay. ``A (quasi-) polynomial time heuristic algorithm for synthesizing T-depth optimal circuits''. npj Quantum Information 8, 110 (2022).
https://doi.org/10.1038/s41534-022-00624-1

[11] Sergey Bravyi and Alexei Kitaev. ``Universal quantum computation with ideal Clifford gates and noisy ancillas''. Physical Review A 71, 022316 (2005).
https://doi.org/10.1103/physreva.71.022316

[12] Matthew Amy and Vlad Gheorghiu. ``staq—A full-stack quantum processing toolkit''. Quantum Science and Technology 5, 034016 (2020).
https://doi.org/10.1088/2058-9565/ab9359

[13] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. ``t$\vert$ket$\rangle$: a retargetable compiler for NISQ devices''. Quantum Science and Technology 6, 014003 (2020).
https://doi.org/10.1088/2058-9565/ab8e92

[14] Simon Martiel and Timothée Goubault de Brugière. ``Architecture aware compilation of quantum circuits via lazy synthesis''. Quantum 6, 729 (2022).
https://doi.org/10.22331/q-2022-06-07-729

[15] Daniel Gottesman. ``The Heisenberg representation of quantum computers'' (1998). arXiv:quant-ph/9807006.
arXiv:quant-ph/9807006

[16] Sergey Bravyi and David Gosset. ``Improved classical simulation of quantum circuits dominated by Clifford gates''. Physical review letters 116, 250501 (2016).
https://doi.org/10.1103/physrevlett.116.250501

[17] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. ``Simulation of quantum circuits by low-rank stabilizer decompositions''. Quantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181

[18] Hammam Qassim, Hakop Pashayan, and David Gosset. ``Improved upper bounds on the stabilizer rank of magic states''. Quantum 5, 606 (2021).
https://doi.org/10.22331/q-2021-12-20-606

[19] Aleks Kissinger and John van de Wetering. ``Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions''. Quantum Science and Technology (2022).
https://doi.org/10.1088/2058-9565/ac5d20

[20] Aleks Kissinger, John van de Wetering, and Renaud Vilmart. ``Classical simulation of quantum circuits with partial and graphical stabiliser decompositions''. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). (2022).

[21] A. Kitaev, A. Shen, and M. Vyalyi. ``Correspondence between classical and quantum computation''. Page 60–65. American Mathematical Society. (2002).
https://doi.org/10.1090/gsm/047/10

[22] CM Dawson and MA Nielsen. ``The Solovay-Kitaev algorithm''. Quantum Information and Computation 6, 81–95 (2006).
https://doi.org/10.26421/qic6.1-6

[23] Peter Selinger. ``Efficient Clifford+T approximation of single-qubit operators''. Quantum Information & Computation 15, 159–180 (2015).
https://doi.org/10.26421/qic15.1-2-10

[24] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. ``Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits''. Physical review letters 110, 190502 (2013).
https://doi.org/10.1103/physrevlett.110.190502

[25] Neil J. Ross and Peter Selinger. ``Optimal ancilla-free Clifford+T approximation of z-rotations''. Quantum Information and Computation 16, 901–953 (2016).
https://doi.org/10.26421/qic16.11-12-1

[26] Alex Bocharov, Martin Roetteler, and Krysta M Svore. ``Efficient synthesis of probabilistic quantum circuits with fallback''. Physical Review A 91, 052317 (2015).
https://doi.org/10.1103/physreva.91.052317

[27] Matthew B. Hastings. ``Turning gate synthesis errors into incoherent errors''. Quantum Information and Computation 17, 488–494 (2017).
https://doi.org/10.26421/qic17.5-6-7

[28] Earl Campbell. ``Shorter gate sequences for quantum computing by mixing unitaries''. Physical Review A 95, 042306 (2017).
https://doi.org/10.1103/physreva.95.042306

[29] Vadym Kliuchnikov, Kristin Lauter, Romy Minko, Adam Paetznick, and Christophe Petit. ``Shorter quantum circuits via single-qubit gate approximation''. Quantum 7, 1208 (2023).
https://doi.org/10.22331/q-2023-12-18-1208

[30] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. ``Fast and efficient exact synthesis of single-qubit unitaries generated by clifford and T gates''. Quantum Information & Computation 13, 607–630 (2013).
https://doi.org/10.26421/qic13.7-8-4

[31] Matthew Amy and Michele Mosca. ``T-Count Optimization and Reed–Muller Codes''. IEEE Transactions on Information Theory 65, 4771–4784 (2019).
https://doi.org/10.1109/tit.2019.2906374

[32] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. ``Techniques to Reduce $\pi/4$-Parity-Phase Circuits, Motivated by the ZX Calculus''. Electronic Proceedings in Theoretical Computer Science 318, 131–149 (2020).
https://doi.org/10.4204/eptcs.318.9

[33] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. ``Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities''. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Volume 158, pages 11:1–11:23. (2020).
https://doi.org/10.4230/LIPIcs.TQC.2020.11

[34] Anthony Munson, Bob Coecke, and Quanlong Wang. ``AND-gates in ZX-calculus: spider nest identities and QBC-completeness''. Electronic Proceedings in Theoretical Computer Science 340, 230–255 (2021).
https://doi.org/10.4204/eptcs.340.12

[35] Witalis Domitrz. ``On the Verge to Improve Technique of T-count Reduction via Spider Nest Identities''. Master's thesis. University of Oxford. (2021).

[36] Luke E Heyfron and Earl T Campbell. ``An efficient quantum compiler that reduces T count''. Quantum Science and Technology 4, 015004 (2018).
https://doi.org/10.1088/2058-9565/aad604

[37] David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo. ``An algorithm for the T-count''. Quantum Information & Computation 14, 1261–1276 (2014).
https://doi.org/10.26421/qic14.15-16-1

[38] Daniel Litinski. ``A game of surface codes: Large-scale quantum computing with lattice surgery''. Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128

[39] Ewout Van Den Berg and Kristan Temme. ``Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters''. Quantum 4, 322 (2020).
https://doi.org/10.22331/q-2020-09-12-322

[40] Michael J Bremner, Richard Jozsa, and Dan J Shepherd. ``Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459–472 (2011).
https://doi.org/10.1098/rspa.2010.0301

[41] Vivien Vandaele, Simon Martiel, Simon Perdrix, and Christophe Vuillot. ``Optimal Hadamard gate count for Clifford+ T synthesis of Pauli rotations sequences''. ACM Transactions on Quantum Computing 5, 1–29 (2024).
https://doi.org/10.1145/3639062

[42] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Physical Review A 70, 052328 (2004).
https://doi.org/10.1103/physreva.70.052328

[43] Earl T Campbell and Mark Howard. ``Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost''. Physical Review A 95, 022316 (2017).
https://doi.org/10.1103/physreva.95.022316

[44] Daniel Gottesman and Isaac L Chuang. ``Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations''. Nature 402, 390–393 (1999).
https://doi.org/10.1038/46503

[45] Christopher M Dawson, Henry L Haselgrove, Andrew P Hines, Duncan Mortimer, Michael A Nielsen, and Tobias J Osborne. ``Quantum computing and polynomial equations over $Z_2$''. Quantum Information and Computation 5, 102–112 (2005).
https://doi.org/10.26421/qic5.2-2

[46] Ashley Montanaro. ``Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$''. Journal of Physics A: Mathematical and Theoretical 50, 084002 (2017).
https://doi.org/10.1088/1751-8121/aa565f

[47] Gadiel Seroussi and Abraham Lempel. ``Maximum likelihood decoding of certain Reed-Muller codes''. IEEE Transactions on Information Theory 29, 448–450 (1983).
https://doi.org/10.1109/tit.1983.1056662

[48] Johan Håstad. ``Tensor rank is NP-complete''. Journal of Algorithms 11, 644–654 (1990).
https://doi.org/10.1016/0196-6774(90)90014-6

[49] John van de Wetering and Matt Amy. ``Optimising T-count is NP-hard'' (2023). arXiv:2310.05958.
arXiv:2310.05958

[50] Matthew Amy. ``Feynman''. https://github.com/meamy/feynman.
https://github.com/meamy/feynman

[51] Dmitri Maslov. ``Reversible Logic Synthesis Benchmarks page''. http://webhome.cs.uvic.ca/ dmaslov. Accessed February 2023.
http://webhome.cs.uvic.ca/~dmaslov

[52] Kyungbae Jang, Anubhab Baksi, Jakub Breier, Hwajeong Seo, and Anupam Chattopadhyay. ``Quantum Implementation and Analysis of DEFAULT''. Cryptology ePrint Archive, Paper 2022/647 (2022). https://eprint.iacr.org/2022/647.
https://eprint.iacr.org/2022/647

[53] Francisco JR Ruiz, Tuomas Laakkonen, Johannes Bausch, Matej Balog, Mohammadamin Barekatain, Francisco JH Heras, Alexander Novikov, Nathan Fitzpatrick, Bernardino Romera-Paredes, John van de Wetering, et al. ``Quantum circuit optimization with alphatensor'' (2024). arXiv:2402.14396.
arXiv:2402.14396

[54] Xiaoning Bian. ``STOMP-code''. https://github.com/onestruggler/stomp-code/tree/8df4f46228c2f413e0cf5f8b6d25c20b6460fc0e.
https://github.com/onestruggler/stomp-code/tree/8df4f46228c2f413e0cf5f8b6d25c20b6460fc0e

[55] https://github.com/VivienVandaele/quantum_circuit_optimization (2023).
https://github.com/VivienVandaele/quantum_circuit_optimization

[56] Cody Jones. ``Low-overhead constructions for the fault-tolerant Toffoli gate''. Physical Review A—Atomic, Molecular, and Optical Physics 87, 022328 (2013).
https://doi.org/10.1103/physreva.87.022328

[57] Sergey Bravyi and Jeongwan Haah. ``Magic-state distillation with low overhead''. Physical Review A—Atomic, Molecular, and Optical Physics 86, 052329 (2012).
https://doi.org/10.1103/physreva.86.052329

[58] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. ``On the controlled-NOT complexity of controlled-NOT–phase circuits''. Quantum Science and Technology 4, 015002 (2018).
https://doi.org/10.1088/2058-9565/aad8ca

[59] Vivien Vandaele, Simon Martiel, and Timothée Goubault de Brugière. ``Phase polynomials synthesis algorithms for NISQ architectures and beyond''. Quantum Science and Technology 7, 045027 (2022).
https://doi.org/10.1088/2058-9565/ac5a0e

[60] Vivien Vandaele, Simon Perdrix, and Christophe Vuillot. ``Optimal number of parametrized rotations and Hadamard gates in parametrized Clifford circuits with non-repeated parameters'' (2024). arXiv:2407.07846.
arXiv:2407.07846

[61] Vivien Vandaele. ``Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost'' (2025). arXiv:2501.16136.
arXiv:2501.16136

[62] Peter W Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th annual symposium on foundations of computer science. Pages 124–134. Ieee (1994).
https://doi.org/10.1109/sfcs.1994.365700

[63] Guillaume Duclos-Cianci and David Poulin. ``Reducing the quantum-computing overhead with complex gate distillation''. Physical Review A 91, 042315 (2015).
https://doi.org/10.1103/physreva.91.042315

[64] Earl T Campbell and Mark Howard. ``Magic state parity-checker with pre-distilled components''. Quantum 2, 56 (2018).
https://doi.org/10.22331/q-2018-03-14-56

[65] Abraham Lempel. ``Matrix Factorization over $GF(2)$ and Trace-Orthogonal Bases of $GF(2^n )$''. SIAM Journal on Computing 4, 175–186 (1975).
https://doi.org/10.1137/0204014

[66] Gérard D Cohen and Simon N Litsyn. ``On the covering radius of Reed-Muller codes''. Discrete Mathematics 106, 147–155 (1992).
https://doi.org/10.1016/0012-365x(92)90542-n

Cited by

[1] Zihan Chen, Henry Chen, Yuwei Jin, Enhyeok Jang, Mingkuan Xu, Vannessa Chan, Won Woo Ro, and Eddy Z. Zhang, 2026 ACM/IEEE 53rd Annual International Symposium on Computer Architecture (ISCA) 2111 (2026) ISBN:979-8-3315-5065-3.

[2] Mu-Te Lau, Hsiang-Chun Yang, Hsin-Yu Chen, and Chung-Yang Huang, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 481 (2025) ISBN:979-8-3315-5736-2.

[3] Oskar Słowik, Piotr Dulian, and Adam Sawicki, "Quantum circuit overhead", Physical Review A 114 1, 012454 (2026).

[4] Yusei Mori, Hideaki Hakoshima, and Keisuke Fujii, "Nontrivial Multiproduct Commutation Relation Toward Reducing T -Count in Sequential Pauli-Based Computation", PRX Quantum 7 2, 020345 (2026).

[5] Yi-Hsiang Kuo, Hsiang-Chun Yang, Hsin-Yu Chen, and Chung-Yang Ric Huang, 2026 Design, Automation & Test in Europe Conference (DATE) 1 (2026) ISBN:978-3-9826741-1-7.

[6] Matthew Amy and Joseph Lunderville, "Linear and Non-linear Relational Analyses for Quantum Program Optimization", Proceedings of the ACM on Programming Languages 9 POPL, 1072 (2025).

[7] Davide Castaldo and Markus Reiher, "Utility-Scale Quantum Computational Chemistry", The Journal of Physical Chemistry Letters 17 29, 8140 (2026).

[8] Meng Wang, Chenxu Liu, Sean Garner, Samuel Stein, Yufei Ding, Prashant J. Nair, and Ang Li, "Tableau-Based Framework for Efficient Logical Quantum Compilation", arXiv:2509.02721, (2025).

[9] Mu-Te Lau, Hsiang-Chun Yang, Hsin-Yu Chen, and Chung-Yang Ric Huang, "A Lazy Resynthesis Approach for Simultaneous T Gate and Two-Qubit Gate Optimization of Quantum Circuits", arXiv:2508.04092, (2025).

[10] Dmitrii Khitrin, Kenneth R. Brown, and Abhinav Anand, "Unbiased observable estimation with approximate channels in fault-tolerant quantum computation", Quantum Science and Technology 11 1, 015034 (2026).

[11] Archisman Ghosh, Avimita Chatterjee, and Swaroop Ghosh, "Design Automation in Quantum Error Correction", arXiv:2507.12253, (2025).

[12] Abhinav Anand and Kenneth R. Brown, "Stabilizer configuration interaction: Finding molecular subspaces with error detection properties", Physical Review A 112 3, 032421 (2025).

[13] Vivien Vandaele, "Qubit-count optimization using ZX-calculus", arXiv:2407.10171, (2024).

[14] Tianyi Hao, Amanda Xu, and Swamit Tannu, "Reducing T Gates with Unitary Synthesis", arXiv:2503.15843, (2025).

[15] Matthew Amy and Joseph Lunderville, "Linear and non-linear relational analyses for Quantum Program Optimization", arXiv:2410.23493, (2024).

[16] Hanyu Wang, Mingfei Yu, Xinrui Wu, and Jason Cong, "Quantum Circuit Synthesis Using an Exact T Library", arXiv:2605.15476, (2026).

[17] Aws Albarghouthi, "Linear-Time T-Gate Optimization via Random Abstraction", arXiv:2605.13929, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 15:33:36) and SAO/NASA ADS (last updated successfully 2026-08-10 15:33:37). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.