The ZX calculus is a language for surface code lattice surgery

Niel de Beaudrap1 and Dominic Horsman2

1Department of Computer Science, University of Oxford, Parks Road, Oxford, OX1 3QD
2Department of Physics, Durham University, South Road, Durham, DH1 1LE Department of Computer Science, University of Oxford, Parks Road, Oxford, OX1 3QD

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


A leading choice of error correction for scalable quantum computing is the surface code with lattice surgery. The basic lattice surgery operations, the merging and splitting of logical qubits, act non-unitarily on the logical states and are not easily captured by standard circuit notation. This raises the question of how best to design, verify, and optimise protocols that use lattice surgery, in particular in architectures with complex resource management issues. In this paper we demonstrate that the operations of the ZX calculus --- a form of quantum diagrammatic reasoning based on bialgebras --- match exactly the operations of lattice surgery. Red and green ``spider'' nodes match rough and smooth merges and splits, and follow the axioms of a dagger special associative Frobenius algebra. Some lattice surgery operations require non-trivial correction operations, which are captured natively in the use of the ZX calculus in the form of ensembles of diagrams. We give a first taste of the power of the calculus as a language for lattice surgery by considering two operations (T gates and producing a CNOT) and show how ZX diagram re-write rules give lattice surgery procedures for these operations that are novel, efficient, and highly configurable.

► BibTeX data

► References

[1] M. 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.

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

[3] H. Bombin. Topological order with a twist: Ising anyons from an Abelian model. Physical review letters, 105 (3): 030403, 2010. 10.1103/​PhysRevLett.105.030403.

[4] H. Bombin and M. Martin-Delgado. Quantum measurements and gates by code deformation. Journal of Physics A: Mathematical and Theoretical, 42 (9): 095302, 2009. 10.1088/​1751-8113/​42/​9/​095302.

[5] S. Bravyi and A. Kitaev. Quantum codes on a lattice with boundary. Preprint, arXiv:quant-ph/​9811052, 1998. Translation of Quantum Computers and Computing 2 (1), pp. 43-48. (2001).

[6] S. Bravyi and A. Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 10.1103/​PhysRevA.71.022316.

[7] E. Campbell and J. O'Gorman. An efficient magic state approach to small angle rotations. Quantum Science and Technology, 1 (1): 015007, 2016. 10.1088/​2058-9565/​1/​1/​015007.

[8] Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. Nature, 549 (7671): 172, 2017. 10.1038/​nature23460. arXiv:1612.07330.

[9] T. Carette, D. Horsman, and S. Perdrix. SZX-calculus: Scalable graphical quantum reasoning. Preprint, arXiv:1905.00041, 2019.

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

[11] B. Coecke and R. Duncan. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13 (4): 043016, 2011. 10.1088/​1367-2630/​13/​4/​043016.

[12] B. Coecke and A. Kissinger. Picturing Quantum Processes: A first course in quantum theory and diagrammatic reasoning. Cambridge University Press, 2017. 10.1017/​9781316219317.

[13] B Coecke, E. Paquette, and D. Pavlovic. Classical and quantum structuralism. Semantic Techniques in Quantum Computation, eds. Gay S., Mackie I., Cambridge University Press, 2008. 10.1017/​CBO9781139193313.003. arXiv:0904.1997.

[14] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the Qubit Routing Problem. In Wim van Dam and Laura Mancinska, editors, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:32, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-112-2. 10.4230/​LIPIcs.TQC.2019.5. URL http:/​/​​opus/​volltexte/​2019/​10397. arXiv:1902.08091.

[15] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill. Topological quantum memory. Journal of Mathematical Physics, 43 (9): 4452–4505, 2002. 10.1063/​1.1499754. arXiv:quant-ph/​0110143.

[16] R. Duncan and S. Perdrix. Graph states and the necessity of Euler decomposition. In Conference on Computability in Europe, pages 167–177. Springer, 2009. 10.1007/​978-3-642-03073-4.

[17] Ross Duncan and Maxime Lucas. Verifying the steane code with Quantomatic. Proceedings QPL 2013, pages 33–49, 2013. 10.4204/​EPTCS.171.4. arXiv:1306.4532.

[18] Ross Duncan and Simon Perdrix. Rewriting measurement-based quantum computations with generalised flow. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, pages 285–296, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. ISBN 978-3-642-14162-1.

[19] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. Graph-theoretic simplification of quantum circuits with the ZX-calculus. Preprint, arXiv:1902.03178, 2019.

[20] B. Eastin and E. Knill. Restrictions on transversal encoded quantum gate sets. Phys. Rev. Lett., 102: 110502, Mar 2009. 10.1103/​PhysRevLett.102.110502. arXiv:0811.4262.

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

[22] A. Fowler, A. Stephens, and P. Groszkowski. High-threshold universal quantum computation on the surface code. Phys. Rev. A, 80: 052312, 2009. 10.1103/​PhysRevA.80.052312.

[23] Austin G Fowler and Craig Gidney. Low overhead quantum computation using lattice surgery. Preprint, arXiv:1808.06709, 2018.

[24] M. Freedman and D. Meyer. Projective plane and planar quantum codes. Foundations of Computational Mathematics, 1 (3): 325–332, 2001. 10.1007/​s102080010013.

[25] Craig Gidney and Austin G Fowler. Efficient magic state factories with a catalyzed $\mathrm{\lvert CCZ\rangle}$ to $\mathrm{2\lvert T\rangle}$ transformation. Quantum, 3, 2019. 10.22331/​q-2019-04-30-135. arXiv:1812.01238.

[26] Google. https:/​/​​2018/​03/​a-preview-of-bristlecone-googles-new.html. Accessed 10/​04/​2019.

[27] Daniel Gottesman. Class of quantum error-correcting codes saturating the quantum Hamming bound. Physical Review A, 54 (3): 1862, 1996. 10.1103/​PhysRevA.54.1862. arXiv:quant-ph/​9604038.

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

[29] D. Herr, F. Nori, and S. Devitt. Lattice surgery translation for quantum computation. New Journal of Physics, (19): 013034, 2017. 10.1088/​1367-2630/​aa5709.

[30] C. Horsman, A. G Fowler, S. Devitt, and R. Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, 2012. 10.1088/​1367-2630/​14/​12/​123011. arXiv:1111.4022.

[31] IBM. https:/​/​​ibm-q/​. Accessed 10/​04/​2019.

[32] C. Jones, D. Kim, M. Rakher, P. Kwiat, and T. Ladd. Design and analysis of communication protocols for quantum repeater networks. New Journal of Physics, 18 (8): 083015, 2016. 10.1088/​1367-2630/​18/​8/​083015.

[33] A. Kissinger and V. Zamdzhiev. Quantomatic: A proof assistant for diagrammatic reasoning. In International Conference on Automated Deduction, pages 326–336. Springer, 2015. 10.1007/​978-3-319-21401-6_22.

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

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

[36] Aleks Kissinger and John van de Wetering. PyZX: Large scale automated diagrammatic reasoning. Preprint, arXiv:1904.04735, 2019b.

[37] E. Knill. Quantum computing with realistically noisy devices. Nature, 434 (7029): 39–44, 2005. 10.1038/​nature03350. arXiv:quant-ph/​0410199.

[38] Andrew J Landahl and Ciáran Ryan-Anderson. Quantum computing by color-code lattice surgery. Preprint, arXiv:1407.5103, 2014. SAND2014-15911J.

[39] Daniel Litinski. A game of surface codes: Large-scale quantum computing with lattice surgery. Quantum, 3: 128, 2019. 10.22331/​q-2019-03-05-128.

[40] N. Nickerson, Y. Li, and S. Benjamin. Topological quantum computing with a very noisy network and local error rates approaching one percent. Nature communications, 4: 1756, 2013. 10.1038/​ncomms2773.

[41] N. Nickerson, J. Fitzsimons, and S. Benjamin. Freely scalable quantum technologies using cells of 5-to-50 qubits with very lossy and noisy photonic links. Physical Review X, 4 (4): 041041, 2014. 10.1103/​PhysRevX.4.041041.

[42] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge UK, 2000. 10.1017/​CBO9780511976667.

[43] R. Raussendorf and J. Harrington. Fault-tolerant quantum computation with high threshold in two dimensions. Physical review letters, 98 (19): 190504, 2007. 10.1103/​PhysRevLett.98.190504.

[44] B. Terhal. Quantum error correction for quantum memories. Reviews of Modern Physics, 87 (2): 307, 2015. 10.1103/​RevModPhys.87.307.

[45] R. Van Meter. Quantum Networking. John Wiley & Sons, 2014. 10.1002/​9781118648919.

[46] R. Van Meter and C. Horsman. A blueprint for building a quantum computer. Communications of the ACM, 56 (10): 84–93, 2013. 10.1145/​2494568.

[47] The ZX-calculus. http:/​/​​. Accessed 08/​07/​2019.

Cited by

[1] Niel de Beaudrap, Ross Duncan, Dominic Horsman, and Simon Perdrix, "Pauli Fusion: a Computational Model to Realise Quantum Transformations from ZX Terms", Electronic Proceedings in Theoretical Computer Science 318, 85 (2020).

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

[3] Selma Dündar-Coecke, Lia Yeh, Caterina Puca, Sieglinde M.-L. Pfaendler, Muhammad Hamza Waseem, Thomas Cervoni, Aleks Kissinger, Stefano Gogioso, and Bob Coecke, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 21 (2023) ISBN:979-8-3503-4323-6.

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

[5] Giovanni de Felice and Bob Coecke, "Quantum Linear Optics via String Diagrams", Electronic Proceedings in Theoretical Computer Science 394, 83 (2023).

[6] Nicholas Chancellor, Aleks Kissinger, Stefan Zohren, Joschka Roffe, and Dominic Horsman, "Graphical structures for design and verification of quantum error correction", Quantum Science and Technology 8 4, 045028 (2023).

[7] Yuxiang Liu, Zaichen Zhang, Yi Hu, Fanxu Meng, Tian Luan, Xianchao Zhang, and Xutao Yu, "Practical circuit optimization algorithm for quantum simulation based on template matching", Quantum Information Processing 23 2, 45 (2024).

[8] Boldizsár Poór, Quanlong Wang, Razin A. Shaikh, Lia Yeh, Richie Yeung, and Bob Coecke, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 1 (2023) ISBN:979-8-3503-3587-3.

[9] Hector Miller-Bakewell, "Finite Verification of Infinite Families of Diagram Equations", Electronic Proceedings in Theoretical Computer Science 318, 27 (2020).

[10] 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).

[11] Tyler Leblond, Ryan S. Bennink, Justin G. Lietz, and Christopher M. Seck, Proceedings of the SC '23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis 1426 (2023) ISBN:9798400707858.

[12] 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 4, 041030 (2020).

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

[14] Joseph Collins and Ross Duncan, "Hopf-Frobenius Algebras and a Simpler Drinfeld Double", Electronic Proceedings in Theoretical Computer Science 318, 150 (2020).

[15] Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering, and Sal Wolffs, "Completeness of the ZH-calculus", Compositionality 5, 5 (2023).

[16] Alejandro Villoria, Henning Basold, and Alfons Laarman, Lecture Notes in Computer Science 14574, 121 (2024) ISBN:978-3-031-57227-2.

[17] Craig Gidney, "A Pair Measurement Surface Code on Pentagons", Quantum 7, 1156 (2023).

[18] 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).

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

[20] Dong-Xiao Quan, Xiao-Jie Lü, and Wen-Fei Zhang, "Structure design and logical CNOT implementation of multi-logical-qubits surface code", Acta Physica Sinica 73 4, 040304 (2024).

[21] Tuomas Laakkonen, Konstantinos Meichanetzidis, and John van de Wetering, "Picturing Counting Reductions with the ZH-Calculus", Electronic Proceedings in Theoretical Computer Science 384, 89 (2023).

[22] John H. Selby, Carlo Maria Scandolo, and Bob Coecke, "Reconstructing quantum theory from diagrammatic postulates", Quantum 5, 445 (2021).

[23] Augustin Borgna and Rafael Romero, "Encoding High-level Quantum Programs as SZX-diagrams", Electronic Proceedings in Theoretical Computer Science 394, 141 (2023).

[24] Boldizsár Poór, Robert I. Booth, Titouan Carette, John van de Wetering, and Lia Yeh, "The Qupit Stabiliser ZX-travaganza: Simplified Axioms, Normal Forms and Graph-Theoretic Simplification", Electronic Proceedings in Theoretical Computer Science 384, 220 (2023).

[25] Héctor Bombín, Chris Dawson, Ryan V. Mishmash, Naomi Nickerson, Fernando Pastawski, and Sam Roberts, "Logical Blocks for Fault-Tolerant Topological Quantum Computation", PRX Quantum 4 2, 020303 (2023).

[26] Filipa C R Peres, Rafael Wagner, and Ernesto F Galvão, "Non-stabilizerness and entanglement from cat-state injection", New Journal of Physics 26 1, 013051 (2024).

[27] Fatimah Rita Ahmadi and Aleks Kissinger, "The ZX-calculus as a language for topological quantum computation", Journal of Physics A: Mathematical and Theoretical 56 41, 415301 (2023).

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

[29] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[30] Craig Gidney and Austin G. Fowler, "Efficient magic state factories with a catalyzed|CCZ⟩to2|T⟩transformation", Quantum 3, 135 (2019).

[31] Christophe Vuillot, Lingling Lao, Ben Criger, Carmen García Almudéver, Koen Bertels, and Barbara M. Terhal, "Code deformation and lattice surgery are gauge fixing", New Journal of Physics 21 3, 033028 (2019).

[32] Craig Gidney and Austin G. Fowler, "Flexible layout of surface code computations using AutoCCZ states", arXiv:1905.08916, (2019).

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

[34] Renaud Vilmart, "A Near-Optimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics", arXiv:1812.09114, (2018).

[35] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart, "A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum Mechanics", arXiv:1705.11151, (2017).

[36] 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, (2021).

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

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

[39] Craig Gidney, Michael Newman, Peter Brooks, and Cody Jones, "Yoked surface codes", arXiv:2312.04522, (2023).

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

[41] Renaud Vilmart, "A ZX-Calculus with Triangles for Toffoli-Hadamard, Clifford+T, and Beyond", arXiv:1804.03084, (2018).

[42] Bob Coecke, "Compositionality as we see it, everywhere around us", arXiv:2110.05327, (2021).

[43] Richard D. P. East, Pierre Martin-Dussaud, and John Van de Wetering, "Spin-networks in the ZX-calculus", arXiv:2111.03114, (2021).

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

[45] Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart, "Completeness of Graphical Languages for Mixed States Quantum Mechanics", arXiv:1902.07143, (2019).

[46] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart, "Diagrammatic Reasoning beyond Clifford+T Quantum Mechanics", arXiv:1801.10142, (2018).

[47] Niel de Beaudrap, "Well-tempered ZX and ZH Calculi", arXiv:2006.02557, (2020).

[48] Bob Coecke, Stefano Gogioso, and John H. Selby, "The time-reverse of any causal theory is eternal noise", arXiv:1711.05511, (2017).

[49] Bob Coecke and Quanlong Wang, "ZX-Rules for 2-qubit Clifford+T Quantum Circuits", arXiv:1804.05356, (2018).

[50] Bob Coecke, "Basic ZX-calculus for students and professionals", arXiv:2303.03163, (2023).

[51] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart, "A Generic Normal Form for ZX-Diagrams and Application to the Rational Angle Completeness", arXiv:1805.05296, (2018).

[52] Quanlong Wang, "Completeness of the ZX-calculus", arXiv:2209.14894, (2022).

[53] 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, (2019).

[54] Renaud Vilmart, "Quantum Multiple-Valued Decision Diagrams in Graphical Calculi", arXiv:2107.01186, (2021).

[55] Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart, "Completeness of the ZX-Calculus", arXiv:1903.06035, (2019).

[56] Augustin Borgna and Rafael Romero, "Encoding High-level Quantum Programs as SZX-diagrams", arXiv:2206.09376, (2022).

[57] Stefano Gogioso and Subhayan Roy Moulik, "Purification and time-reversal deny entanglement in LOCC-distinguishable orthonormal bases", arXiv:1902.00316, (2019).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-19 05:20:31) and SAO/NASA ADS (last updated successfully 2024-04-19 05:20:32). The list may be incomplete as not all publishers provide suitable and complete citation data.