A graph-based formalism for surface codes and twists

Rahul Sarkar; Theodore J. Yoder

doi:10.22331/q-2024-07-18-1416

A graph-based formalism for surface codes and twists

Rahul Sarkar¹ and Theodore J. Yoder²

¹Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA 94305
²IBM T.J. Watson Research Center, Yorktown Heights, NY

Published:	2024-07-18, volume 8, page 1416
Eprint:	arXiv:2101.09349v4
Doi:	https://doi.org/10.22331/q-2024-07-18-1416
Citation:	Quantum 8, 1416 (2024).

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

Abstract

Twist defects in surface codes can be used to encode more logical qubits, improve the code rate, and implement logical gates. In this work we provide a rigorous formalism for constructing surface codes with twists generalizing the well-defined homological formalism introduced by Kitaev for describing CSS surface codes. In particular, we associate a surface code to $any$ graph $G$ embedded on $any$ 2D-manifold, in such a way that (1) qubits are associated to the vertices of the graph, (2) stabilizers are associated to faces, (3) twist defects are associated to odd-degree vertices. In this way, we are able to reproduce the variety of surface codes, with and without twists, in the literature and produce new examples. We also calculate and bound various code properties such as the rate and distance in terms of topological graph properties such as genus, systole, and face-width.

Featured image: Stabilizers and logical operators in a surface code with twist defects.

► BibTeX data

@article{Sarkar2024graphbasedformalism,
  doi = {10.22331/q-2024-07-18-1416},
  url = {https://doi.org/10.22331/q-2024-07-18-1416},
  title = {A graph-based formalism for surface codes and twists},
  author = {Sarkar, Rahul and Yoder, Theodore J.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1416},
  month = jul,
  year = {2024}
}

► References

[1] Alexei Yu. Kitaev. ``Fault-tolerant quantum computation by anyons''. Annals of Physics 303, 2–30 (2003). doi: 10.1016/s0003-4916(02)00018-0.
https://doi.org/10.1016/s0003-4916(02)00018-0

[2] Sergey Bravyi, David Poulin, and Barbara Terhal. ``Tradeoffs for reliable quantum information storage in 2D systems''. Physical Review Letters 104, 050503 (2010). doi: 10.1103/physrevlett.104.050503.
https://doi.org/10.1103/physrevlett.104.050503

[3] Héctor Bombín and Miguel A. Martin-Delgado. ``Optimal resources for topological two-dimensional stabilizer codes: Comparative study''. Physical Review A 76, 012305 (2007). doi: 10.1103/physreva.76.012305.
https://doi.org/10.1103/physreva.76.012305

[4] Héctor Bombín. ``Topological order with a twist: Ising anyons from an abelian model''. Physical Review Letters 105, 030403 (2010). doi: 10.1103/physrevlett.105.030403.
https://doi.org/10.1103/physrevlett.105.030403

[5] Alexei Kitaev and Liang Kong. ``Models for gapped boundaries and domain walls''. Communications in Mathematical Physics 313, 351–373 (2012). doi: 10.1007/s00220-012-1500-5.
https://doi.org/10.1007/s00220-012-1500-5

[6] Theodore J. Yoder and Isaac H. Kim. ``The surface code with a twist''. Quantum 1, 2 (2017). doi: 10.22331/q-2017-04-25-2.
https://doi.org/10.22331/q-2017-04-25-2

[7] Andrew J. Landahl. ``The surface code on the rhombic dodecahedron'' (2020). doi: 10.48550/arXiv.2010.06628.
https://doi.org/10.48550/arXiv.2010.06628

[8] Anirudh Krishna and David Poulin. ``Topological wormholes: Nonlocal defects on the toric code''. Physical Review Research 2, 023116 (2020). doi: 10.1103/physrevresearch.2.023116.
https://doi.org/10.1103/physrevresearch.2.023116

[9] Markus S. Kesselring, Fernando Pastawski, Jens Eisert, and Benjamin J. Brown. ``The boundaries and twist defects of the color code and their applications to topological quantum computation''. Quantum 2, 101 (2018). doi: 10.22331/q-2018-10-19-101.
https://doi.org/10.22331/q-2018-10-19-101

[10] Nicolas Delfosse. ``Tradeoffs for reliable quantum information storage in surface codes and color codes''. In 2013 IEEE International Symposium on Information Theory. Pages 917–921. IEEE (2013). doi: 10.1109/isit.2013.6620360.
https://doi.org/10.1109/isit.2013.6620360

[11] Nikolas P. Breuckmann and Barbara M. Terhal. ``Constructions and noise threshold of hyperbolic surface codes''. IEEE transactions on Information Theory 62, 3731–3744 (2016). doi: 10.1109/tit.2016.2555700.
https://doi.org/10.1109/tit.2016.2555700

[12] Xiao-Gang Wen. ``Quantum orders in an exact soluble model''. Phys. Rev. Lett. 90, 016803 (2003). doi: 10.1103/PhysRevLett.90.016803.
https://doi.org/10.1103/PhysRevLett.90.016803

[13] Alexei Kitaev. ``Anyons in an exactly solved model and beyond''. Annals of Physics 321, 2–111 (2006). doi: 10.1016/j.aop.2005.10.005.
https://doi.org/10.1016/j.aop.2005.10.005

[14] Sergey Bravyi, Matthias Englbrecht, Robert König, and Nolan Peard. ``Correcting coherent errors with surface codes''. NPJ Quantum Information 4, 55 (2018). doi: 10.1038/s41534-018-0106-y.
https://doi.org/10.1038/s41534-018-0106-y

[15] Alexey A. Kovalev and Leonid P. Pryadko. ``Improved quantum hypergraph-product LDPC codes''. In 2012 IEEE International Symposium on Information Theory Proceedings. Pages 348–352. IEEE (2012). doi: 10.1109/isit.2012.6284206.
https://doi.org/10.1109/isit.2012.6284206

[16] Nikolas P. Breuckmann, Christophe Vuillot, Earl Campbell, Anirudh Krishna, and Barbara M. Terhal. ``Hyperbolic and semi-hyperbolic surface codes for quantum storage''. Quantum Science and Technology 2, 035007 (2017). doi: 10.1088/2058-9565/aa7d3b.
https://doi.org/10.1088/2058-9565/aa7d3b

[17] Nikolas P. Breuckmann. ``Homological quantum codes beyond the toric code''. PhD thesis. RWTH Aachen University. (2017). doi: 10.18154/RWTH-2018-01100.
https://doi.org/10.18154/RWTH-2018-01100

[18] Sagar Vijay, Timothy H. Hsieh, and Liang Fu. ``Majorana fermion surface code for universal quantum computation''. Physical Review X 5, 041038 (2015). doi: 10.1103/physrevx.5.041038.
https://doi.org/10.1103/physrevx.5.041038

[19] Alexey A. Kovalev, Ilya Dumer, and Leonid P. Pryadko. ``Design of additive quantum codes via the code-word-stabilized framework''. Physical Review A 84, 062319 (2011). doi: 10.1103/PhysRevA.84.062319.
https://doi.org/10.1103/PhysRevA.84.062319

[20] Saul Stahl. ``The embeddings of a graph—a survey''. Journal of Graph Theory 2, 275–298 (1978). doi: 10.1002/jgt.3190020402.
https://doi.org/10.1002/jgt.3190020402

[21] Saul Stahl. ``Generalized embedding schemes''. Journal of Graph Theory 2, 41–52 (1978). doi: 10.1002/jgt.3190020106.
https://doi.org/10.1002/jgt.3190020106

[22] Marcus Schaefer. ``Crossing numbers of graphs''. CRC Press. (2018). First edition. doi: 10.1201/9781315152394.
https://doi.org/10.1201/9781315152394

[23] John Lee. ``Introduction to topological manifolds''. Volume 202 of Graduate Texts in Mathematics. Springer Science & Business Media. (2011). doi: 10.1007/978-1-4419-7940-7.
https://doi.org/10.1007/978-1-4419-7940-7

[24] John Lee. ``Introduction to smooth manifolds''. Volume 218 of Graduate Texts in Mathematics. Springer Science & Business Media. (2012). Second edition. doi: 10.1007/978-1-4419-9982-5.
https://doi.org/10.1007/978-1-4419-9982-5

[25] Tibor Radó. ``Über den Begriff der Riemannschen Fläche''. Acta Litt. Sci. Szeged 2, 101–121 (1925). url: https://zbmath.org/51.0273.01.
https://zbmath.org/51.0273.01

[26] Herbert Seifert and William Threlfall. ``Seifert and Threlfall: A textbook of topology''. Volume 89 of Pure and Applied Mathematics. Elsevier. (1980). doi: 10.1016/s0079-8169(08)x6140-9.
https://doi.org/10.1016/s0079-8169(08)x6140-9

[27] George K. Francis and Jeffrey R. Weeks. ``Conway's ZIP proof''. The American Mathematical Monthly 106, 393–399 (1999). doi: 10.1080/00029890.1999.12005061.
https://doi.org/10.1080/00029890.1999.12005061

[28] Roman Nedela and Martin Škoviera. ``Regular maps on surfaces with large planar width''. European Journal of Combinatorics 22, 243–262 (2001). doi: 10.1006/eujc.2000.0441.
https://doi.org/10.1006/eujc.2000.0441

[29] Jozef Širáň. ``Triangle group representations and their applications to graphs and maps''. Discrete Mathematics 229, 341–358 (2001). doi: 10.1016/s0012-365x(00)00215-6.
https://doi.org/10.1016/s0012-365x(00)00215-6

[30] Reinhard Diestel. ``Graph theory''. Volume 173 of Graduate Texts in Mathematics. Springer Berlin, Heidelberg. (2000). Fifth edition. doi: 10.1007/978-3-662-53622-3.
https://doi.org/10.1007/978-3-662-53622-3

[31] Jonathan L Gross and Thomas W Tucker. ``Topological graph theory''. Dover books on mathematics. Dover Publications. (2001).

[32] Allen Hatcher. ``Algebraic topology''. Cambridge University Press. (2002).

[33] Sergio Cabello and Bojan Mohar. ``Finding shortest non-separating and non-contractible cycles for topologically embedded graphs''. Discrete & Computational Geometry 37, 213–235 (2007). doi: 10.1007/s00454-006-1292-5.
https://doi.org/10.1007/s00454-006-1292-5

[34] Glen E. Bredon. ``Topology and geometry''. Volume 139 of Graduate Texts in Mathematics. Springer Science & Business Media. (2013). First edition. doi: 10.1007/978-1-4757-6848-0.
https://doi.org/10.1007/978-1-4757-6848-0

[35] Sergey Bravyi, Barbara M. Terhal, and Bernhard Leemhuis. ``Majorana fermion codes''. New Journal of Physics 12, 083039 (2010). doi: 10.1088/1367-2630/12/8/083039.
https://doi.org/10.1088/1367-2630/12/8/083039

[36] Sagar Vijay and Liang Fu. ``Quantum error correction for complex and Majorana fermion qubits'' (2017). doi: 10.48550/arXiv.1703.00459.
https://doi.org/10.48550/arXiv.1703.00459

[37] Alexei Yu. Kitaev. ``Unpaired Majorana fermions in quantum wires''. Physics-Uspekhi 44, 131 (2001). doi: 10.1070/1063-7869/44/10S/S29.
https://doi.org/10.1070/1063-7869/44/10S/S29

[38] Rahul Sarkar and Ewout van den Berg. ``On sets of maximally commuting and anticommuting Pauli operators''. Research in the Mathematical Sciences 8, 14 (2021). doi: 10.1007/s40687-020-00244-1.
https://doi.org/10.1007/s40687-020-00244-1

[39] Sergey B. Bravyi and Alexei Yu. Kitaev. ``Quantum codes on a lattice with boundary'' (1998). doi: 10.48550/arXiv.quant-ph/9811052.
https://doi.org/10.48550/arXiv.quant-ph/9811052
arXiv:quant-ph/9811052

[40] Michael H. Freedman and David A. Meyer. ``Projective plane and planar quantum codes''. Foundations of Computational Mathematics 1, 325–332 (2001). doi: 10.1007/s102080010013.
https://doi.org/10.1007/s102080010013

[41] Jonas T. Anderson. ``Homological stabilizer codes''. Annals of Physics 330, 1–22 (2013). doi: 10.1016/j.aop.2012.11.007.
https://doi.org/10.1016/j.aop.2012.11.007

[42] Peter W. Shor. ``Scheme for reducing decoherence in quantum computer memory''. Physical Review A 52, R2493–R2496 (1995). doi: 10.1103/PhysRevA.52.R2493.
https://doi.org/10.1103/PhysRevA.52.R2493

[43] Mark De Berg, Marc Van Kreveld, Mark Overmars, and Otfried Schwarzkopf. ``Computational geometry''. Springer. (1997). First edition. doi: 10.1007/978-3-662-03427-9.
https://doi.org/10.1007/978-3-662-03427-9

[44] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. ``Topological quantum memory''. Journal of Mathematical Physics 43, 4452–4505 (2002). doi: 10.1063/1.1499754.
https://doi.org/10.1063/1.1499754

[45] Maissam Barkeshli and Michael Freedman. ``Modular transformations through sequences of topological charge projections''. Physical Review B 94, 165108 (2016). doi: 10.1103/PhysRevB.94.165108.
https://doi.org/10.1103/PhysRevB.94.165108

[46] Joseph Douglas Horton. ``A polynomial-time algorithm to find the shortest cycle basis of a graph''. SIAM Journal on Computing 16, 358–366 (1987). doi: 10.1137/0216026.
https://doi.org/10.1137/0216026

[47] Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn, and Romeo Rizzi. ``Breaking the ${O} (m^ 2 n)$ barrier for minimum cycle bases''. In Algorithms - ESA 2009. Pages 301–312. Springer Berlin Heidelberg (2009). doi: 10.1007/978-3-642-04128-0_28.
https://doi.org/10.1007/978-3-642-04128-0_28

[48] Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna Paluch. ``A faster algorithm for minimum cycle basis of graphs''. In International Colloquium on Automata, Languages, and Programming. Pages 846–857. Springer Berlin Heidelberg (2004). doi: 10.1007/978-3-540-27836-8_71.
https://doi.org/10.1007/978-3-540-27836-8_71

[49] Kurt Mehlhorn and Dimitrios Michail. ``Minimum cycle bases: Faster and simpler''. ACM Transactions on Algorithms (TALG) 6, 8 (2010). doi: 10.1145/1644015.1644023.
https://doi.org/10.1145/1644015.1644023

[50] The GAP Group. ``GAP – Groups, Algorithms, and Programming, Version 4.11.0''. (2020). url: https://www.gap-system.org.
https://www.gap-system.org

[51] Friedrich Rober. ``LINS – a gap package''. (2020). url: https://github.com/FriedrichRober/LINS.
https://github.com/FriedrichRober/LINS

[52] Markus Grassl. ``Bounds on the minimum distance of linear codes and quantum codes''. Online available at http://www.codetables.de (2007). Accessed on 2020-11-03.
http://www.codetables.de

[53] Luca Trevisan. ``Inapproximability of combinatorial optimization problems''. In Paradigms of Combinatorial Optimization. Chapter 13, pages 381–434. John Wiley & Sons, Ltd (2014). doi: 10.1002/9781119005353.ch13.
https://doi.org/10.1002/9781119005353.ch13

[54] ChunJun Cao, Michael J Gullans, Brad Lackey, and Zitao Wang. ``Quantum Lego expansion pack: Enumerators from tensor networks'' (2023). doi: 10.48550/arXiv.2308.05152.
https://doi.org/10.48550/arXiv.2308.05152

[55] Héctor Bombín. ``Structure of 2D topological stabilizer codes''. Communications in Mathematical Physics 327, 387–432 (2014). doi: 10.1007/s00220-014-1893-4.
https://doi.org/10.1007/s00220-014-1893-4

[56] Jeongwan Haah. ``Algebraic methods for quantum codes on lattices''. Revista Colombiana de Matemáticas 50, 299–349 (2016). doi: 10.15446/recolma.v50n2.62214.
https://doi.org/10.15446/recolma.v50n2.62214

[57] Ben Criger and Barbara Terhal. ``Noise thresholds for the [4,2,2]-concatenated toric code''. Quantum Information & Computation 16, 1261–1281 (2016). doi: 10.26421/qic16.15-16-1.
https://doi.org/10.26421/qic16.15-16-1

[58] Daniel Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. (1997). doi: 10.7907/rzr7-dt72.
https://doi.org/10.7907/rzr7-dt72

[59] Pascual Jordan and Eugene Paul Wigner. ``Über das Paulische Äquivalenzverbot''. Zeitschrift für Physik 47, 631–651 (1928). doi: 10.1007/BF01331938.
https://doi.org/10.1007/BF01331938

[60] Pavel Hrubeš. ``On families of anticommuting matrices''. Linear Algebra and its Applications 493, 494–507 (2016). doi: 10.1016/j.laa.2015.12.015.
https://doi.org/10.1016/j.laa.2015.12.015

[61] Henry S Warren. ``Hacker's delight''. Addison-Wesley Professional. (2012). 2nd edition.

Cited by

[1] Qian Xu, Nam Mannucci, Alireza Seif, Aleksander Kubica, Steven T. Flammia, and Liang Jiang, "Tailored XZZX codes for biased noise", Physical Review Research 5 1, 013035 (2023).

[2] Andrew J. Landahl and Benjamin C. A. Morrison, "Logical fermions for fault-tolerant quantum simulation", arXiv:2110.10280, (2021).

[3] Rahul Sarkar and Theodore J. Yoder, "The qudit Pauli group: non-commuting pairs, non-commuting sets, and structure theorems", Quantum 8, 1307 (2024).

[4] Lukas Voss, Sim Jian Xian, Tobias Haug, and Kishor Bharti, "Multivariate Bicycle Codes", arXiv:2406.19151, (2024).

[5] Kao-Yueh Kuo and Ching-Yi Lai, "Comparison of 2D topological codes and their decoding performances", arXiv:2202.06612, (2022).

[6] Simon Burton, Elijah Durso-Sabina, and Natalie C. Brown, "Genons, Double Covers and Fault-tolerant Clifford Gates", arXiv:2406.09951, (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2024-09-08 04:20:40). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-09-08 04:20:39).

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.