Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits

Matthew Amy; Andrew N. Glaudell; Neil J. Ross

doi:10.22331/q-2020-04-06-252

Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits

Matthew Amy¹, Andrew N. Glaudell^2,3, and Neil J. Ross¹

¹Department of Mathematics and Statistics, Dalhousie University, Halifax, NS, Canada
²Institute for Advanced Computer Studies and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD, USA
³Joint Quantum Institute, University of Maryland, College Park, MD, USA

Published:	2020-04-06, volume 4, page 252
Eprint:	arXiv:1908.06076v3
Doi:	https://doi.org/10.22331/q-2020-04-06-252
Citation:	Quantum 4, 252 (2020).

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

Abstract

Kliuchnikov, Maslov, and Mosca proved in 2012 that a $2\times 2$ unitary matrix $V$ can be exactly represented by a single-qubit Clifford+$T$ circuit if and only if the entries of $V$ belong to the ring $\mathbb{Z}[1/\sqrt{2},i]$. Later that year, Giles and Selinger showed that the same restriction applies to matrices that can be exactly represented by a multi-qubit Clifford+$T$ circuit. These number-theoretic characterizations shed new light upon the structure of Clifford+$T$ circuits and led to remarkable developments in the field of quantum compiling. In the present paper, we provide number-theoretic characterizations for certain restricted Clifford+$T$ circuits by considering unitary matrices over subrings of $\mathbb{Z}[1/\sqrt{2},i]$. We focus on the subrings $\mathbb{Z}[1/2]$, $\mathbb{Z}[1/\sqrt{2}]$, $\mathbb{Z}[1/i\sqrt{2}]$, and $\mathbb{Z}[1/2,i]$, and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates $\{X, CX, CCX\}$ with an analogue of the Hadamard gate and an optional phase gate.

► BibTeX data

@article{Amy2020numbertheoretic,
  doi = {10.22331/q-2020-04-06-252},
  url = {https://doi.org/10.22331/q-2020-04-06-252},
  title = {Number-{T}heoretic {C}haracterizations of {S}ome {R}estricted {C}lifford+{T} {C}ircuits},
  author = {Amy, Matthew and Glaudell, Andrew N. and Ross, Neil J.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {252},
  month = apr,
  year = {2020}
}

► References

[1] S. Aaronson, D. Grier, and L. Schaeffer. The classification of reversible bit operations. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference, volume 67 of LIPIcs, pages 23:1–23:34, 2017. 10.4230/LIPIcs.ITCS.2017.23. Also available from arxiv1504.05155.
https://doi.org/10.4230/LIPIcs.ITCS.2017.23

[2] D. Aharonov. A simple proof that Toffoli and Hadamard are quantum universal. Preprint available from arxivquant-ph/0301040, Jan. 2003.
arXiv:quant-ph/0301040

[3] M. Amy and M. Mosca. T-count optimization and Reed-Muller codes. IEEE Transactions on Information Theory, 65 (8): 4771–4784, 2019. 10.1109/TIT.2019.2906374. Also available from arxiv1601.07363.
https://doi.org/10.1109/TIT.2019.2906374

[4] M. Amy, D. Maslov, M. Mosca, and M. 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 (6): 818–830, 2013. 10.1109/TCAD.2013.2244643. Also available from arxiv1206.0758.
https://doi.org/10.1109/TCAD.2013.2244643

[5] M. Amy, D. Maslov, and M. 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 (10): 1476–1489, 2014. 10.1109/TCAD.2014.2341953. Also available from arxiv1303.2042.
https://doi.org/10.1109/TCAD.2014.2341953

[6] M. Amy, J. Chen, and N. J. Ross. A finite presentation of CNOT-dihedral operators. In Proceedings of the 14th International Conference on Quantum Physics and Logic, QPL '17, pages 84–97, 2017. 10.4204/EPTCS.266.5.
https://doi.org/10.4204/EPTCS.266.5

[7] M. Artin. Algebra. Prentice Hall, 1991.

[8] M. Backens and A. Kissinger. ZH: A complete graphical calculus for quantum computations involving classical non-linearity. In Proceedings of the 15th International Conference on Quantum Physics and Logic, QPL '18, pages 23–42, 2018. 10.4204/EPTCS.287.2.
https://doi.org/10.4204/EPTCS.287.2

[9] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Physical Review A, 52: 3457–3467, 1995. 10.1103/PhysRevA.52.3457. Also available from arxivquant-ph/9503016.
https://doi.org/10.1103/PhysRevA.52.3457
arXiv:quant-ph/9503016

[10] X. Bian. Private communication, July 2019.

[11] X. Bian and P. Selinger. Relations for the group of 2-qubit Clifford+T operators. Talk given at the Quantum Programming and Circuits Workshop. Slides available from https://www.mathstat.dal.ca/ xbian/talks/slide_cliffordt2.pdf, June 2015.
https://www.mathstat.dal.ca/~xbian/talks/slide_cliffordt2.pdf

[12] A. Bocharov, Y. Gurevich, and K. M. Svore. Efficient decomposition of single-qubit gates into V basis circuits. Physical Review A, 88: 012313, 2013. 10.1103/PhysRevA.88.012313. Also available from arxiv1303.1411.
https://doi.org/10.1103/PhysRevA.88.012313

[13] A. Bocharov, M. Roetteler, and K. M. Svore. Efficient synthesis of probabilistic quantum circuits with fallback. Physical Review A, 91: 052317, 2015. 10.1103/PhysRevA.91.052317. Also available from arxiv1409.3552.
https://doi.org/10.1103/PhysRevA.91.052317

[14] A. Bouland and S. Aaronson. Generation of universal linear optics by any beam splitter. Physical Review A, 89: 062316, 2014. 10.1103/PhysRevA.89.062316. Also available from arxiv1310.6718.
https://doi.org/10.1103/PhysRevA.89.062316

[15] A. De Vos, R. Van Laer, and S. Vandenbrande. The group of dyadic unitary matrices. Open Systems & Information Dynamics, 19 (01): 1250003, 2012. 10.1142/S1230161212500035.
https://doi.org/10.1142/S1230161212500035

[16] S. Forest, D. Gosset, V. Kliuchnikov, and D. McKinnon. Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets. Journal of Mathematical Physics, 56 (8): 082201, 2015. 10.1063/1.4927100. Also available from arxiv1501.04944.
https://doi.org/10.1063/1.4927100

[17] B. Giles and P. Selinger. Exact synthesis of multiqubit Clifford+T circuits. Physical Review A, 87: 032332, 2013a. 10.1103/PhysRevA.87.032332. Also available from arxiv1212.0506.
https://doi.org/10.1103/PhysRevA.87.032332

[18] B. Giles and P. Selinger. Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators. Preprint available from arxiv1312.6584, Dec. 2013b.

[19] D. Gosset, V. Kliuchnikov, M. Mosca, and V. Russo. An algorithm for the T-count. Quantum Information & Computation, 14 (15-16): 1261–1276, 2014. 10.26421/QIC14.15-16. Also available from arxiv1308.4134.
https://doi.org/10.26421/QIC14.15-16

[20] S. Greylyn. Generators and relations for the group $U_4(\mathbb{Z}[1/\sqrt{2},i])$. Master's thesis. Available from arxiv1408.6204, 2014.

[21] D. Grier and L. Schaeffer. The classification of stabilizer operations over qubits. Preprint available from arxiv1603.03999, 2016.

[22] A. K. Hashagen, S. T. Flammia, D. Gross, and J. J. Wallman. Real randomized benchmarking. Quantum, 2: 85, 2018. 10.22331/q-2018-08-22-85. Also available from arxiv1801.06121.
https://doi.org/10.22331/q-2018-08-22-85

[23] L. E. Heyfron and E. T. Campbell. An efficient quantum compiler that reduces T count. Quantum Science and Technology, 4 (1): 015004, 2018. 10.1088/2058-9565/aad604. Also available from arxiv1712.01557.
https://doi.org/10.1088/2058-9565/aad604

[24] E. Jeandel, S. Perdrix, and R. Vilmart. Y-calculus: A language for real matrices derived from the ZX-calculus. In Proceedings of the 14th International Conference on Quantum Physics and Logic, QPL '17, pages 23–57, 2017. 10.4204/EPTCS.266.2.
https://doi.org/10.4204/EPTCS.266.2

[25] V. Kliuchnikov and J. Yard. A framework for exact synthesis. Preprint available from arxiv1504.04350, April 2015.

[26] V. Kliuchnikov, D. Maslov, and M. Mosca. Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates. Quantum Information & Computation, 13 (7-8): 607–630, 2013. 10.26421/QIC13.7-8. Also available from arxiv1206.5236.
https://doi.org/10.26421/QIC13.7-8

[27] V. Kliuchnikov, A. Bocharov, and K. M. Svore. Asymptotically optimal topological quantum compiling. Physical Review Letters, 112: 140504, 2014. 10.1103/PhysRevLett.112.140504. Also available from arxiv1310.4150.
https://doi.org/10.1103/PhysRevLett.112.140504

[28] V. Kliuchnikov, D. Maslov, and M. Mosca. Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits. IEEE Transactions on Computers, 65 (1): 161–172, 2016. 10.1109/TC.2015.2409842. Also available from arxiv1212.6964.
https://doi.org/10.1109/TC.2015.2409842

[29] K. Matsumoto and K. Amano. Representation of quantum circuits with Clifford and $\pi$/8 gates. Preprint available from arxiv0806.3834, June 2008.

[30] G. Meuli, M. Soeken, and G. D. Micheli. SAT-based $\{CNOT, T\}$ quantum circuit synthesis. In Proceedings of the 10th International Conference on Reversible Computation, RC '17, pages 175–188, 2018. 10.1007/978-3-319-99498-7_12.
https://doi.org/10.1007/978-3-319-99498-7_12

[31] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge Series on Information and the Natural Sciences. Cambridge University Press, 2000. ISBN 9780521635035. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[32] O. Parzanchevski and P. Sarnak. Super-Golden-Gates for PU(2). Advances in Mathematics, 327: 869 – 901, 2018. https://doi.org/10.1016/j.aim.2017.06.022. Special volume honoring David Kazhdan. Also available from arxiv1704.02106.
https://doi.org/10.1016/j.aim.2017.06.022

[33] N. J. Ross. Optimal ancilla-free Clifford+V approximation of z-rotations. Quantum Information & Computation, 15 (11–12): 932–950, 2015. 10.26421/QIC15.11-12. Also available from arxiv1409.4355.
https://doi.org/10.26421/QIC15.11-12

[34] N. J. Ross and P. Selinger. Optimal ancilla-free Clifford+T approximation of z-rotations. Quantum Information & Computation, 16 (11-12): 901–953, 2016. 10.26421/QIC16.11-12. Also available from arxiv1403.2975.
https://doi.org/10.26421/QIC16.11-12

[35] T. Rudolph and L. Grover. A 2 rebit gate universal for quantum computing. Preprint available from arxivquant-ph/0210187, Nov. 2002.
arXiv:quant-ph/0210187

[36] P. Selinger. Generators and relations for $n$-qubit Clifford operators. Logical Methods in Computer Science, 11 (10): 1–17, 2015. 10.2168/LMCS-11(2:10)2015. Also available from arxiv1310.6813.
https://doi.org/10.2168/LMCS-11(2:10)2015

[37] Y. Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Information & Computation, 3 (1): 84–92, 2003. 10.26421/QIC3.1. Also available from arxivquant-ph/0205115.
https://doi.org/10.26421/QIC3.1
arXiv:quant-ph/0205115

[38] R. Vilmart. A ZX-calculus with triangles for Toffoli-Hadamard, Clifford+T, and beyond. In Proceedings of the 15th International Conference on Quantum Physics and Logic, QPL '18, pages 313–344, 2018. 10.4204/EPTCS.287.18.
https://doi.org/10.4204/EPTCS.287.18

[39] J. Welch, A. Bocharov, and K. M. Svore. Efficient approximation of diagonal unitaries over the Clifford+T basis. Quantum Information & Computation, 16 (1-2): 87–104, 2016. 10.26421/QIC16.1-2. Also available from arxiv1412.5608.
https://doi.org/10.26421/QIC16.1-2

Cited by

[1] Xiaoning Bian and Peter Selinger, "Generators and Relations for Un(Z[1/2,i])", Electronic Proceedings in Theoretical Computer Science 343, 145 (2021).

[2] Matthew Amy, Andrew N. Glaudell, Sarah Meng Li, and Neil J. Ross, Lecture Notes in Computer Science 13960, 169 (2023) ISBN:978-3-031-38099-0.

[3] Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering, and Sal Wolffs, "Completeness of the ZH-calculus", Compositionality 5, 5 (2023).

[4] Youssef Amraoui and Zeno Toffano, "Geometric Algebra Quantum Gate Decomposition", Axioms 15 7, 523 (2026).

[5] Daniel Grier and Luke Schaeffer, "The Classification of Clifford Gates over Qubits", Quantum 6, 734 (2022).

[6] Priyanka Mukhopadhyay, "Synthesis of V-count-optimal quantum circuits for multiqubit unitaries", Physical Review A 109 5, 052619 (2024).

[7] Vincent G. Harris and Parisa Andalib, "Modern quantum materials", Frontiers in Materials 11, 1343005 (2024).

[8] Jacques Carette, Chris Heunen, Robin Kaarsgaard, and Amr Sabry, "With a Few Square Roots, Quantum Computing Is as Easy as Pi", Proceedings of the ACM on Programming Languages 8 POPL, 546 (2024).

[9] Jatin Arora, Mingkuan Xu, Sam Westrick, Pengyu Liu, Dantong Li, Yongshan Ding, and Umut A. Acar, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 572 (2025) ISBN:979-8-3315-5736-2.

[10] Patrick Roy, John van de Wetering, and Lia Yeh, "The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality", Electronic Proceedings in Theoretical Computer Science 384, 142 (2023).

[11] Andrew N. Glaudell, Neil J. Ross, John van de Wetering, and Lia Yeh, "Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits", Electronic Proceedings in Theoretical Computer Science 406, 44 (2024).

[12] Synthesis Lectures on Computer Architecture (2020) ISBN:978-3-031-00637-1.

[13] Wang Fang, Chris Heunen, and Robin Kaarsgaard, "Hadamard-Pi: Equational Quantum Programming", Proceedings of the ACM on Programming Languages 10 POPL, 117 (2026).

[14] Giovanni De Micheli, Jie-Hong R. Jiang, Robert Rand, Kaitlin Smith, and Mathias Soeken, "Advances in Quantum Computation and Quantum Technologies: A Design Automation Perspective", IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12 3, 584 (2022).

[15] Xiaohui Li and Shunlong Luo, "Optimality of T-gate for generating magic resource", Communications in Theoretical Physics 75 4, 045101 (2023).

[16] Alexis De Vos, "Quantum Computing with the Subgroup YU(n) of the Unitary Group U(n)", Open Systems & Information Dynamics 32 01, 2550002 (2025).

[17] Hasan Sayginel, Francois Jamet, Abhishek Agarwal, Dan E Browne, and Ivan Rungger, "A fault-tolerant variational quantum algorithm with limited T-depth", Quantum Science and Technology 9 1, 015015 (2024).

[18] Matthew Amy, "Complete Equational Theories for the Sum-Over-Paths with Unbalanced Amplitudes", Electronic Proceedings in Theoretical Computer Science 384, 127 (2023).

[19] Matthew Amy, Andrew N. Glaudell, Shaun Kelso, William Maxwell, Samuel S. Mendelson, and Neil J. Ross, Lecture Notes in Computer Science 14680, 238 (2024) ISBN:978-3-031-62075-1.

[20] Linh Dinh and Neil J. Ross, "Contributions to the Theory of Clifford-Cyclotomic Circuits", Electronic Proceedings in Theoretical Computer Science 426, 231 (2025).

[21] Jacques Carette, Chris Heunen, Robin Kaarsgaard, Neil J. Ross, and Amr Sabry, "Free quantum computing", Proceedings of the National Academy of Sciences 123 8, e2510881123 (2026).

[22] Priyanka Mukhopadhyay, "CS-count-optimal quantum circuits for arbitrary multi-qubit unitaries", Scientific Reports 14 1, 13916 (2024).

[23] Justin Makary, Neil J. Ross, and Peter Selinger, "Generators and Relations for Real Stabilizer Operators", Electronic Proceedings in Theoretical Computer Science 343, 14 (2021).

[24] Sarah Meng Li, Neil J. Ross, and Peter Selinger, "Generators and Relations for the Group On(Z[1/2])", Electronic Proceedings in Theoretical Computer Science 343, 210 (2021).

[25] Matthew Amy, Neil J. Ross, and Scott Wesley, "A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits", Electronic Proceedings in Theoretical Computer Science 406, 1 (2024).

[26] Andrew N. Glaudell, Neil J. Ross, and Jacob M. Taylor, "Optimal two-qubit circuits for universal fault-tolerant quantum computation", npj Quantum Information 7 1, 103 (2021).

[27] Xiaoning Bian and Peter Selinger, "Generators and Relations for 3-Qubit Clifford+CS Operators", Electronic Proceedings in Theoretical Computer Science 384, 114 (2023).

[28] Ismail Yunus Akhalwaya, Adam Connolly, Roland Guichard, Steven Herbert, Cahit Kargi, Alexandre Krajenbrink, Michael Lubasch, Conor Mc Keever, Julien Sorci, Michael Spranger, and Ifan Williams, "A Modular Engine for Quantum Monte Carlo Integration", arXiv:2308.06081, (2023).

[29] Robin Kaarsgaard, "Universality of a standard two-qubit gate by catalytic embedding", arXiv:2509.07578, (2025).

[30] M. Amy, M. Crawford, A. N. Glaudell, M. L. Macasieb, S. S. Mendelson, and N. J. Ross, "Catalytic Embeddings of Quantum Circuits", arXiv:2305.07720, (2023).

[31] Dorian Rudolph, "Towards a universal gateset for $\mathsf{QMA}_1$", arXiv:2411.02681, (2024).

[32] Vadym Kliuchnikov and Sebastian Schönnenbeck, "Multi-qubit circuit synthesis and Hermitian lattices", arXiv:2405.19302, (2024).

[33] Matthew Amy, Neil J. Ross, and Scott Wesley, "A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits", arXiv:2407.11152, (2024).

[34] Xiaohui Li and Shunlong Luo, "Optimal diagonal qutrit gates for creating Wigner negativity", Physics Letters A 460, 128620 (2023).

[35] Wang Fang, Chris Heunen, and Robin Kaarsgaard, "Hadamard-Pi: Equational Quantum Programming", arXiv:2506.06835, (2025).

[36] Andrew N. Glaudell, Neil J. Ross, John van de Wetering, and Lia Yeh, "Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits", arXiv:2405.08136, (2024).

[37] Sarah Meng Li, Neil J. Ross, and Peter Selinger, "Generators and Relations for the Group On(Z[1/2])", arXiv:2106.01175, (2021).

[38] Linh Dinh and Neil J. Ross, "Contributions to the Theory of Clifford-Cyclotomic Circuits", arXiv:2508.14674, (2025).

[39] Patrick Roy, John van de Wetering, and Lia Yeh, "The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality", arXiv:2307.10095, (2023).

[40] Xiaoning Bian and Peter Selinger, "Generators and Relations for 3-Qubit Clifford+CS Operators", arXiv:2306.08530, (2023).

[41] Justin Makary, Neil J. Ross, and Peter Selinger, "Generators and Relations for Real Stabilizer Operators", arXiv:2109.05655, (2021).

[42] Xiaoning Bian and Peter Selinger, "Generators and Relations for Un(Z[1/2,i])", arXiv:2105.14047, (2021).

[43] Alexandre Clément, "A Complete Equational Theory for Real-Clifford+CH Quantum Circuits", arXiv:2602.06644, (2026).

[44] Youssef Amraoui and Zeno Toffano, "Geometric Algebra Quantum Gate Decomposition", arXiv:2606.12480, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-08 17:10:25) and SAO/NASA ADS (last updated successfully 2026-08-08 17:10:26). 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.