Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits

Matthew Amy1, Andrew N. Glaudell2,3, and Neil J. Ross1

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

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


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

► 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.

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

[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.

[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.

[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.

[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.

[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.

[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.

[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:/​/​​ xbian/​talks/​slide_cliffordt2.pdf, June 2015.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

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

[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.

[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.

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

[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.

[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.

[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.

[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.

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] Justin Makary, Neil J. Ross, and Peter Selinger, "Generators and Relations for Real Stabilizer Operators", Electronic Proceedings in Theoretical Computer Science 343, 14 (2021).

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

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

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

[8] 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).

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

[10] 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).

[11] 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).

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

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

[14] 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).

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-21 21:40:37) and SAO/NASA ADS (last updated successfully 2023-09-21 21:40:38). The list may be incomplete as not all publishers provide suitable and complete citation data.