×

On tensor products of CSS codes. (English) Zbl 1460.81013

Summary: CSS codes are in one-to-one correspondance with length 3 chain complexes. The latter are naturally endowed with a tensor product \(\otimes\) which induces a similar operation on the former. We investigate this operation, and in particular its behavior with regard to minimum distances. Given a CSS code \(\mathcal{C}\), we give a criterion which provides a lower bound on the minimum distance of \(\mathcal{C} \otimes \mathcal{D}\) for every CSS code \(\mathcal{D}\). From this criterion arises a generic bound for the minimum distance which is twice larger than the single bound previously known in the literature. We apply these results to study the behaviour of iterated tensor powers of codes. Such sequences of codes are logarithmically LDPC and we prove in particular that their minimum distances tend generically to infinity. More precisely, their minimum distance increases as \(O(n^\alpha)\) for some \(\alpha > 0\), where \(n\) is the code length, while the row weight of their parity – check matrices grows as \(O(\log(n))\). This entails a rather surprizing fact: even if a CSS code does not have quantum degeneracy, for a large enough \(\ell\), its \(\ell\)-th iterated tensor power does. Different known results are also reinterpretated in terms of tensor products and three new families of LDPC CSS codes are studied.

MSC:

81P70 Quantum coding (general)
55U15 Chain complexes in algebraic topology
46M05 Tensor products in functional analysis
94B60 Other types of codes

References:

[1] B. Audoux, An application of Khovanov homology to quantum codes. Ann. Inst. Henri Poincaré D 1(2014), no. 2, 185-223.MR 3229943 Zbl 1309.81055 · Zbl 1309.81055
[2] H. Bombin and M. Martin-Delgado, Homological error correction: classical and quantum codes. J. Math. Phys. 48 (2007), no. 5, 052105, 35 pp.MR 2326330 Zbl 1144.81317 · Zbl 1144.81317
[3] S. Bravyi and M. B. Hastings, Homological product codes.arXiv:1311.0885, 2013. · Zbl 1315.94143
[4] S. Bravyi and M. B. Hastings, Homological product codes. In TOC’14—Proceedings of the 2014 ACM Symposium on Theory of Computing.Held in New York, May 31-June 3, 2014. ACM Press, New York, 2014, 273-282.MR 3238953 Zbl 1315.94143 · Zbl 1315.94143
[5] R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist. Phys. Rev. A 54(1996), 1098-1105.
[6] A. Couvreur, N. Delfosse, and G. Zémor, A construction of quantum LDPC codes from Cayley graphs. IEEE Trans. Inform. Theory 59 (2013), no. 9, 6087-6098. MR 3096980 Zbl 1364.81086 · Zbl 1364.81086
[7] N. Delfosse, Constructions et performances de codes LDPC quantiques. Ph.D. thesis. University of Bordeaux, Bordeaux, 2012.
[8] N. Delfosse, Tradeoffs for reliable quantum information storage in surface codes and color codes. In 2013 IEEE International Symposium on Information Theory, 2013, 917-921,
[9] J. Farinholt, Quantum LDPC codes constructed from point-line subsets of the finite projective plane. Preprint, 2012.arXiv:1207.0732[quant-ph]
[10] M. H. Freedman and M. B. Hastings, Quantum systems on non-k-hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs. Quan- tum Inf. Comput. 14(2014), no. 1-2, 144-180.MR 3222761 286B. Audoux and A. Couvreur
[11] M. H. Freedman and D. A. Meyer, Projective plane and planar quantum codes. Found. Comput. Math. 1(2001), no. 3, 325-332.MR 1838758 Zbl 0995.94037 · Zbl 0995.94037
[12] M. H. Freedman, D. A. Meyer, and F. Luo, Z2-systolic freedom and quantum codes. In G. Chen and R. K. Brylinski (eds.), Mathematics of quantum computation. Computational Mathematics Series. Chapman & Hall/CRC, Boca Raton, FL, 2002, 287-320.MR 2007952 Zbl 1075.81508 · Zbl 1075.81508
[13] R. G. Gallager, Low density parity check codes. Ph.D. thesis. Massachussetts Institute of Technology, Boston, 1962. · Zbl 0107.11802
[14] A. Yu. Kitaev, Fault-tolerant quantum computation by anyons. Ann. Physics 303 (2003), no. 1, 2-30.MR 1951039 Zbl 1012.81006 · Zbl 1012.81006
[15] Y. Kou, S. Lin, and M. P. C. Fossorier, Low-density parity-check codes based on finite geometries: a rediscovery and new results. IEEE Trans. Inform. Theory, 47(7):2711-2736, 2001. · Zbl 1015.94015
[16] A. Leverrier, J. Tillich, and G. Zémor, Quantum expander codes. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015.Proceedings of the symposium held in Berkeley, CA, October 18-20, 2015. IEEE Computer Society, Los Alamitos, CA, 2015, 810-824.MR 3473342
[17] F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. Part I. North-Holland Mathematical Library, 16. North-Holland Publishing Co., Amsterdam etc., 1977.MR 0465509 Zbl 0369.94008
[18] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information. 10thanniversary editions edition. Cambridge University Press, Cambridge, 2010. MR 1796805 Zbl 1288.81001 · Zbl 1288.81001
[19] J. Preskill, Quantum information and computation. Course Information for Physics. http://www.theory.caltech.edu/people/preskill/ph229/ · Zbl 1036.81006
[20] Th. J. Richardson, M. Amin Shokrollahi, and R. L. Urbanke, Design of capacityapproaching irregular low-density parity-check codes. IEEE Trans. Inform. Theory 47 (2001), no. 2, 619-637.MR 1820480 Zbl 1019.94034 · Zbl 1019.94034
[21] K. J. C. Smith, On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry. J. Combinatorial Theory 7 (1969) 122-129.MR 0251628 Zbl 0185.24305 · Zbl 0185.24305
[22] A. Steane, Multiple particle interference and quantum error correction. Proc. Roy. Soc. London Ser. A 452(1996), no. 1954, 2551-2577.MR 1421749 Zbl 0876.94002 · Zbl 0876.94002
[23] A. Steane, Quantum Reed-Muller codes. IEEE Trans. Inform. Theory 45 (1999), no. 5, 1701-1703.MR 1699902 Zbl 0957.94054 · Zbl 0957.94054
[24] J.-P. Tillich and G. Zémor, Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Trans. Inform. Theory 60(2014), no. 2, 1193-1202.MR 316497 Zbl 1364.94630 On tensor products of CSS codes287 · Zbl 1364.94630
[25] Ch. A. Weibel, An introduction to homological algebra. Cambridge Studies in Advanced Mathematics, 38. Cambridge University Press, Cambridge, 1994. MR 1269324 Zbl 0797.18001 · Zbl 0797.18001
[26] G. Zémor, On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction. In Y. M. Chee, C. Li, S. Ling, H. Wang, and C. Xing (eds), Coding and cryptology. Proceedings of the 2ndInternational Workshop (IWCC 2009) held in Zhangjiajie, June 1-5, 2009. Lecture Notes in Computer Science, 5557. Springer, Berlin, 2009, 259-273.MR 2836246 Zbl 1248.94128 · Zbl 1248.94128
[27] L. Zhang and I. Fuss, Quantum Reed-Muller codes. Preprint, 1997. arXiv:quant-ph/9703045 © European Mathematical Society Communicated by Gil Kalai Received January 24
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.