Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus

Ross Duncan1,2, Aleks Kissinger3, Simon Perdrix4, and John van de Wetering5

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.


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.

Quantum circuits are a de facto assembly language for quantum software. Programs are described as list of primitive operations, or gates, which are run in sequence on a quantum computer to perform a computation. Just like with classical software, there is more that one way to write a program to do the same job, and so it's important to find programs that do that job as quickly and cheaply as possible. Looking at quantum circuits just as lists of gates doesn't tell us a whole lot about what computation is being performed, or how it might be optimised. However, if we "break open" quantum gates, we see a rich graphical/algebraic structure inside called the ZX-calculus.

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:

For a 2-minute intro to PyZX, see this YouTube video:

If that leaves you wanting more, there is also a 40-minute talk about this and more on YouTube:

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

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

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

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

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

[6] André Bouchet. Graphic presentations of isotropic systems. J. Comb. Theory Ser. A, 45: 58–76, July 1987. ISSN 0097-3165. URL http:/​/​​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.

[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:/​/​​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.

[10] B. Coecke and A. Kissinger. Picturing Quantum Processes. Cambridge University Press, 2014. 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:/​/​​10.1088.

[12] V. Danos and E. Kashefi. Determinism in the one-way model. Phys. Rev. A, 74 (052310), 2006. 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.

[14] Vincent Danos, Elham Kashefi, Prakash Panangaden, and Simon Perdrix. Extended Measurement Calculus. Semantic Techniques in Quantum Computation, 2010. 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.

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

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

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

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

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

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

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

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

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

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

[26] Aleks Kissinger and Arianne Meijer-van de Griend. Cnot circuit extraction for topologically-constrained quantum memories. arXiv preprint arXiv:1904.00633, 2019.

[27] Aleks Kissinger and John van de Wetering. Reducing T-count with the ZX-calculus. arXiv preprint arXiv:1903.10477, 2019.

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

[29] Vadym Kliuchnikov and Dmitri Maslov. Optimization of Clifford circuits. Phys. Rev. A, 88: 052307, Nov 2013. 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.

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

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

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

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

[37] M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information. Cambridge university press, 2010. 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:/​/​​abs/​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.

Cited by

[1] Niel de Beaudrap, "Well-tempered ZX and ZH Calculi", arXiv:2006.02557, Electronic Proceedings in Theoretical Computer Science 340, 13 (2021).

[2] Will Simmons, "Relating Measurement Patterns to Circuits via Pauli Flow", Electronic Proceedings in Theoretical Computer Science 343, 50 (2021).

[3] Louis Lemonnier, John van de Wetering, and Aleks Kissinger, "Hypergraph Simplification: Linking the Path-sum Approach to the ZH-calculus", Electronic Proceedings in Theoretical Computer Science 340, 188 (2021).

[4] Wonho Jang, Koji Terashi, Masahiko Saito, Christian W. Bauer, Benjamin Nachman, Yutaro Iiyama, Ryunosuke Okubo, and Ryu Sawada, "Initial-State Dependent Optimization of Controlled Gate Operations with Quantum Computer", Quantum 6, 798 (2022).

[5] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[6] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan, " t|ket⟩: a retargetable compiler for NISQ devices", Quantum Science and Technology 6 1, 014003 (2021).

[7] Alexis Toumi, Richie Yeung, and Giovanni de Felice, "Diagrammatic Differentiation for Quantum Machine Learning", Electronic Proceedings in Theoretical Computer Science 343, 132 (2021).

[8] Bob Coecke, Dominic Horsman, Aleks Kissinger, and Quanlong Wang, "Kindergarden quantum mechanics graduates ...or how I learned to stop gluing LEGO together and love the ZX-calculus", Theoretical Computer Science 897, 1 (2022).

[9] Wonho Jang, Koji Terashi, Masahiko Saito, Christian W. Bauer, Benjamin Nachman, Yutaro Iiyama, Tomoe Kishimoto, Ryunosuke Okubo, Ryu Sawada, Junichi Tanaka, C. Biscarat, S. Campana, B. Hegner, S. Roiser, C.I. Rovelli, and G.A. Stewart, "Quantum Gate Pattern Recognition and Circuit Optimization for Scientific Applications", EPJ Web of Conferences 251, 03023 (2021).

[10] Tahereh Salehi, Mariam Zomorodi, Pawel Plawiak, Mina Abbaszade, and Vahid Salari, "An optimizing method for performance and resource utilization in quantum machine learning circuits", Scientific Reports 12 1, 16949 (2022).

[11] Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering, "There and back again: A circuit extraction tale", Quantum 5, 421 (2021).

[12] Chen Zhao and Xiao-Shan Gao, "Analyzing the barren plateau phenomenon in training quantum neural networks with the ZX-calculus", Quantum 5, 466 (2021).

[13] Alexandru Paler, Lucian M. Sasu, Adrian-Cătălin Florea, and Răzvan Andonie, "Machine Learning Optimization of Quantum Circuit Layouts", ACM Transactions on Quantum Computing 3565271 (2022).

[14] Agustín Borgna, Simon Perdrix, and Benoît Valiron, Lecture Notes in Computer Science 13008, 121 (2021) ISBN:978-3-030-89050-6.

[15] Titouan Carette, Yohann D'Anello, and Simon Perdrix, "Quantum Algorithms and Oracles with the Scalable ZX-calculus", arXiv:2104.01043, Electronic Proceedings in Theoretical Computer Science 343, 193 (2021).

[16] Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov, "Clifford Circuit Optimization with Templates and Symbolic Pauli Gates", Quantum 5, 580 (2021).

[17] Nikodem Grzesiak, Andrii Maksymov, Pradeep Niroula, and Yunseong Nam, "Efficient quantum programming using EASE gates on a trapped-ion quantum computer", Quantum 6, 634 (2022).

[18] Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister, "Logical Clifford Synthesis for Stabilizer Codes", arXiv:1907.00310, IEEE Transactions on Quantum Engineering 1, 1 (2020).

[19] Robert Wille, Lukas Burgholzer, Stefan Hillmich, Thomas Grurl, Alexander Ploier, and Tom Peham, Proceedings of the 59th ACM/IEEE Design Automation Conference 1367 (2022) ISBN:9781450391429.

[20] John van de Wetering, "Constructing quantum circuits with global gates", New Journal of Physics 23 4, 043015 (2021).

[21] Aleks Kissinger and John van de Wetering, "Reducing the number of non-Clifford gates in quantum circuits", Physical Review A 102 2, 022406 (2020).

[22] Titouan Carette, Marc de Visme, and Simon Perdrix, 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 1 (2021) ISBN:978-1-6654-4895-6.

[23] Timothee Goubault de Brugiere, Marc Baboulin, Benoit Valiron, Simon Martiel, and Cyril Allouche, "Reducing the Depth of Linear Reversible Quantum Circuits", IEEE Transactions on Quantum Engineering 2, 1 (2021).

[24] Sergey Bravyi and Dmitri Maslov, "Hadamard-Free Circuits Expose the Structure of the Clifford Group", IEEE Transactions on Information Theory 67 7, 4546 (2021).

[25] Aleks Kissinger and John van de Wetering, "Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions", Quantum Science and Technology 7 4, 044001 (2022).

[26] Richard D.P. East, John van de Wetering, Nicholas Chancellor, and Adolfo G. Grushin, "AKLT-States as ZX-Diagrams: Diagrammatic Reasoning for Quantum States", PRX Quantum 3 1, 010302 (2022).

[27] Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart, "Completeness of Graphical Languages for Mixed State Quantum Mechanics", arXiv:1902.07143, ACM Transactions on Quantum Computing 2 4, 1 (2021).

[28] Bob Coecke, Giovanni de Felice, Konstantinos Meichanetzidis, and Alexis Toumi, Quantum Computing in the Arts and Humanities 277 (2022) ISBN:978-3-030-95537-3.

[29] Aleks Kissinger and John van de Wetering, "PyZX: Large Scale Automated Diagrammatic Reasoning", arXiv:1904.04735.

[30] Bob Coecke, Giovanni de Felice, Konstantinos Meichanetzidis, and Alexis Toumi, "Foundations for Near-Term Quantum Natural Language Processing", arXiv:2012.03755.

[31] Pascal Baßler, Matthias Zipper, Christopher Cedzich, Markus Heinrich, Patrick Huber, Michael Johanning, and Martin Kliesch, "Synthesis of and compilation with time-optimal multi-qubit gates", arXiv:2206.06387.

[32] Lucas Slattery and Bryan K. Clark, "Quantum Circuits For Two-Dimensional Isometric Tensor Networks", arXiv:2108.02792.

[33] Aleks Kissinger and Arianne Meijer-van de Griend, "CNOT circuit extraction for topologically-constrained quantum memories", arXiv:1904.00633.

[34] Aleks Kissinger and John van de Wetering, "Reducing T-count with the ZX-calculus", arXiv:1903.10477.

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

[36] Niel de Beaudrap and Dominic Horsman, "The ZX calculus is a language for surface code lattice surgery", arXiv:1704.08670.

[37] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons, and Seyon Sivarajah, "Phase Gadget Synthesis for Shallow Circuits", arXiv:1906.01734.

[38] Prakash Murali, David C. McKay, Margaret Martonosi, and Ali Javadi-Abhari, "Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers", arXiv:2001.02826.

[39] Raban Iten, Romain Moyard, Tony Metger, David Sutter, and Stefan Woerner, "Exact and practical pattern matching for quantum circuit optimization", arXiv:1909.05270.

[40] Tom Peham, Lukas Burgholzer, and Robert Wille, "Equivalence Checking of Quantum Circuits With the ZX-Calculus", IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12 3, 662 (2022).

[41] Stach Kuijpers, John van de Wetering, and Aleks Kissinger, "Graphical Fourier Theory and the Cost of Quantum Addition", arXiv:1904.07551.

[42] Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang, "Fast and effective techniques for T-count reduction via spider nest identities", arXiv:2004.05164.

[43] Jonathan Gorard, Manojna Namuduri, and Xerxes D. Arsiwalla, "ZX-Calculus and Extended Wolfram Model Systems II: Fast Diagrammatic Reasoning with an Application to Quantum Circuit Simplification", arXiv:2103.15820.

[44] John van de Wetering and Sal Wolffs, "Completeness of the Phase-free ZH-calculus", arXiv:1904.07545.

[45] Bob Coecke, "Compositionality as we see it, everywhere around us", arXiv:2110.05327.

[46] Hector Miller-Bakewell, "Entanglement and Quaternions: The graphical calculus ZQ", arXiv:2003.09999.

[47] Aleks Kissinger and John van de Wetering, "Universal MBQC with generalised parity-phase interactions and Pauli measurements", arXiv:1704.06504.

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

[49] Titouan Carette, Dominic Horsman, and Simon Perdrix, "SZX-calculus: Scalable Graphical Quantum Reasoning", arXiv:1905.00041.

[50] Bob Coecke, Giovanni de Felice, Konstantinos Meichanetzidis, and Alexis Toumi, "How to make qubits speak", arXiv:2107.06776.

[51] Narayanan Rengaswamy, "Classical Coding Approaches to Quantum Applications", arXiv:2004.06834.

[52] Cole Comfort, "Circuit Relations for Real Stabilizers: Towards TOF+H", arXiv:1904.10614.

[53] Lukas Burgholzer, Richard Kueng, and Robert Wille, "Random Stimuli Generation for the Verification of Quantum Circuits", arXiv:2011.07288.

[54] Jaeho Choi and Joongheon Kim, "Kirchhoff's Circuit Law Applications to Graph Simplification in Search Problems", arXiv:2009.11675.

[55] Agustín Borgna and Rafael Romero, "Encoding High-level Quantum Programs as SZX-diagrams", arXiv:2206.09376.

[56] Titouan Carette and Emmanuel Jeandel, "On a recipe for quantum graphical languages", arXiv:2008.04193.

The above citations are from Crossref's cited-by service (last updated successfully 2022-11-29 02:42:50) and SAO/NASA ADS (last updated successfully 2022-11-29 02:42:51). The list may be incomplete as not all publishers provide suitable and complete citation data.