quantum-computing

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

Isaac H. Kim

14 min read

0 likes

⚡ Quantum Brief

AbstractWe 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)$. ``Complete list of primitive trinomials over GF(2) up to degree 400''. The list may be incomplete as not all publishers provide suitable and complete citation data.

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractWe 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.03842Cited by[1] Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen, "Random Unitaries in Constant (Quantum) Time", arXiv:2508.11487, (2025). [2] 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). [3] Matteo Ippoliti and David M. Long, "Infinite temperature at zero energy", arXiv:2509.04410, (2025). [4] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026). [5] Craig Gidney, "A Classical-Quantum Adder with Constant Workspace and Linear Gates", arXiv:2507.23079, (2025). [6] Isaac H. Kim and Tuomas Laakkonen, "Any Clifford+T circuit can be controlled with constant T-depth overhead", arXiv:2512.24982, (2025). [7] 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). [8] William A. Simon and Peter J. Love, "Halving the Cost of Controlled Time-Evolution", arXiv:2511.13855, (2025). [9] Yichen Xu and Xiao Wang, "Controlled jump in the Clifford hierarchy", arXiv:2602.22201, (2026). [10] Zoë Webb-Mack and Natalie Klco, "Deforming the Trail: Baseline Quantum Circuitry for $\text{SU(2)}_k$ Lattice Gauge Theory", arXiv:2605.15076, (2026). [11] 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 SAO/NASA ADS (last updated successfully 2026-08-13 13:52:22). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-08-13 13:52:21: Could not fetch cited-by data for 10.22331/q-2026-08-13-2191 from Crossref. This is normal if the DOI was registered recently.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. AbstractWe 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.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

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

Tags

Source Information