1University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, UK
2Cambridge Quantum Computing Ltd, 9a Bridge Street, Cambridge CB2 1UB, UK
3Department of Computer Science, University of Oxford
4CNRS LORIA, Inria-MOCQUA, Université de Lorraine, F 54000 Nancy, France
5Institute for Computing and Information Sciences, Radboud University Nijmegen
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We present a completely new approach to quantum circuit optimisation, based on the ZX-calculus. We first interpret quantum circuits as ZX-diagrams, which provide a flexible, lower-level language for describing quantum computations graphically. Then, using the rules of the ZX-calculus, we give a simplification strategy for ZX-diagrams based on the two graph transformations of local complementation and pivoting and show that the resulting reduced diagram can be transformed back into a quantum circuit. While little is known about extracting circuits from arbitrary ZX-diagrams, we show that the underlying graph of our simplified ZX-diagram always has a graph-theoretic property called generalised flow, which in turn yields a deterministic circuit extraction procedure. For Clifford circuits, this extraction procedure yields a new normal form that is both asymptotically optimal in size and gives a new, smaller upper bound on gate depth for nearest-neighbour architectures. For Clifford+T and more general circuits, our technique enables us to to `see around’ gates that obstruct the Clifford structure and produce smaller circuits than naïve `cut-and-resynthesise’ methods.
Popular summary
In this paper, we give a technique for optimising quantum circuits that first breaks the gates open to reveal a graph-like structure underneath. We then give a strategy for reducing these graphs in size without changing the computation they represent, then extracting a new, smaller circuit out of the result.
We have implemented the technique described in this paper in a Python tool called PyZX:
https://github.com/Quantomatic/pyzx
For a 2-minute intro to PyZX, see this YouTube video: https://www.youtube.com/watch?v=iC-KVdB8pf0
If that leaves you wanting more, there is also a 40-minute talk about this and more on YouTube: https://www.youtube.com/watch?v=JafI_LZts2g
► BibTeX data
► References
[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328
[2] Nabila Abdessaied, Mathias Soeken, and Rolf Drechsler. Quantum circuit optimization by Hadamard gate reduction. In International Conference on Reversible Computation, pages 149–162. Springer, 2014. 10.1007/978-3-319-08494-7_12.
https://doi.org/10.1007/978-3-319-08494-7_12
[3] Matthew Amy, Dmitri Maslov, and Michele 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.
https://doi.org/10.1109/TCAD.2014.2341953
[4] Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. New Journal of Physics, 16 (9): 093021, 2014. 10.1088/1367-2630/16/9/093021.
https://doi.org/10.1088/1367-2630/16/9/093021
[5] Miriam Backens. Making the stabilizer ZX-calculus complete for scalars. In Chris Heunen, Peter Selinger, and Jamie Vicary, editors, Proceedings of the 12th International Workshop on Quantum Physics and Logic (QPL 2015), volume 195 of Electronic Proceedings in Theoretical Computer Science, pages 17–32, 2015. 10.4204/EPTCS.195.2.
https://doi.org/10.4204/EPTCS.195.2
[6] André Bouchet. Graphic presentations of isotropic systems. J. Comb. Theory Ser. A, 45: 58–76, July 1987. ISSN 0097-3165. URL http://dl.acm.org/citation.cfm?id=51355.51360.
http://dl.acm.org/citation.cfm?id=51355.51360
[7] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the clifford group. arXiv preprint arXiv:2003.09412, 2020.
arXiv:2003.09412
[8] Daniel E Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix. Generalized flow and determinism in measurement-based quantum computation. New Journal of Physics, 9 (8): 250, 2007. 10.1088/1367-2630/9/8/250. URL http://stacks.iop.org/1367-2630/9/i=8/a=250.
https://doi.org/10.1088/1367-2630/9/8/250
http://stacks.iop.org/1367-2630/9/i=8/a=250
[9] Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of Graphical Languages for Mixed States Quantum Mechanics. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 108:1–108:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-109-2. 10.4230/LIPIcs.ICALP.2019.108.
https://doi.org/10.4230/LIPIcs.ICALP.2019.108
[10] B. Coecke and A. Kissinger. Picturing Quantum Processes. Cambridge University Press, 2014. 10.1007/978-3-319-91376-6_6.
https://doi.org/10.1007/978-3-319-91376-6_6
[11] Bob Coecke and Ross Duncan. Interacting quantum observables: Categorical algebra and diagrammatics. New Journal of Physics, 13 (4): 043016, apr 2011. 10.1088/1367-2630/13/4/043016. URL https://doi.org/10.1088.
https://doi.org/10.1088/1367-2630/13/4/043016
[12] V. Danos and E. Kashefi. Determinism in the one-way model. Phys. Rev. A, 74 (052310), 2006. 10.1103/PhysRevA.74.052310.
https://doi.org/10.1103/PhysRevA.74.052310
[13] Vincent Danos, Elham Kashefi, and Prakash Panangaden. The measurement calculus. Journal of the ACM (JACM), 54 (2): 8, 2007. 10.1145/1219092.1219096.
https://doi.org/10.1145/1219092.1219096
[14] Vincent Danos, Elham Kashefi, Prakash Panangaden, and Simon Perdrix. Extended Measurement Calculus. Semantic Techniques in Quantum Computation, 2010. 10.1017/CBO9781139193313.008.
https://doi.org/10.1017/CBO9781139193313.008
[15] Jeroen Dehaene and Bart De Moor. Clifford group, stabilizer states, and linear and quadratic operations over GF(2). Physical Review A, 68 (4): 042318, 2003. 10.1103/PhysRevA.68.042318.
https://doi.org/10.1103/PhysRevA.68.042318
[16] R. Duncan and S. Perdrix. Graph states and the necessity of Euler decomposition. Mathematical Theory and Computational Practice, pages 167–177, 2009. 10.1007/978-3-642-03073-4_18.
https://doi.org/10.1007/978-3-642-03073-4_18
[17] R. Duncan and S. Perdrix. Rewriting measurement-based quantum computations with generalised flow. In Proceedings of ICALP, Lecture Notes in Computer Science, pages 285–296. Springer, 2010. 10.1007/978-3-642-14162-1_24.
https://doi.org/10.1007/978-3-642-14162-1_24
[18] Ross Duncan and Simon Perdrix. Pivoting makes the ZX-calculus complete for real stabilizers. In Proceedings of the 10th International Workshop on Quantum Physics and Logic (QPL), volume 171 of Electronic Proceedings in Theoretical Computer Science, pages 50–62. Open Publishing Association, 2014. 10.4204/EPTCS.171.5.
https://doi.org/10.4204/EPTCS.171.5
[19] Andrew Fagan and Ross Duncan. Optimising Clifford Circuits with Quantomatic. In Proceedings of the 15th International Conference on Quantum Physics and Logic (QPL), volume 287 of Electronic Proceedings in Theoretical Computer Science, pages 85–105. Open Publishing Association, 2019. 10.4204/EPTCS.287.5.
https://doi.org/10.4204/EPTCS.287.5
[20] Amar Hadzihasanovic, Kang Feng Ng, and Quanlong Wang. Two complete axiomatisations of pure-state qubit quantum computing. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages 502–511, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5583-4. 10.1145/3209108.3209128.
https://doi.org/10.1145/3209108.3209128
[21] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, M Nest, and H-J Briegel. Entanglement in graph states and its applications. In Proceedings of the International School of Physics “Enrico Fermi”, Quantum Computers, Algorithms and Chaos,, volume 162, pages 115 – 218, 2006. 10.3254/978-1-61499-018-5-115.
https://doi.org/10.3254/978-1-61499-018-5-115
[22] Luke E Heyfron and Earl T Campbell. An efficient quantum compiler that reduces T count. Quantum Science and Technology, 4 (015004), 2018. 10.1088/2058-9565/aad604.
https://doi.org/10.1088/2058-9565/aad604
[23] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Diagrammatic Reasoning Beyond Clifford+T Quantum Mechanics. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages 569–578, New York, NY, USA, 2018a. ACM. ISBN 978-1-4503-5583-4. 10.1145/3209108.3209139.
https://doi.org/10.1145/3209108.3209139
[24] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum Mechanics. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’18, pages 559–568, New York, NY, USA, 2018b. ACM. ISBN 978-1-4503-5583-4. 10.1145/3209108.3209131.
https://doi.org/10.1145/3209108.3209131
[25] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A generic normal form for zx-diagrams and application to the rational angle completeness. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019. 10.1109/LICS.2019.8785754.
https://doi.org/10.1109/LICS.2019.8785754
[26] Aleks Kissinger and Arianne Meijer-van de Griend. Cnot circuit extraction for topologically-constrained quantum memories. arXiv preprint arXiv:1904.00633, 2019.
arXiv:1904.00633
[27] Aleks Kissinger and John van de Wetering. Reducing T-count with the ZX-calculus. arXiv preprint arXiv:1903.10477, 2019.
arXiv:1903.10477
[28] Aleks Kissinger and John van de Wetering. Pyzx: Large scale automated diagrammatic reasoning. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019, volume 318 of Electronic Proceedings in Theoretical Computer Science, pages 229–241. Open Publishing Association, 2020. 10.4204/EPTCS.318.14.
https://doi.org/10.4204/EPTCS.318.14
[29] Vadym Kliuchnikov and Dmitri Maslov. Optimization of Clifford circuits. Phys. Rev. A, 88: 052307, Nov 2013. 10.1103/PhysRevA.88.052307.
https://doi.org/10.1103/PhysRevA.88.052307
[30] Anton Kotzig. Eulerian lines in finite 4-valent graphs and their transformations. In Colloqium on Graph Theory Tihany 1966, pages 219–230. Academic Press, 1968.
[31] Samuel A Kutin, David Petrie Moulton, and Lawren M Smithline. Computation at a distance. arXiv preprint quant-ph/0701194, 2007.
arXiv:quant-ph/0701194
[32] Ketan Markov, Igor Patel, and John Hayes. Optimal synthesis of linear reversible circuits. Quantum Information and Computation, 8 (3&4): 0282–0294, 2008.
[33] Dmitri Maslov and Martin Roetteler. Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations. IEEE Transactions on Information Theory, 64 (7): 4729–4738, 2018. 10.1109/TIT.2018.2825602.
https://doi.org/10.1109/TIT.2018.2825602
[34] Mehdi Mhalla, Mio Murao, Simon Perdrix, Masato Someya, and Peter S Turner. Which graph states are useful for quantum information processing? In Conference on Quantum Computation, Communication, and Cryptography, pages 174–187. Springer, 2011. 10.1007/978-3-642-54429-3_12.
https://doi.org/10.1007/978-3-642-54429-3_12
[35] Yunseong Nam, Neil J Ross, Yuan Su, Andrew M Childs, and Dmitri Maslov. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information, 4 (1): 23, 2018. 10.1038/s41534-018-0072-4.
https://doi.org/10.1038/s41534-018-0072-4
[36] Beatrice Nash, Vlad Gheorghiu, and Michele Mosca. Quantum circuit optimizations for NISQ architectures. arXiv preprint arXiv:1904.01972, 2019. 10.1088/2058-9565/ab79b1.
https://doi.org/10.1088/2058-9565/ab79b1
arXiv:1904.01972
[37] M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010. 10.1119/1.1463744.
https://doi.org/10.1119/1.1463744
[38] Maarten Van Den Nest. Classical simulation of quantum computation, the gottesman-knill theorem, and slightly beyond. Quantum Information & Computation, 10 (3): 258–271, 2010.
[39] Renaud Vilmart. A near-optimal axiomatisation of ZX-calculus for pure qubit quantum mechanics. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019. 10.1109/LICS.2019.8785765. URL https://arxiv.org/abs/1812.09114.
https://doi.org/10.1109/LICS.2019.8785765
arXiv:1812.09114
[40] Fang Zhang and Jianxin Chen. Optimizing t gates in clifford+t circuit as $pi/4$ rotations around paulis. arXiv:1903.12456, 2019.
arXiv:1903.12456
Cited by
[1] Aleks Kissinger and John van de Wetering, “Reducing T-count with the ZX-calculus”, arXiv:1903.10477.
[2] Aleks Kissinger and Arianne Meijer-van de Griend, “CNOT circuit extraction for topologically-constrained quantum memories”, arXiv:1904.00633.
[3] Niel de Beaudrap and Dominic Horsman, “The ZX calculus is a language for surface code lattice surgery”, arXiv:1704.08670.
[4] Raban Iten, Oliver Reardon-Smith, Luca Mondada, Ethan Redmond, Ravjot Singh Kohli, and Roger Colbeck, “Introduction to UniversalQCompiler”, arXiv:1904.01072.
[5] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons, and Seyon Sivarajah, “Phase Gadget Synthesis for Shallow Circuits”, arXiv:1906.01734.
[6] Titouan Carette, Dominic Horsman, and Simon Perdrix, “SZX-calculus: Scalable Graphical Quantum Reasoning”, arXiv:1905.00041.
[7] John van de Wetering and Sal Wolffs, “Completeness of the Phase-free ZH-calculus”, arXiv:1904.07545.
[8] Aleks Kissinger and John van de Wetering, “PyZX: Large Scale Automated Diagrammatic Reasoning”, arXiv:1904.04735.
[9] Cole Comfort, “Circuit Relations for Real Stabilizers: Towards TOF+H”, arXiv:1904.10614.
[10] Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart, “Completeness of Graphical Languages for Mixed States Quantum Mechanics”, arXiv:1902.07143.
[11] Niel de Beaudrap, Ross Duncan, Dominic Horsman, and Simon Perdrix, “Pauli Fusion: a Computational Model to Realise Quantum Transformations from ZX Terms”, arXiv:1904.12817.
[12] Aleks Kissinger and John van de Wetering, “Universal MBQC with generalised parity-phase interactions and Pauli measurements”, arXiv:1704.06504.
[13] Stach Kuijpers, John van de Wetering, and Aleks Kissinger, “Graphical Fourier Theory and the Cost of Quantum Addition”, arXiv:1904.07551.
[14] A. D. Corcoles, A. Kandala, A. Javadi-Abhari, D. T. McClure, A. W. Cross, K. Temme, P. D. Nation, M. Steffen, and J. M. Gambetta, “Challenges and Opportunities of Near-Term Quantum Computing Systems”, arXiv:1910.02894.
[15] Prakash Murali, David C. McKay, Margaret Martonosi, and Ali Javadi-Abhari, “Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers”, arXiv:2001.02826.
[16] Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister, “Logical Clifford Synthesis for Stabilizer Codes”, arXiv:1907.00310.
[17] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang, “Fast and effective techniques for T-count reduction via spider nest identities”, arXiv:2004.05164.
[18] Sergey Bravyi and Dmitri Maslov, “Hadamard-free circuits expose the structure of the Clifford group”, arXiv:2003.09412.
[19] Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering, “There and back again: A circuit extraction tale”, arXiv:2003.01664.
[20] Hector Miller-Bakewell, “Entanglement and Quaternions: The graphical calculus ZQ”, arXiv:2003.09999.
[21] Narayanan Rengaswamy, “Classical Coding Approaches to Quantum Applications”, arXiv:2004.06834.
The above citations are from SAO/NASA ADS (last updated successfully 2020-06-04 12:48: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 2020-06-04 12:48:21: Could not fetch cited-by data for 10.22331/q-2020-06-04-279 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.
Source: https://quantum-journal.org/papers/q-2020-06-04-279/
