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.
Abstract
Kliuchnikov, Maslov, and Mosca proved in 2012 that a $2times 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/isqrt{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.
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/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] Andrew N. Glaudell, Neil J. Ross, and Jacob M. Taylor, “Optimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation”, arXiv:2001.05997.
The above citations are from SAO/NASA ADS (last updated successfully 2020-06-03 19:22:01). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2020-06-03 19:21:59).
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.
Source: https://quantum-journal.org/papers/q-2020-04-06-252/
