Quantum Codes of Maximal Distance and Highly Entangled Subspaces

Felix Huber1,2,3 and Markus Grassl4,5

1ICFO - The Institute of Photonic Sciences, 08860 Castelldefels (Barcelona), Spain
2Institut für Theoretische Physik, Universität zu Köln, 50937 Köln, Germany
3Naturwissenschaftlich-Technische Fakultät, Universität Siegen, 57068 Siegen, Germany
4International Centre for Theory of Quantum Technologies, University of Gdansk, 80-308 Gdańsk, Poland
5Max Planck Institute for the Science of Light, 91058 Erlangen, Germany

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

Abstract

We present new bounds on the existence of general quantum maximum distance separable codes (QMDS): the length $n$ of all QMDS codes with local dimension $D$ and distance $d \geq 3$ is bounded by $n \leq D^2 + d - 2$. We obtain their weight distribution and present additional bounds that arise from Rains' shadow inequalities. Our main result can be seen as a generalization of bounds that are known for the two special cases of stabilizer QMDS codes and absolutely maximally entangled states, and confirms the quantum MDS conjecture in the special case of distance-three codes. As the existence of QMDS codes is linked to that of highly entangled subspaces (in which every vector has uniform $r$-body marginals) of maximal dimension, our methods directly carry over to address questions in multipartite entanglement.

Quantum error-correcting codes are essential to protect quantum information against decoherence and interaction with the environment. While this interaction creates undesired entanglement between the system and its environment, it is again entanglement among the individual subsystems composing the code that allows to fight decoherence.

We investigate bounds on the parameters of the code that relate to the entanglement in the code, as manifested by maximally mixed marginals of the logical states. The first bound is the quantum Singleton bound, which has already been known very early in the theory of quantum error-correction. It is independent of the local dimension and can always be reached when the local dimension is sufficiently large. The corresponding codes are known as quantum maximum distance separable (QMDS) codes.

In this paper, we derive additional bounds on the existence of QMDS codes. Crucially, they are valid for all QMDS codes, including codes beyond the stabilizer formalism. We show that another characteristic property, the weight enumerator, is also independent of whether the QMDS code is of the stabilizer type or not.

In many cases the known stabilizer constructions match our upper bounds. It it surprising that these combinatorial, inherently classical constructions yield optimal codes also in the quantum case, dealing with arbitrary subspaces of complex vector spaces. We conclude with the open question whether or not there are QMDS codes which do not arise from classical MDS codes.

► BibTeX data

► References

[1] P. W. Shor, ``Scheme for reducing decoherence in quantum computer memory,'' Phys. Rev. A 52, 2493(R) (1995).
https:/​/​doi.org/​10.1103/​PhysRevA.52.R2493

[2] A. M. Steane, ``Error Correcting Codes in Quantum Theory,'' Phys. Rev. Lett. 77, 793–797 (1996).
https:/​/​doi.org/​10.1103/​PhysRevLett.77.793

[3] E. Knill and R. Laflamme, ``Theory of quantum error-correcting codes,'' Phys. Rev. A 55, 900–911 (1997).
https:/​/​doi.org/​10.1103/​PhysRevA.55.900

[4] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, ``Mixed-state entanglement and quantum error correction,'' Phys. Rev. A 54, 3824 (1996).
https:/​/​doi.org/​10.1103/​PhysRevA.54.3824

[5] B. Schumacher and M. A. Nielsen, ``Quantum data processing and error correction,'' Phys. Rev. A 54, 2629–2635 (1996).
https:/​/​doi.org/​10.1103/​PhysRevA.54.2629

[6] A. R. Calderbank, E. M. Rains, P. M. Shor, and N. J. A. Sloane, ``Quantum error correction via codes over GF(4),'' IEEE Trans. Inf. Theory 44, 1369 (1998).
https:/​/​doi.org/​10.1109/​18.681315

[7] Dennis, A. Kitaev, A. Landahl, and J. Preskill, ``Topological quantum memory,'' J. Math. Phys. 43, 4452–4505 (2002).
https:/​/​doi.org/​10.1063/​1.1499754

[8] H. Bombin and M. A. Martin-Delgado, ``Topological Quantum Distillation,'' Phys. Rev. Lett. 97, 180501 (2006).
https:/​/​doi.org/​10.1103/​PhysRevLett.97.180501

[9] J. Tillich and G. Zémor, ``Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength,'' IEEE Trans. Inf. Theory 60, 1193–1202 (2014).
https:/​/​doi.org/​10.1109/​TIT.2013.2292061

[10] M. B. Hastings and S. Bravyi, ``Homological Product Codes,'' in Proc. of the 46th ACM Symposium on Theory of Computing (2014) pp. 273–282.
https:/​/​doi.org/​10.1145/​2591796.2591870

[11] B. M. Terhal, ``Quantum error correction for quantum memories,'' Rev. Mod. Phys. 87, 307–346 (2015).
https:/​/​doi.org/​10.1103/​RevModPhys.87.307

[12] E. T. Campbell, B. M. Terhal, and V. Christophe, ``Roads towards fault-tolerant universal quantum computation,'' Nature 549, 172 (2017).
https:/​/​doi.org/​10.1038/​nature23460

[13] A. Ashikhmin and S. Litsyu, ``Upper bounds on the size of quantum codes,'' IEEE Trans. Inf. Theory 45, 1206–1215 (1999).
https:/​/​doi.org/​10.1109/​18.761270

[14] D. Chandra, Z. Babar, H. V. Nguyen, D. Alanis, P. Botsinis, S. X. Ng, and L. Hanzo, ``Quantum Coding Bounds and a Closed-Form Approximation of the Minimum Distance Versus Quantum Coding Rate,'' IEEE Access 5, 11557–11581 (2017).
https:/​/​doi.org/​10.1109/​ACCESS.2017.2716367

[15] N. J. Cerf and R. Cleve, ``Information-theoretic interpretation of quantum error-correcting codes,'' Phys. Rev. A 56, 1721–1732 (1997).
https:/​/​doi.org/​10.1103/​PhysRevA.56.1721

[16] D. Gottesman, ``Lecture Notes CO639,'' available online at www.perimeterinstitute.ca/​personal/​dgottesman/​CO639-2004/​ (2004).
http:/​/​www.perimeterinstitute.ca/​personal/​dgottesman/​CO639-2004/​

[17] E. M. Rains, ``Nonbinary quantum codes,'' IEEE Trans. Inf. Theory 45, 1827 (1999a).
https:/​/​doi.org/​10.1109/​18.782103

[18] W. Dür, G. Vidal, and J. I. Cirac, ``Three qubits can be entangled in two inequivalent ways,'' Phys. Rev. A 62, 062314 (2000).
https:/​/​doi.org/​10.1103/​PhysRevA.62.062314

[19] M. Walter, D. Gross, and J. Eisert, ``Multi-partite entanglement,'' (2017), arXiv:1612.02437.
arXiv:1612.02437

[20] I. Bengtsson and K. Życzkowski, Geometry of Quantum States: An Introduction to Quantum Entanglement, 2nd ed. (Cambridge University Press, 2017).
https:/​/​doi.org/​10.1017/​CBO9780511535048

[21] T. Cubitt, A. Montanaro, and A. Winter, ``On the dimension of subspaces with bounded Schmidt rank,'' J. Math. Phys. 49, 022107 (2008).
https:/​/​doi.org/​10.1063/​1.2862998

[22] N. Johnston, ``Non-positive-partial-transpose subspaces can be as large as any entangled subspace,'' Phys. Rev. A 87, 064302 (2013).
https:/​/​doi.org/​10.1103/​PhysRevA.87.064302

[23] J. Walgate and A. J. Scott, ``Generic local distinguishability and completely entangled subspaces,'' J. Phys. A: Math. Theor. 41, 375305 (2008).
https:/​/​doi.org/​10.1088/​1751-8113/​41/​37/​375305

[24] R. Sengupta, Arvind, and A. I. Singh, ``Entanglement properties of positive operators with ranges in completely entangled subspaces,'' Phys. Rev. A 90, 062323 (2014).
https:/​/​doi.org/​10.1103/​PhysRevA.90.062323

[25] M. Demianowicz and R. Augusiak, ``From unextendible product bases to genuinely entangled subspaces,'' Phys. Rev. A 98, 012313 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.012313

[26] M. Demianowicz and R. Augusiak, ``Entanglement of genuinely entangled subspaces and states: Exact, approximate, and numerical results,'' Phys. Rev. A 100, 062318 (2019).
https:/​/​doi.org/​10.1103/​PhysRevA.100.062318

[27] M. Demianowicz and R. Augusiak, ``An approach to constructing genuinely entangled subspaces of maximal dimension,'' Quantum Inf. Process. 19, 199 (2020).
https:/​/​doi.org/​10.1007/​s11128-020-02688-4

[28] G. Gour and N. R. Wallach, ``Entanglement of subspaces and error-correcting codes,'' Phys. Rev. A 76, 042309 (2007).
https:/​/​doi.org/​10.1103/​PhysRevA.76.042309

[29] M. Grassl, T. Beth, and M. Rötteler, ``On optimal quantum codes,'' Int. J. Quant. Inf. 2, 55 (2004).
https:/​/​doi.org/​10.1142/​S0219749904000079

[30] M. Grassl and M. Rötteler, ``Quantum MDS codes over small fields,'' in IEEE Int. Symp. Inf. Theory (ISIT 2015) (2015) pp. 1104–1108.
https:/​/​doi.org/​10.1109/​ISIT.2015.7282626

[31] G. G. L. Guardia, ``New Quantum MDS Codes,'' IEEE Trans. Inf. Theory 57, 5551–5554 (2011).
https:/​/​doi.org/​10.1109/​TIT.2011.2159039

[32] W. Helwig, Multipartite Entanglement: Transformations, Quantum Secret Sharing, Quantum Error Correction, Ph.D. thesis, University of Toronto (2014).
http:/​/​hdl.handle.net/​1807/​44114

[33] D. Joyner and J.-L. Kim, Selected Unsolved Problems in Coding Theory (Applied and Numerical Harmonic Analysis), 1st ed. (Birkhäuser Basel, 2011).
https:/​/​doi.org/​10.1007/​978-0-8176-8256-9

[34] S. Ball, ``On sets of vectors of a finite vector space in which every subset of basis size is a basis,'' J. Eur. Math. Soc. 14, 733–748 (2012).
https:/​/​doi.org/​10.4171/​JEMS/​316

[35] C. Eltschka, F. Huber, O. Gühne, and J. Siewert, ``Exponentially many entanglement and correlation constraints for multipartite quantum states,'' Phys. Rev. A 98, 052317 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.052317

[36] E. Knill, R. Laflamme, and L. Viola, ``Theory of Quantum Error Correction for General Noise,'' Phys. Rev. Lett. 84, 2525–2528 (2000).
https:/​/​doi.org/​10.1103/​PhysRevLett.84.2525

[37] D. Gottesman, ``An Introduction to Quantum Error Correction,'' in Quantum computation: A grand mathematical challenge for the twenty-first century and the millennium, ed. S. J. Lomonaco, Jr., pp. 221–235, (American Mathematical Society, 2002) arXiv:quant-ph/​0004072.
arXiv:quant-ph/0004072

[38] R. Cleve, D. Gottesman, and H.-K. Lo, ``How to share a quantum secret,'' Phys. Rev. Lett. 83, 648–651 (1999).
https:/​/​doi.org/​10.1103/​PhysRevLett.83.648

[39] P. Shor and R. Laflamme, ``Quantum Analog of the MacWilliams Identities for Classical Coding Theory,'' Phys. Rev. Lett. 78, 1600–1602 (1997).
https:/​/​doi.org/​10.1103/​PhysRevLett.78.1600

[40] E. M. Rains, ``Quantum weight enumerators,'' IEEE Trans. Inf. Theory 44, 1388–1394 (1998).
https:/​/​doi.org/​10.1109/​18.681316

[41] F. Huber, C. Eltschka, J. Siewert, and O. Gühne, ``Bounds on absolutely maximally entangled states from shadow inequalities, and the quantum MacWilliams identity,'' J. Phys. A: Math. Theor. 51, 175301 (2018).
https:/​/​doi.org/​10.1088/​1751-8121/​aaade5

[42] A. Ashikhmin and A. Barg, ``Binomial moments of the distance distribution: bounds and applications,'' IEEE Transactions on Information Theory 45, 438–452 (1999).
https:/​/​doi.org/​10.1109/​18.748994

[43] D. Gottesman, Stabilizer Codes and Quantum Error Correction, Ph.D. thesis, Caltech (1997), arXiv:quant-ph/​9705052.
arXiv:quant-ph/9705052

[44] D. Alsina and M. Razavi, ``Absolutely maximally entangled states, quantum maximum distance separable codes, and quantum repeaters,'' (2019), arXiv:1907.11253.
arXiv:1907.11253

[45] T. A. Brun and D. E. Lidar, Quantum Error Correction (Cambridge University Press, 2013).
https:/​/​doi.org/​10.1017/​CBO9781139034807

[46] A. Winter, private communication (2019).

[47] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003).
https:/​/​doi.org/​10.1017/​CBO9780511807077

[48] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (North Holland, 1981).

[49] R. P. Stanley, Enumerative Combinatorics: Volume 1, 2nd ed. (Cambridge University Press, 2011).
https:/​/​doi.org/​10.1017/​CBO9780511609589

[50] A. J. Scott, ``Multipartite entanglement, quantum-error-correcting codes, and entangling power of quantum evolutions,'' Phys. Rev. A 69, 052330 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.69.052330

[51] A. Ketkar, A. Klappenecker, S. Kumar, and P. K. Sarvepalli, ``Nonbinary Stabilizer Codes Over Finite Fields,'' IEEE Trans. Inf. Theory 52, 4892–4914 (2006).
https:/​/​doi.org/​10.1109/​TIT.2006.883612

[52] W. Helwig, W. Cui, J. I. Latorre, A. Riera, and H.-K. Lo, ``Absolute maximal entanglement and quantum secret sharing,'' Phys. Rev. A 86, 052335 (2012).
https:/​/​doi.org/​10.1103/​PhysRevA.86.052335

[53] F. Huber, O. Gühne, and J. Siewert, ``Absolutely Maximally Entangled States of Seven Qubits Do Not Exist,'' Phys. Rev. Lett. 118, 200502 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.200502

[54] F. Huber and N. Wyderka, ``Table of AME states,'' available online at http:/​/​www.tp.nt.uni-siegen.de/​+fhuber/​ame.html (2020).
http:/​/​www.tp.nt.uni-siegen.de/​+fhuber/​ame.html

[55] E. M. Rains, ``Polynomial invariants of quantum codes,'' IEEE Trans. Inf. Theory 46, 54–59 (2000).
https:/​/​doi.org/​10.1109/​18.817508

[56] E. M. Rains, ``Quantum shadow enumerators,'' IEEE Trans. Inf. Theory 45, 2361–2366 (1999b).
https:/​/​doi.org/​10.1109/​18.796376

[57] G. Nebe, E. M. Rains, and N. J. A. Sloane, Self-Dual Codes and Invariant Theory (Springer Berlin-Heidelberg, 2006).
https:/​/​doi.org/​10.1007/​3-540-30731-1

[58] E. M. Rains, ``Quantum codes of minimum distance two,'' IEEE Trans. Inf. Theory 45, 266–271 (1999c).
https:/​/​doi.org/​10.1109/​18.746807

[59] P. Horodecki, L. Rudnicki, and K. Życzkowski, ``Five open problems in quantum information,'' (2020), arXiv:2002.03233.
arXiv:2002.03233

[60] A. Ashikhmin, ``Remarks on Bounds for Quantum Codes,'' (1997), arXiv:quant-ph/​9705037.
arXiv:quant-ph/9705037

[61] A. Ashikhmin and S. Litsyu, ``Upper bounds on the size of quantum codes,'' IEEE Transactions on Information Theory 45, 1206–1215 (1999).
https:/​/​doi.org/​10.1109/​18.761270

[62] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press, 2011).
https:/​/​doi.org/​10.1017/​CBO9780511976667

[63] A. Müller-Hermes, D. Stilck França, and M. M. Wolf, ``Relative entropy convergence for depolarizing channels,'' J. Math. Phys. 57, 022202 (2016).
https:/​/​doi.org/​10.1063/​1.4939560

[64] A. Klappenecker and M. Rötteler, ``Beyond stabilizer codes. I. Nice error bases,'' IEEE Trans. Inf. Theory 48, 2392–2395 (2002).
https:/​/​doi.org/​10.1109/​TIT.2002.800471

[65] M. Rötteler, M. Grassl, and T. Beth, ``On quantum MDS codes,'' in Proceedings, Int. Symp. Inf. Theory (ISIT 2004) (2004) p. 356.
https:/​/​doi.org/​10.1109/​ISIT.2004.1365393

[66] P. K. Sarvepalli and A. Klappenecker, ``Nonbinary quantum Reed-Muller codes,'' in Proceedings. Int. Symp. Inf. Theory, (ISIT 2005) (2005) pp. 1023–1027.
https:/​/​doi.org/​10.1109/​ISIT.2005.1523494

[67] L. Jin, S. Ling, J. Luo, and C. Xing, ``Application of classical Hermitian self-orthogonal MDS codes to quantum MDS codes,'' IEEE Trans. Inf. Theory 56, 4735–4740 (2010).
https:/​/​doi.org/​10.1109/​TIT.2010.2054174

[68] R. Li and Z. Xu, ``Construction of $[[n,n{-}4,3]]{}_{q}$ quantum codes for odd prime power $q$,'' Phys. Rev. A 82, 052316 (2010).
https:/​/​doi.org/​10.1103/​PhysRevA.82.052316

[69] S. Ball, ``Some constructions of quantum MDS codes,'' (2019), arXiv:1907.04391.
arXiv:1907.04391

[70] D. G. Glynn, ``The non-classical $10$-arc of $PG(4, 9)$,'' Discrete Math. 59, 43–51 (1986).
https:/​/​doi.org/​10.1016/​0012-365X(86)90067-1

[71] T. A. Gulliver, J. Kim, and Y. Lee, ``New MDS or near-MDS self-dual codes,'' IEEE Trans. Inf. Theory 54, 4354–4360 (2008).
https:/​/​doi.org/​10.1109/​TIT.2008.928297

[72] J.-L. Kim and Y. Lee, ``Euclidean and Hermitian self-dual MDS codes over large finite fields,'' J. Comb. Theory A 105, 79–95 (2004).
https:/​/​doi.org/​10.1016/​j.jcta.2003.10.003

Cited by

[1] Daniel Alsina and Mohsen Razavi, "Absolutely maximally entangled states, quantum maximum distance separable codes, and quantum repeaters", arXiv:1907.11253.

[2] Maciej Demianowicz and Remigiusz Augusiak, "Entanglement of genuinely entangled subspaces and states: Exact, approximate, and numerical results", Physical Review A 100 6, 062318 (2019).

[3] Paweł Mazurek, Máté Farkas, Andrzej Grudka, Michał Horodecki, and Michał Studziński, "Quantum error-correction codes and absolutely maximally entangled states", Physical Review A 101 4, 042305 (2020).

[4] Maciej Demianowicz and Remigiusz Augusiak, "An approach to constructing genuinely entangled subspaces of maximal dimension", Quantum Information Processing 19 7, 199 (2020).

[5] Sathwik Chadaga, Mridul Agarwal, and Vaneet Aggarwal, "Encoders and Decoders for Quantum Expander Codes Using Machine Learning", arXiv:1909.02945.

[6] Zahra Raissi, "Modifying method of constructing quantum codes from highly entangled states", arXiv:2005.01426.

The above citations are from SAO/NASA ADS (last updated successfully 2020-10-21 18:50:24). 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 2020-10-21 18:50:22).