×

Decodable quantum LDPC codes beyond the \(\sqrt{n}\) distance barrier using high-dimensional expanders. (English) Zbl 1498.81063

Summary: Constructing quantum low-density parity-check (LDPC) codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large \(X\)-distance but a much smaller \(Z\)-distance. However, together with a classical expander LDPC code and a tensoring method that generalizes a construction of Hastings and also the Tillich-Zémor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance \(n^{1/2}\log^{1/2}n\). We then exploit the expansion properties of the complex to devise the first polynomial-time algorithm that decodes above the square root barrier for quantum LDPC codes. Using a 3-dimensional Ramanujan complex, we also obtain an overall quantum code of minimum distance \(n^{1/2}\log n\), which sets a new record for quantum LDPC codes.

MSC:

81P70 Quantum coding (general)
81Q80 Special quantum systems, such as solvable systems
05C48 Expander graphs
81P73 Computational stability and error-correcting codes for quantum computation and communication processing
94B50 Synchronization error-correcting codes
81P43 Quantum discord
46N10 Applications of functional analysis in optimization, convex analysis, mathematical programming, economics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P. Abramenko and K. S. Brown, Buildings: Theory and Applications, Grad. Texts in Math. 248, Springer Science & Business Media, 2008. · Zbl 1214.20033
[2] B. Audoux and A. Couvreur, On tensor products of CSS codes, Ann. Inst. Henri Poincaré (D), 6 (2019), pp. 239-287. · Zbl 1460.81013
[3] S. Bravyi and M. A. Hastings, Homological product codes, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 14, ACM, New York, 2014, pp. 273-282. · Zbl 1315.94143
[4] N. Breuckmann and B. Terhal, Constructions and noise threshold of hyperbolic surface codes, IEEE Trans. Inform. Theory, 62 (2016), pp. 3731-3744. · Zbl 1359.94882
[5] R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Phys. Rev. A, 54 (1996), pp. 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), pp. 6087-6098. · Zbl 1364.81086
[7] N. Delfosse, Tradeoffs for reliable quantum information storage in surface codes and color codes, in IEEE International Symposium on Information Theory (ISIT), 2013, pp. 917-921.
[8] S. Evra and T. Kaufman, Bounded degree cosystolic expanders of every dimension, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 36-48. · Zbl 1376.05095
[9] M. H. Freedman, D. A. Meyer, and F. Luo, \(Z_2\)-systolic freedom and quantum codes, in Mathematics of Quantum Computation, Chapman & Hall/CRC, 2002, pp. 287-320. · Zbl 1075.81508
[10] R. Gallager, Low-density parity-check codes, IRE Trans. Inform. Theory, 8 (1962), pp. 21-28. · Zbl 0107.11802
[11] L. Guth and A. Lubotzky, Quantum error-correcting codes and 4-dimensional arithmetic hyperbolic manifolds, J. Math. Phys., 55 (2014), 082202. · Zbl 1298.81052
[12] M. A. Hastings, Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture, Quantum Inf. Comput., 13 (2013), 393-429.
[13] M. A. Hastings, Quantum codes from high-dimensional manifolds, in 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), Schloss Dagstuhl, 2017, 25. · Zbl 1406.81020
[14] M. A. Hastings, Weight reduction for quantum codes, Quantum Inf. Comput., 17 (2017), pp. 1307-1334.
[15] A. Hatcher, Algebraic Topology, Cambridge University Press, 2000. · Zbl 1044.55001
[16] S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc., 43 (2006), pp. 439-561. · Zbl 1147.68608
[17] T. Kaufman, D. Kazhdan, and A. Lubotzky, Isoperimetric inequalities for Ramanujan complexes and topological expanders, Geom. Funct. Anal., 26 (2016), pp. 250-287. · Zbl 1339.05075
[18] A. Yu. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Physics, 303 (2003), pp. 2-30. · Zbl 1012.81006
[19] A. Leverrier, J-P. Tillich, and G. Zémor, Quantum expander codes, in Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2015, pp. 810-824.
[20] V. Londe and A. Leverrier, Golden codes: Quantum LDPC codes built from regular tessellations of hyperbolic \(4\)-manifolds, Quantum Inf. Comput., 19 (2019), pp. 361-391.
[21] A. Lubotzky, Ramanujan complexes and high dimensional expanders, Jpn. J. Math., 9 (2014), pp. 137-169. · Zbl 1302.05095
[22] A. Lubotzky, High dimensional expanders, in Proceedings of the International Congress of Mathematicians (ICM 2018), 2018, pp. 705-730. · Zbl 1448.05125
[23] A. Lubotzky and R. Meshulam, A Moore bound for simplicial complexes, Bull. London Math. Soc., 39 (2007), pp. 353-358. · Zbl 1180.13028
[24] A. Lubotzky, B. Samuels, and U. Vishne, Ramanujan complexes of type \(\widetilde{A}_d \), Israel J. Math., 149 (2005) pp. 267-300. · Zbl 1087.05036
[25] A. Lubotzky, B. Samuels, and U. Vishne, Explicit construction of Ramanujan complexes of type \(\widetilde{A}_d \), European J. Combin., 26 (2005), pp. 965-993. · Zbl 1135.05038
[26] A. Ntafos and A. Hakimi, On the complexity of some coding problems, IEEE Trans. Inform. Theory, 27 (1981), pp. 794-796. · Zbl 0465.94021
[27] I. Oppenheim, Local spectral expansion approach to high dimensional expanders, Part I: Descent of spectral gaps, Discrete Comput. Geom., 59 (2018), pp. 293-330. · Zbl 1383.05312
[28] M. Sipser and D. A. Spielman, Expander codes, IEEE Trans. Inform. Theory, 42 (1996), pp. 1710-1722. · Zbl 0943.94543
[29] A. Steane, Multiple-particle interference and quantum error correction, Proc. Roy. Soc. London Ser. A, 452 (1996), pp. 2551-2577. · Zbl 0876.94002
[30] 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), pp. 1193-1202. · Zbl 1364.94630
[31] G. Zémor, On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction, in Coding and Cryptology, Second International Workshop IWCC 2009, Lecture Notes in Comput. Sci. 5557, Springer, Berlin, 2009, pp. 259-273. · Zbl 1248.94128
[32] W. Zeng and L. Pryadko, Higher-dimensional quantum hypergraph-product codes with finite rates, Phys. Rev. Lett., 122 (2019), 230501.
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.