Catalytic $z$-rotations in constant $T$-depth

Isaac H. Kim

doi:10.22331/q-2026-08-13-2191

Catalytic $z$-rotations in constant $T$-depth

Isaac H. Kim

Department of Computer Science, University of California, Davis, CA, 95616, USA

Published:	2026-08-13, volume 10, page 2191
Editor:	Alexander Schuckert
Eprint:	arXiv:2506.15147v3
Doi:	https://doi.org/10.22331/q-2026-08-13-2191
Citation:	Quantum 10, 2191 (2026).

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

Abstract

We show that the $T$-depth of any single-qubit $z$-rotation can be reduced to $3$ if a certain catalyst state is available. To achieve an $\epsilon$-approximation, it suffices to have a catalyst state of size polynomial in $\log(1/\epsilon)$. This implies that $\mathsf{QNC}^0_f/\mathsf{qpoly}$ admits a finite universal gate set consisting of Clifford+$T$. In particular, there are catalytic constant $T$-depth circuits that approximate multi-qubit Toffoli, adder, and quantum Fourier transform arbitrarily well. We also show that the catalyst state can be prepared in time polynomial in $\log (1/\epsilon)$.

► BibTeX data

@article{Kim2026catalyticzrotations,
  doi = {10.22331/q-2026-08-13-2191},
  url = {https://doi.org/10.22331/q-2026-08-13-2191},
  title = {Catalytic {$z$}-rotations in constant {$T$}-depth},
  author = {Kim, Isaac H.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2191},
  month = aug,
  year = {2026}
}

► References

[1] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. ``Classical and quantum computation''. Number 47 in Graduate Studies in Mathematics. American Mathematical Soc. (2002).
https://doi.org/10.1090/gsm/047

[2] Daniel Litinski. ``Magic state distillation: Not as costly as you think''. Quantum 3, 205 (2019).
https://doi.org/10.22331/q-2019-12-02-205

[3] 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

[4] Neil J. Ross and Peter Selinger. ``Optimal ancilla-free clifford+t approximation of z-rotations'' (2016). arXiv:1403.2975.
arXiv:1403.2975

[5] Alex Bocharov, Martin Roetteler, and Krysta M Svore. ``Efficient synthesis of universal repeat-until-success quantum circuits''. Physical review letters 114, 080502 (2015).
https://doi.org/10.1103/PhysRevLett.114.080502

[6] 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

[7] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Phys. Rev. A 86, 032324 (2012).
https://doi.org/10.1103/PhysRevA.86.032324

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

[9] 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

[10] Hayato Goto. ``Minimizing resource overheads for fault-tolerant preparation of encoded states of the steane code''. Scientific reports 6, 19578 (2016).
https://doi.org/10.1038/srep19578

[11] Christopher Chamberland and Kyungjoo Noh. ``Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits''. npj Quantum Information 6, 91 (2020).
https://doi.org/10.1038/s41534-020-00319-5

[12] Tomohiro Itogawa, Yugo Takada, Yutaka Hirano, and Keisuke Fujii. ``Even more efficient magic state distillation by zero-level distillation'' (2024). arXiv:2403.03991.
https://doi.org/10.1103/thxx-njr6
arXiv:2403.03991

[13] Craig Gidney, Noah Shutty, and Cody Jones. ``Magic state cultivation: growing t states as cheap as cnot gates'' (2024). arXiv:2409.17595.
arXiv:2409.17595

[14] Lucas Daguerre and Isaac H. Kim. ``Code switching revisited: Low-overhead magic state preparation using color codes''. Phys. Rev. Res. 7, 023080 (2025).
https://doi.org/10.1103/PhysRevResearch.7.023080

[15] Lucas Daguerre, Robin Blume-Kohout, Natalie C. Brown, David Hayes, and Isaac H. Kim. ``Experimental demonstration of high-fidelity logical magic states from code switching''. Phys. Rev. X 15, 041008 (2025).
https://doi.org/10.1103/dck4-x9c2

[16] Shival Dasu, Simon Burton, Karl Mayer, David Amaro, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Davide DelVento, Andrew C. Potter, and David Hayes. ``Breaking even with magic: demonstration of a high-fidelity logical non-clifford gate'' (2025). arXiv:2506.14688.
arXiv:2506.14688

[17] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. ``Lower bounds on the non-clifford resources for quantum computations''. Quantum Science and Technology 5, 035009 (2020).
https://doi.org/10.1088/2058-9565/ab8963

[18] Natalie Parham. ``Quantum circuit lower bounds in the magic hierarchy'' (2025). arXiv:2504.19966.
arXiv:2504.19966

[19] 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

[20] Earl T. Campbell. ``Catalysis and activation of magic states in fault-tolerant architectures''. Phys. Rev. A 83, 032317 (2011).
https://doi.org/10.1103/PhysRevA.83.032317

[21] Craig Gidney and Austin G. Fowler. ``Efficient magic state factories with a catalyzed $|CCZ\rangle$ to $2|T\rangle$ transformation''. Quantum 3, 135 (2019).
https://doi.org/10.22331/q-2019-04-30-135

[22] M. Amy, M. Crawford, A. N. Glaudell, M. L. Macasieb, S. S. Mendelson, and N. J. Ross. ``Catalytic embeddings of quantum circuits'' (2023). arXiv:2305.07720.
arXiv:2305.07720

[23] Peter Høyer and Robert Špalek. ``Quantum fan-out is powerful''. Theory of computing 1, 81–103 (2005).
https://doi.org/10.4086/toc.2005.v001a005

[24] Yasuhiro Takahashi and Seiichiro Tani. ``Collapse of the hierarchy of constant-depth exact quantum circuits''. computational complexity 25, 849–881 (2016).
https://doi.org/10.1007/s00037-016-0140-0

[25] Richard Beigel. ``The polynomial method in circuit complexity''. In [1993] Proceedings of the Eighth Annual Structure in Complexity Theory Conference. Pages 82–95. IEEE (1993).
https://doi.org/10.1109/SCT.1993.336538

[26] Craig Gidney. ``Halving the cost of quantum addition''. Quantum 2, 74 (2018).
https://doi.org/10.22331/q-2018-06-18-74

[27] Algirdas Avizienis. ``Signed-digit number representations for fast parallel arithmetic''. IRE Transactions on electronic computers EC-10, 389–400 (1961).
https://doi.org/10.1109/TEC.1961.5219227

[28] Peter Selinger. ``Quantum circuits of $t$-depth one''. Phys. Rev. A 87, 042302 (2013).
https://doi.org/10.1103/PhysRevA.87.042302

[29] Cristopher Moore and Martin Nilsson. ``Parallel quantum computation and quantum codes''. SIAM journal on computing 31, 799–815 (2001).
https://doi.org/10.1137/S0097539799355053

[30] Janusz Rajski and Jerzy Tyszer. ``Primitive polynomials over gf (2) of degree up to 660 with uniformly distributed coefficients''. Journal of Electronic testing 19, 645–657 (2003).
https://doi.org/10.1023/A:1027422805851

[31] Richard P Brent and Paul Zimmermann. ``The great trinomial hunt''. Notices of the AMS 58, 233–239 (2011). url: https://www.ams.org/notices/201102/rtx110200233p.pdf.
https://www.ams.org/notices/201102/rtx110200233p.pdf

[32] Joerg Arndt. ``Complete list of primitive trinomials over GF(2) up to degree 400''. https://www.jjj.de/mathdata/all-trinomial-primpoly.txt (2003). Text file generated 2003-01-16.
https://www.jjj.de/mathdata/all-trinomial-primpoly.txt

[33] Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoefler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, and Alexander Vaschillo. ``Assessing requirements to scale to practical quantum advantage'' (2022). arXiv:2211.07629.
arXiv:2211.07629

[34] 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

[35] J Barkley Rosser and Lowell Schoenfeld. ``Approximate formulas for some functions of prime numbers''. Illinois Journal of Mathematics 6, 64–94 (1962).
https://doi.org/10.1215/ijm/1255631807

[36] Richard Cleve and John Watrous. ``Fast parallel circuits for the quantum fourier transform''. In Proceedings 41st Annual Symposium on Foundations of Computer Science. Pages 526–536. IEEE (2000).
https://doi.org/10.1109/SFCS.2000.892140

[37] Harumichi Nishimura and Tomoyuki Yamakami. ``Polynomial time quantum computation with advice''. Information Processing Letters 90, 195–204 (2004).
https://doi.org/10.1016/j.ipl.2004.02.005

[38] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. ``Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 515–526. (2019).
https://doi.org/10.1145/3313276.3316404

[39] Craig Gidney. ``Post on x (twitter)''. https://x.com/CraigGidney/status/1936285631359197210. Accessed: 2026-02-12.
https://x.com/CraigGidney/status/1936285631359197210

[40] Isaac H. Kim and Tuomas Laakkonen. ``Any clifford+t circuit can be controlled with constant t-depth overhead'' (2025). arXiv:2512.24982.
arXiv:2512.24982

[41] Alastair Kay. ``Tutorial on the quantikz package'' (2023). arXiv:1809.03842.
arXiv:1809.03842

Cited by

[1] William A. Simon and Peter J. Love, "Halving the arbitrary rotation cost of controlled, Trotterized time evolution", Physical Review A 114 3, 032425 (2026).

[2] Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen, "Random Unitaries in Constant (Quantum) Time", arXiv:2508.11487, (2025).

[3] Jeongrak Son, Ray Ganardi, Shintaro Minagawa, Francesco Buscemi, Seok Hyung Lie, and Nelly H. Y. Ng, "Catalytic Channels Are the Only Noise-Robust Catalytic Processes", Physical Review Letters 136 5, 050202 (2026).

[4] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).

[5] Matteo Ippoliti and David M. Long, "Infinite Temperature at Zero Energy", Physical Review X 16 3, 031030 (2026).

[6] Craig Gidney, "A Classical-Quantum Adder with Constant Workspace and Linear Gates", arXiv:2507.23079, (2025).

[7] Isaac H. Kim and Tuomas Laakkonen, "Any Clifford+T circuit can be controlled with constant T-depth overhead", arXiv:2512.24982, (2025).

[8] Berta Casas, Paolo Braccia, Élie Gouzien, M. Cerezo, and Diego García-Martín, "Matchgate synthesis via Clifford matchgates and $T$ gates", arXiv:2602.05425, (2026).

[9] Yichen Xu and Xiao Wang, "Controlled jump in the Clifford hierarchy", arXiv:2602.22201, (2026).

[10] William A. Simon and Peter J. Love, "Halving the Cost of Controlled Time-Evolution", arXiv:2511.13855, (2025).

[11] Zoë Webb-Mack and Natalie Klco, "Deforming the Trail: Baseline Quantum Circuitry for $\text{SU(2)}_k$ Lattice Gauge Theory", arXiv:2605.15076, (2026).

[12] Anqi Gong, Christopher A. Pattison, Patrick Rall, and Adam Wills, "Magic State Distillation via Codes over Binary Extension Fields", arXiv:2608.09727, (2026).

[13] Uma Girish, Alex May, Natalie Parham, and Henry Yuen, "New bounds on private simultaneous quantum message passing", arXiv:2606.12557, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-09-17 02:54:18) and SAO/NASA ADS (last updated successfully 2026-09-17 02:54:19). 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.