Algebraic Methods for Quantum Codes on Lattices

This is a note from a series of lectures at Encuentro Colombiano de Computación Cuántica, Universidad de los Andes, Bogotá, Colombia, 2015. The purpose is to introduce additive quantum error correcting codes, with emphasis on the use of binary representation of Pauli matrices and modules over a translation group algebra. The topics include symplectic vector spaces, Cliord group, cleaning lemma, an error correcting criterion, entanglement spectrum, implications of the locality of stabilizer group generators, and the classication of translation-invariant one-dimensional additive codes and two-dimensional CSS codes with large code distances. In particular, we describe an algorithm to find a Cliord quantum circuit (CNOTs) to transform any two-dimensional translation-invariant CSS code on qudits of a prime dimension with code distance being the linear system size, into a tensor product of finitely many copies of the qudit toric code and a product state. Thus, the number of embedded toric codes is the complete invariant of these CSS codes under local Cliord circuits.

DOI: https://doi.org/10.15446/recolma.v50n2.62214

Jeongwan Haah

Massachusetts Institute of Technology, Cambridge, Massachusetts, USA. jwhaah@microsoft.com

---

Abstract

This is a note from a series of lectures at Encuentro Colombiano de Computación Cuántica, Universidad de los Andes, Bogotá, Colombia, 2015. The purpose is to introduce additive quantum error correcting codes, with emphasis on the use of binary representation of Pauli matrices and modules over a translation group algebra. The topics include symplectic vector spaces, Clifford group, cleaning lemma, an error correcting criterion, entanglement spectrum, implications of the locality of stabilizer group generators, and the classification of translation-invariant one-dimensional additive codes and two-dimensional CSS codes with large code distances. In particular, we describe an algorithm to find a Clifford quantum circuit (CNOTs) to transform any two-dimensional translation-invariant CSS code on qudits of a prime dimension with code distance being the linear system size, into a tensor product of finitely many copies of the qudit toric code and a product state. Thus, the number of embedded toric codes is the complete invariant of these CSS codes under local Clifford circuits.

Keywords: quantum stabilizer codes, additive codes, symplectic codes, Laurent polynomial ring, toric code, Clifford circuit.

---

Mathematics Subject Classification: 81P70, 81R05, 12Y05.

---

Texto completo disponible en PDF

---

References

[1] Morou Amidou and Ihsen Yengui, An algorithm for unimodular completion over laurent polynomial rings, Linear Algebra and its Applications 429 (2008), no. 7, 1687-1698.

[2] Pablo Arrighi, Vincent Nesme, and Reinhard Werner, Unitarity plus causality implies localizability, 2007.

[3] M. F. Atiyah and I. G. MacDonald, Introduction to commutative algebra, 1969.

[4] Bojko Bakalov and Alexander Kirillov Jr., Lectures on tensor categories and modular functors, University Lecture Series 21 (2001).

[5] Héctor Bombín, Structure of 2D topological stabilizer codes, Commun. Math. Phys. 327 (2014), 387-432.

[6] Sergey Bravyi, Bernhard Leemhuis, and Barbara M. Terhal, Topological order in an exactly solvable 3D spin model, Annals of Physics 326 (2011), no. 4, 839-866.

[7] Sergey Bravyi and Barbara Terhal, A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes, New J. Phys. 11 (2009), 043029.

[8] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, Quantum error correction and orthogonal geometry, Phys. Rev. Lett. 78 (1997), 405-408.

[9] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, Quantum error correction via codes over gf(4), Information Theory, IEEE Transactions on 44 (1998), no. 4, 1369-1387.

[10] A. R. Calderbank and Peter W. Shor, Good quantum error-correcting codes exist, Phys. Rev. A 54 (1996), no. 2, 1098-1105.

[11] Claudio Chamon, Quantum glassiness, Phys. Rev. Lett. 94 (2005), 040402.

[12] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill, Topological quantum memory, J. Math. Phys. 43 (2002), 4452-4505.

[13] J. M. Farinholt, An ideal characterization of the clifford operators, Phys. A: Math. Theor. 47 (2014), 305303.

[14] David Fattal, Toby S. Cubitt, Yoshihisa Yamamoto, Sergey Bravyi, and Isaac L. Chuang, Entanglement in the stabilizer formalism, (2004).

[15] Daniel Gottesman, A class of quantum error-correcting codes saturating the quantum hamming bound, Phys. Rev. A 54 (1996), 1862.

[16] Daniel Gottesman, Fault-tolerant quantum computation with higher-dimensional systems, Quantum Computing and Quantum Communications (ColinP. Williams, ed.), Lecture Notes in Computer Science 1509 (1999), 302-313, Springer Berlin Heidelberg.

[17] M. Grassl and M. Roetteler, Non-catastrophic encoders and encoder inverses for quantum convolutional codes, vol. 21, Information Theory, 2006 IEEE International Symposium on, 2016, pp. 1109-1113.

[18] Jeongwan Haah, Local stabilizer codes in three dimensions without string logical operators, Phys. Rev. A 83 (2011), no. 4, 042330.

[19] Jeongwan Haah, Commuting Pauli Hamiltonians as maps between free modules, Commun. Math. Phys. 324 (2013), 351-399.

[20] Jeongwan Haah, An invariant of topologically ordered states under local unitary transformations, Communications in Mathematical Physics 342 (2016), no. 3, 771-801.

[21] Jeongwan Haah and John Preskill, Logical operator tradeoff for local quantum codes, Phys. Rev. A 86 (2012), 032308.

[22] Alioscia Hamma, Radu Ionicioiu, and Paolo Zanardi, Bipartite entanglement and entropic boundary law in lattice spin systems, Phys. Rev. A 71 (2005), 022315.

[23] Allen Hatcher, Algebraic topology, Cambridge University Press, 2002.

[24] Isaac H. Kim, 3d local qupit quantum code without string logical operator, (2012).

[25] Alexei Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics 303 (2003), 2-30.

[26] Alexei Kitaev, Anyons in an exactly solved model and beyond, Annals of Physics 321 (2006), 2-111.

[27] A. Klappenecker and M. Roetteler, Beyond stabilizer codes ii: Clifford codes, IEEE Transactions on Information Theory 48 (2002), no. 8, 2396-2399.

[28] Emanuel Knill and Raymond Laflamme, Theory of quantum error-correcting codes, Phys. Rev. A 55 (1997), 900-911.

[29] Serge Lang, Algebra, revised 3rd ed., Springer, 2002.

[30] Michael Levin and Xiao-Gang Wen, Fermions, strings, and gauge fields in lattice spin models, Phys. Rev. B 67 (2003), 245316.

[31] Noah Linden, abd Mary Beth Ruskai Frantisek Matus, and Andreas Winter, The Quantum Entropy Cone of Stabiliser States, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013) (Dagstuhl, Germany) (Simone Severini and Fernando Brandao, eds.), Leibniz International Proceedings in Informatics (LIPIcs) 22 (2013), 270-284, Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik.

[32] H. Park and C. Woodburn, An algorithmic proof of Suslin's stability theorem over polynomial rings, Journal of Algebra 178 (1995), 277-298.

[33] Hyungju Park, Symbolic computation and signal processing, Journal of Symbolic Computation 37 (2004), no. 2, 209-226.

[34] E. M. Rains, Nonbinary quantum codes, Information Theory, IEEE Transactions on 45 (1999), no. 6, 1827-1832.

[35] N. Read and Subir Sachdev, Large-n expansion for frustrated quantum antiferromagnets, Phys. Rev. Lett. 66 (1991), 1773-1776.

[36] Peter W. Shor, Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A 52 (1995), R2493-R2496.

[37] Peter W. Shor, Fault-tolerant quantum computation, Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on (1996), 56-65.

[38] Andrew Steane, Multiple particle interference and quantum error correction, Proc. Roy. Soc. Lond. A 452 (1996), 2551.

[39] Sagar Vijay, Jeongwan Haah, and Liang Fu, A new kind of topological quantum order: A dimensional hierarchy of quasiparticles built from stationary excitations, Phys. Rev. B 92 (2015), 235136.

[40] Sagar Vijay, Jeongwan Haah, and Liang Fu, Fracton topological order, generalized lattice gauge theory and duality, (2016).

[41] Beni Yoshida, Exotic topological order in fractal spin liquids, Phys. Rev. B 88 (2013), 125122.

[42] Beni Yoshida and Isaac L. Chuang, Framework for classifying logical operators in stabilizer codes, Phys. Rev. A 81 (2010), 052302.

Recibido: julio de 2016 Aceptado: noviembre de 2016