{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T23:01:30Z","timestamp":1771455690356,"version":"3.50.1"},"reference-count":39,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T00:00:00Z","timestamp":1586131200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Kliuchnikov, Maslov, and Mosca proved in 2012 that a 2<\/mml:mn>\u00d7<\/mml:mo>2<\/mml:mn><\/mml:math> unitary matrix V<\/mml:mi><\/mml:math> can be exactly represented by a single-qubit Clifford+T<\/mml:mi><\/mml:math> circuit if and only if the entries of V<\/mml:mi><\/mml:math> belong to the ring Z<\/mml:mi><\/mml:mrow>[<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn><\/mml:msqrt>,<\/mml:mo>i<\/mml:mi>]<\/mml:mo><\/mml:math>. 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<\/mml:mi><\/mml:math> circuit. These number-theoretic characterizations shed new light upon the structure of Clifford+T<\/mml:mi><\/mml:math> 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<\/mml:mi><\/mml:math> circuits by considering unitary matrices over subrings of Z<\/mml:mi><\/mml:mrow>[<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn><\/mml:msqrt>,<\/mml:mo>i<\/mml:mi>]<\/mml:mo><\/mml:math>. We focus on the subrings Z<\/mml:mi><\/mml:mrow>[<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn>]<\/mml:mo><\/mml:math>, Z<\/mml:mi><\/mml:mrow>[<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn><\/mml:msqrt>]<\/mml:mo><\/mml:math>, Z<\/mml:mi><\/mml:mrow>[<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>i<\/mml:mi>2<\/mml:mn><\/mml:msqrt>]<\/mml:mo><\/mml:math>, and Z<\/mml:mi><\/mml:mrow>[<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn>,<\/mml:mo>i<\/mml:mi>]<\/mml:mo><\/mml:math>, 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 {<\/mml:mo>X<\/mml:mi>,<\/mml:mo>C<\/mml:mi>X<\/mml:mi>,<\/mml:mo>C<\/mml:mi>C<\/mml:mi>X<\/mml:mi>}<\/mml:mo><\/mml:math> with an analogue of the Hadamard gate and an optional phase gate.<\/jats:p>","DOI":"10.22331\/q-2020-04-06-252","type":"journal-article","created":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T14:24:19Z","timestamp":1586183059000},"page":"252","source":"Crossref","is-referenced-by-count":26,"title":["Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits"],"prefix":"10.22331","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3514-420X","authenticated-orcid":false,"given":"Matthew","family":"Amy","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, Dalhousie University, Halifax, NS, Canada"}]},{"given":"Andrew N.","family":"Glaudell","sequence":"additional","affiliation":[{"name":"Institute for Advanced Computer Studies and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD, USA"},{"name":"Joint Quantum Institute, University of Maryland, College Park, MD, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0941-4333","authenticated-orcid":false,"given":"Neil J.","family":"Ross","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Dalhousie University, Halifax, NS, Canada"}]}],"member":"9598","published-online":{"date-parts":[[2020,4,6]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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\u201323:34, 2017. 10.4230\/LIPIcs.ITCS.2017.23. Also available from arxiv1504.05155.","DOI":"10.4230\/LIPIcs.ITCS.2017.23"},{"key":"1","unstructured":"D. Aharonov. A simple proof that Toffoli and Hadamard are quantum universal. Preprint available from arxivquant-ph\/0301040, Jan. 2003."},{"key":"2","doi-asserted-by":"publisher","unstructured":"M. Amy and M. Mosca. T-count optimization and Reed-Muller codes. IEEE Transactions on Information Theory, 65 (8): 4771\u20134784, 2019. 10.1109\/TIT.2019.2906374. Also available from arxiv1601.07363.","DOI":"10.1109\/TIT.2019.2906374"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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\u2013830, 2013. 10.1109\/TCAD.2013.2244643. Also available from arxiv1206.0758.","DOI":"10.1109\/TCAD.2013.2244643"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u20131489, 2014. 10.1109\/TCAD.2014.2341953. Also available from arxiv1303.2042.","DOI":"10.1109\/TCAD.2014.2341953"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u201397, 2017. 10.4204\/EPTCS.266.5.","DOI":"10.4204\/EPTCS.266.5"},{"key":"6","unstructured":"M. Artin. Algebra. Prentice Hall, 1991."},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u201342, 2018. 10.4204\/EPTCS.287.2.","DOI":"10.4204\/EPTCS.287.2"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u20133467, 1995. 10.1103\/PhysRevA.52.3457. Also available from arxivquant-ph\/9503016.","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"9","unstructured":"X. Bian. Private communication, July 2019."},{"key":"10","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.2168\/LMCS-11(2:10)2015"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.88.012313"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.91.052317"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.89.062316"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1142\/S1230161212500035"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1063\/1.4927100"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.87.032332"},{"key":"17","unstructured":"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."},{"key":"18","doi-asserted-by":"publisher","unstructured":"D. Gosset, V. Kliuchnikov, M. Mosca, and V. Russo. An algorithm for the T-count. Quantum Information & Computation, 14 (15-16): 1261\u20131276, 2014. 10.26421\/QIC14.15-16. Also available from arxiv1308.4134.","DOI":"10.26421\/QIC14.15-16"},{"key":"19","unstructured":"S. Greylyn. Generators and relations for the group $U_4(\\mathbb{Z}[1\/\\sqrt{2},i])$. Master's thesis. Available from arxiv1408.6204, 2014."},{"key":"20","unstructured":"D. Grier and L. Schaeffer. The classification of stabilizer operations over qubits. Preprint available from arxiv1603.03999, 2016."},{"key":"21","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2018-08-22-85"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/2058-9565\/aad604"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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\u201357, 2017. 10.4204\/EPTCS.266.2.","DOI":"10.4204\/EPTCS.266.2"},{"key":"24","unstructured":"V. Kliuchnikov and J. Yard. A framework for exact synthesis. Preprint available from arxiv1504.04350, April 2015."},{"key":"25","doi-asserted-by":"publisher","unstructured":"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\u2013630, 2013. 10.26421\/QIC13.7-8. Also available from arxiv1206.5236.","DOI":"10.26421\/QIC13.7-8"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.112.140504"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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\u2013172, 2016. 10.1109\/TC.2015.2409842. Also available from arxiv1212.6964.","DOI":"10.1109\/TC.2015.2409842"},{"key":"28","unstructured":"K. Matsumoto and K. Amano. Representation of quantum circuits with Clifford and $\\pi$\/8 gates. Preprint available from arxiv0806.3834, June 2008."},{"key":"29","doi-asserted-by":"publisher","unstructured":"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\u2013188, 2018. 10.1007\/978-3-319-99498-7_12.","DOI":"10.1007\/978-3-319-99498-7_12"},{"key":"30","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1017\/CBO9780511976667"},{"key":"31","unstructured":"O. Parzanchevski and P. Sarnak. Super-Golden-Gates for PU(2). Advances in Mathematics, 327: 869 \u2013 901, 2018. https:\/\/doi.org\/10.1016\/j.aim.2017.06.022. Special volume honoring David Kazhdan. Also available from arxiv1704.02106."},{"key":"32","doi-asserted-by":"publisher","unstructured":"N. J. Ross. Optimal ancilla-free Clifford+V approximation of z-rotations. Quantum Information & Computation, 15 (11\u201312): 932\u2013950, 2015. 10.26421\/QIC15.11-12. Also available from arxiv1409.4355.","DOI":"10.26421\/QIC15.11-12"},{"key":"33","doi-asserted-by":"publisher","unstructured":"N. J. Ross and P. Selinger. Optimal ancilla-free Clifford+T approximation of z-rotations. Quantum Information & Computation, 16 (11-12): 901\u2013953, 2016. 10.26421\/QIC16.11-12. Also available from arxiv1403.2975.","DOI":"10.26421\/QIC16.11-12"},{"key":"34","unstructured":"T. Rudolph and L. Grover. A 2 rebit gate universal for quantum computing. Preprint available from arxivquant-ph\/0210187, Nov. 2002."},{"key":"35","doi-asserted-by":"publisher","unstructured":"P. Selinger. Generators and relations for $n$-qubit Clifford operators. Logical Methods in Computer Science, 11 (10): 1\u201317, 2015. 10.2168\/LMCS-11(2:10)2015. Also available from arxiv1310.6813.","DOI":"10.2168\/LMCS-11(2:10)2015"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Y. Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Information & Computation, 3 (1): 84\u201392, 2003. 10.26421\/QIC3.1. Also available from arxivquant-ph\/0205115.","DOI":"10.26421\/QIC3.1"},{"key":"37","doi-asserted-by":"publisher","unstructured":"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\u2013344, 2018. 10.4204\/EPTCS.287.18.","DOI":"10.4204\/EPTCS.287.18"},{"key":"38","doi-asserted-by":"publisher","unstructured":"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\u2013104, 2016. 10.26421\/QIC16.1-2. Also available from arxiv1412.5608.","DOI":"10.26421\/QIC16.1-2"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-04-06-252\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T14:24:24Z","timestamp":1586183064000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-04-06-252\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,6]]},"references-count":39,"URL":"https:\/\/doi.org\/10.22331\/q-2020-04-06-252","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,6]]},"article-number":"252"}}