Completeness of the ZH-calculus

Miriam Backens; Aleks Kissinger; Hector Miller-Bakewell; John van de Wetering; Sal Wolffs

doi:10.32408/compositionality-5-5

ABSTRACT

There are various gate sets used for describing quantum computation. A particularly popular one consists of Clifford gates and arbitrary single-qubit phase gates. Computations in this gate set can be elegantly described by the ZX-calculus, a graphical language for a class of string diagrams describing linear maps between qubits. The ZX-calculus has proven useful in a variety of areas of quantum information, but is less suitable for reasoning about operations outside its natural gate set such as multi-linear Boolean operations like the Toffoli gate. In this paper we study the ZH-calculus, an alternative graphical language of string diagrams that does allow straightforward encoding of Toffoli gates and other more complicated Boolean logic circuits. We find a set of simple rewrite rules for this calculus and show it is complete with respect to matrices over $\mathbb Z[\frac12]$, which correspond to the approximately universal Toffoli+Hadamard gateset. Furthermore, we construct an extended version of the ZH-calculus that is complete with respect to matrices over any ring $R$ where $1+1$ is not a zero-divisor.

► BibTeX data

@article{Backens2023completenessofzh,
  doi = {10.32408/compositionality-5-5},
  url = {https://doi.org/10.32408/compositionality-5-5},
  title = {Completeness of the {ZH}-calculus},
  author = {Backens, Miriam and Kissinger, Aleks and Miller-Bakewell, Hector and Wetering, John van de and Wolffs, Sal},
  journal = {{Compositionality}},
  issn = {2631-4444},
  publisher = {{Compositionality}},
  volume = {5},
  pages = {5},
  month = jul,
  year = {2023}
}

► References

[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. https://doi.org/10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328

[2] Matthew Amy. Towards large-scale functional verification of universal quantum circuits. In Peter Selinger and Giulio Chiribella, editors, Proceedings of the 15th International Conference on Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018, volume 287 of Electronic Proceedings in Theoretical Computer Science, pages 1–21. Open Publishing Association, 2019. https://doi.org/10.4204/EPTCS.287.1.
https://doi.org/10.4204/EPTCS.287.1

[3] Matthew Amy, Andrew N. Glaudell, and Neil J. Ross. Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits. Quantum, 4: 252, 4 2020. ISSN 2521-327X. https://doi.org/10.22331/q-2020-04-06-252.
https://doi.org/10.22331/q-2020-04-06-252

[4] Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. New Journal of Physics, 16 (9): 093021, 2014. https://doi.org/10.1088/1367-2630/16/9/093021.
https://doi.org/10.1088/1367-2630/16/9/093021

[5] Miriam Backens and Aleks Kissinger. ZH: A complete graphical calculus for quantum computations involving classical non-linearity. In Peter Selinger and Giulio Chiribella, editors, Proceedings of the 15th International Conference on Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018, volume 287 of Electronic Proceedings in Theoretical Computer Science, pages 23–42. Open Publishing Association, 2019. https://doi.org/10.4204/EPTCS.287.2.
https://doi.org/10.4204/EPTCS.287.2

[6] 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, 3 2021. ISSN 2521-327X. https://doi.org/10.22331/q-2021-03-25-421.
https://doi.org/10.22331/q-2021-03-25-421

[7] Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, pages 175–179. IEEE, 1984.

[8] Titouan Carette. When Only Topology Matters. 2021. https://doi.org/10.48550/arXiv.2102.03178.
https://doi.org/10.48550/arXiv.2102.03178

[9] Titouan Carette and Emmanuel Jeandel. A Recipe for Quantum Graphical Languages. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 118:1–118:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-138-2. https://doi.org/10.4230/LIPIcs.ICALP.2020.118.
https://doi.org/10.4230/LIPIcs.ICALP.2020.118

[10] Nicholas Chancellor, Aleks Kissinger, Joschka Roffe, Stefan Zohren, and Dominic Horsman. Graphical structures for design and verification of quantum error correction. 2016. https://doi.org/10.48550/arXiv.1611.08012.
https://doi.org/10.48550/arXiv.1611.08012

[11] Bob Coecke and Ross Duncan. Interacting quantum observables. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, 2008. https://doi.org/10.1007/978-3-540-70583-3_25.
https://doi.org/10.1007/978-3-540-70583-3_25

[12] Bob Coecke and Ross Duncan. Interacting quantum observables: Categorical algebra and diagrammatics. New Journal of Physics, 13: 043016, 2011. https://doi.org/10.1088/1367-2630/13/4/043016.
https://doi.org/10.1088/1367-2630/13/4/043016

[13] Bob Coecke and Aleks Kissinger. The compositional structure of multipartite quantum entanglement. In Automata, Languages and Programming, Lecture Notes in Computer Science, pages 297–308. Springer, 2010. https://doi.org/10.1007/978-3-642-14162-1_25. Extended version: arXiv:1002.2540.
https://doi.org/10.1007/978-3-642-14162-1_25

[14] Bob Coecke and Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. https://doi.org/10.1017/9781316219317.
https://doi.org/10.1017/9781316219317

[15] Bob Coecke, Dusko Pavlovic, and Jamie Vicary. A new description of orthogonal bases. Mathematical Structures in Computer Science, 23 (3): 555–567, 2013. https://doi.org/10.1017/S0960129512000047.
https://doi.org/10.1017/S0960129512000047

[16] Cole Comfort. The ZX&-calculus: A complete graphical calculus for classical circuits using spiders. In Benoı̂t Valiron, Shane Mansfield, Pablo Arrighi, and Prakash Panangaden, editors, Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020, volume 340 of Electronic Proceedings in Theoretical Computer Science, pages 60–90. Open Publishing Association, 2021. https://doi.org/10.4204/EPTCS.340.4.
https://doi.org/10.4204/EPTCS.340.4

[17] 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: 010302, Jan 2022. https://doi.org/10.1103/PRXQuantum.3.010302.
https://doi.org/10.1103/PRXQuantum.3.010302

[18] Niel de Beaudrap and Dominic Horsman. The ZX calculus is a language for surface code lattice surgery. Quantum, 4, 2020. https://doi.org/10.22331/q-2020-01-09-218.
https://doi.org/10.22331/q-2020-01-09-218

[19] Ross Duncan and Simon Perdrix. Rewriting measurement-based quantum computations with generalised flow. In Proceedings of ICALP, Lecture Notes in Computer Science, pages 285–296. Springer, 2010. https://doi.org/10.1007/978-3-642-14162-1_24.
https://doi.org/10.1007/978-3-642-14162-1_24

[20] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum, 4: 279, 6 2020. ISSN 2521-327X. https://doi.org/10.22331/q-2020-06-04-279.
https://doi.org/10.22331/q-2020-06-04-279

[21] Richard D. P. East, Pierre Martin-Dussaud, and John van de Wetering. Spin-networks in the ZX-calculus. 2021. https://doi.org/10.48550/arXiv.2111.03114.
https://doi.org/10.48550/arXiv.2111.03114

[22] Andrew Fagan and Ross Duncan. Optimising Clifford circuits with Quantomatic. In Peter Selinger and Giulio Chiribella, editors, 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. https://doi.org/10.4204/EPTCS.287.5.
https://doi.org/10.4204/EPTCS.287.5

[23] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86 (3): 032324, 2012. https://doi.org/10.1103/PhysRevA.86.032324.
https://doi.org/10.1103/PhysRevA.86.032324

[24] Craig Gidney and Austin G. Fowler. Efficient magic state factories with a catalyzed $|CCZ\rangle$ to $2|T\rangle$ transformation. Quantum, 3: 135, 4 2019. ISSN 2521-327X. https://doi.org/10.22331/q-2019-04-30-135.
https://doi.org/10.22331/q-2019-04-30-135

[25] Daniel Gottesman. An introduction to quantum error correction and fault-tolerant quantum computation. In Quantum information science and its contributions to mathematics, Proceedings of Symposia in Applied Mathematics, volume 68, pages 13–58, 2010. https://doi.org/10.1090/psapm/068/2762145.
https://doi.org/10.1090/psapm/068/2762145

[26] Amar Hadzihasanovic. A diagrammatic axiomatisation for qubit entanglement. In 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 573–584. IEEE, 2015. https://doi.org/10.1109/LICS.2015.59.
https://doi.org/10.1109/LICS.2015.59

[27] Amar Hadzihasanovic. The algebra of entanglement and the geometry of composition. DPhil thesis, University of Oxford, 2017. https://doi.org/10.48550/arXiv.1709.08086.
https://doi.org/10.48550/arXiv.1709.08086

[28] Michael Hanks, Marta P. Estarellas, William J. Munro, and Kae Nemoto. Effective compression of quantum braided circuits aided by ZX-calculus. Physical Review X, 10: 041030, 2020. https://doi.org/10.1103/PhysRevX.10.041030.
https://doi.org/10.1103/PhysRevX.10.041030

[29] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A complete axiomatisation of the ZX-calculus for Clifford+T quantum mechanics. In 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '18, pages 559–568, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5583-4. https://doi.org/10.1145/3209108.3209131.
https://doi.org/10.1145/3209108.3209131

[30] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A generic normal form for ZX-diagrams and application to the rational angle completeness. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), LICS '19, pages 1–10. ACM, 2019. https://doi.org/10.1109/LICS.2019.8785754.
https://doi.org/10.1109/LICS.2019.8785754

[31] Aleks Kissinger and John van de Wetering. Universal MBQC with generalised parity-phase interactions and Pauli measurements. Quantum, 3: 134, 4 2019. ISSN 2521-327X. https://doi.org/10.22331/q-2019-04-26-134.
https://doi.org/10.22331/q-2019-04-26-134

[32] Aleks Kissinger and John van de Wetering. Reducing the number of non-Clifford gates in quantum circuits. Physical Review A, 102: 022406, 8 2020. https://doi.org/10.1103/PhysRevA.102.022406.
https://doi.org/10.1103/PhysRevA.102.022406

[33] Aleks Kissinger and John van de Wetering. Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions. Quantum Science and Technology, 2022. https://doi.org/10.1088/2058-9565/ac5d20.
https://doi.org/10.1088/2058-9565/ac5d20

[34] Aleks Kissinger, Alex Merry, and Matvey Soloviev. Pattern graph rewrite systems. Electronic Proceedings in Theoretical Computer Science, 143: 54–66, 3 2014. ISSN 2075-2180. https://doi.org/10.4204/EPTCS.143.5.
https://doi.org/10.4204/EPTCS.143.5

[35] Aleks Kissinger, John van de Wetering, and Renaud Vilmart. Classical simulation of quantum circuits with partial and graphical stabiliser decompositions. In François Le Gall and Tomoyuki Morimae, editors, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), volume 232 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:13, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-237-2. https://doi.org/10.4230/LIPIcs.TQC.2022.5.
https://doi.org/10.4230/LIPIcs.TQC.2022.5

[36] Stach Kuijpers, John van de Wetering, and Aleks Kissinger. Graphical Fourier theory and the cost of quantum addition. 2019. https://doi.org/10.48550/arXiv.1904.07551.
https://doi.org/10.48550/arXiv.1904.07551

[37] Louis Lemonnier, John van de Wetering, and Aleks Kissinger. Hypergraph simplification: Linking the path-sum approach to the ZH-calculus. 2020. https://doi.org/10.48550/arXiv.2003.13564.
https://doi.org/10.48550/arXiv.2003.13564

[38] Hector Miller-Bakewell. Entanglement and Quaternions: The graphical calculus ZQ. 2020a. https://doi.org/10.48550/arXiv.2003.09999.
https://doi.org/10.48550/arXiv.2003.09999

[39] Hector Miller-Bakewell. Graphical Calculi and Their Conjecture Synthesis. DPhil thesis, University of Oxford, 2020b. https://doi.org/10.48550/arXiv.2010.03914.
https://doi.org/10.48550/arXiv.2010.03914

[40] Kang Feng Ng and Quanlong Wang. A universal completion of the ZX-calculus. 2017. https://doi.org/10.48550/arXiv.1706.09877.
https://doi.org/10.48550/arXiv.1706.09877

[41] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2010. https://doi.org/10.1119/1.1463744.
https://doi.org/10.1119/1.1463744

[42] Peter Selinger. Dagger compact closed categories and completely positive maps. Electronic Notes in Theoretical computer science, 170: 139–163, 2007. https://doi.org/10.1016/j.entcs.2006.12.018.
https://doi.org/10.1016/j.entcs.2006.12.018

[43] Yaoyun Shi. Both Toffoli and controlled-not need little help to do universal quantum computing. Quantum Information & Computation, 3 (1): 84–92, 2003.

[44] John van de Wetering. ZX-calculus for the working quantum computer scientist. 2020. https://doi.org/10.48550/arXiv.2012.13966.
https://doi.org/10.48550/arXiv.2012.13966

[45] John van de Wetering and Sal Wolffs. Completeness of the phase-free ZH-calculus. 2019. https://doi.org/10.48550/arXiv.1904.07545.
https://doi.org/10.48550/arXiv.1904.07545

[46] Renaud Vilmart. A near-minimal axiomatisation of ZX-calculus for pure qubit quantum mechanics. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–10, 2019a. https://doi.org/10.1109/LICS.2019.8785765.
https://doi.org/10.1109/LICS.2019.8785765

[47] Renaud Vilmart. A ZX-calculus with triangles for Toffoli-Hadamard, Clifford+T, and beyond. In Peter Selinger and Giulio Chiribella, editors, Proceedings of the 15th International Conference on Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018, volume 287 of Electronic Proceedings in Theoretical Computer Science, pages 313–344. Open Publishing Association, 2019b. https://doi.org/10.4204/EPTCS.287.18.
https://doi.org/10.4204/EPTCS.287.18

[48] Renaud Vilmart, 2020. Personal communication.

[49] Renaud Vilmart. The structure of sum-over-paths, its consequences, and completeness for Clifford. In Stefan Kiefer and Christine Tasson, editors, Foundations of Software Science and Computation Structures, pages 531–550, Cham, 2021a. Springer International Publishing. ISBN 978-3-030-71995-1. https://doi.org/10.1007/978-3-030-71995-1_27.
https://doi.org/10.1007/978-3-030-71995-1_27

[50] Renaud Vilmart. Quantum multiple-valued decision diagrams in graphical calculi. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 89:1–89:15, Dagstuhl, Germany, 2021b. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-201-3. https://doi.org/10.4230/LIPIcs.MFCS.2021.89.
https://doi.org/10.4230/LIPIcs.MFCS.2021.89

[51] Renaud Vilmart. Completeness of sum-over-paths for Toffoli-Hadamard and the Clifford Hierarchy. HAL preprint: hal-03654438, 2022. https://hal.archives-ouvertes.fr/hal-03654438.
https://hal.archives-ouvertes.fr/hal-03654438

[52] Quanlong Wang. Algebraic complete axiomatisation of ZX-calculus with a normal form via elementary matrix operations. 2020. https://doi.org/10.48550/arXiv.2007.13739.
https://doi.org/10.48550/arXiv.2007.13739

[53] Fabio Zanasi. Interacting Hopf Algebras—The Theory of Linear Systems. PhD thesis, Lyon, École normale supérieure, 2015. https://doi.org/10.48550/arXiv.1805.03032.
https://doi.org/10.48550/arXiv.1805.03032

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2023-08-23 07:49:45). On SAO/NASA ADS no data on citing works was found (last attempt 2023-08-23 07:49:46).

This Paper is published in Compositionality 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.

Published:	2023-07-12, volume 5, page 5
Eprint:	arXiv:2103.06610v2
Doi:	https://doi.org/10.32408/compositionality-5-5
Citation:	Compositionality 5, 5 (2023).

Compositionality

The open-access journal for the mathematics of composition

ABSTRACT

► BibTeX data

► References

Cited by