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", arXiv:1904.12817, Electronic Proceedings in Theoretical Computer Science 318, 85 (2020).

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

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

[4] John H. Selby, Carlo Maria Scandolo, and Bob Coecke, "Reconstructing quantum theory from diagrammatic postulates", arXiv:1802.00367.

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

[6] Craig Gidney and Austin G. Fowler, "Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation", arXiv:1812.01238.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[23] Niel de Beaudrap, "Well-tempered ZX and ZH calculi", arXiv:2006.02557.

[24] Michael Hanks, Marta P. Estarellas, William J. Munro, and Kae Nemoto, "Efficient compression of quantum braided circuits", arXiv:1912.11503.

The above citations are from Crossref's cited-by service (last updated successfully 2020-10-28 00:05:00) and SAO/NASA ADS (last updated successfully 2020-10-28 00:05:01). The list may be incomplete as not all publishers provide suitable and complete citation data.