CoChat
Sign Up
PreprintCited by 9Quantum Computing Algorithms and ArchitectureCoding theory and cryptographyError Correcting Code Techniques

The DOI matches its DataCite record.

Asymptotically Good Quantum and Locally Testable Classical LDPC Codes

Open access
Panteleev, Pavel, Kalachev, Gleb·2021·arXiv
DOI 10.48550/arxiv.2111.03654arXiv 2111.03654
Open this paper in CoChat — free accountOpen PDF

Abstract

We study classical and quantum LDPC codes of constant rate obtained by the lifted product construction over non-abelian groups. We show that the obtained families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. Moreover, we show that the produced classical LDPC codes are also asymptotically good and locally testable with constant query and soundness parameters, which proves a well-known conjecture in the field of locally testable codes.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2111.03654

Cites

Statistics

Figures

Figure 1 Lifting of the base graph Γ.
Figure 1 Lifting of the base graph Γ.CC-BY · From the PDF
Figure 2 Voltage assignments for the graphs B w and D w . The derived graph for B w corresponds to Cay( G,S ), while the derived graph for D w is the double-cover of Cay( G,S ). The small arrows shows the orientation that we fix.
Figure 2 Voltage assignments for the graphs B w and D w . The derived graph for B w corresponds to Cay( G,S ), while the derived graph for D w is the double-cover of Cay( G,S ). The small arrows shows the orientation that we fix.CC-BY · From the PDF
Figure 3 High-level view of the tensor product complex A⊗B ∗ , where A ∈ T ( D w ; h ), B ∈ T ( D w ; h ′ ), and w = 8 (on the right); and its part that corresponds to the elements from X incident to the vertex v (on the left).
Figure 3 High-level view of the tensor product complex A⊗B ∗ , where A ∈ T ( D w ; h ), B ∈ T ( D w ; h ′ ), and w = 8 (on the right); and its part that corresponds to the elements from X incident to the vertex v (on the left).CC-BY · From the PDF
Figure 4 Idea of the proof.
Figure 4 Idea of the proof.CC-BY · From the PDF
Figure 5 Local expansion for the vertex v
Figure 5 Local expansion for the vertex vCC-BY · From the PDF
Figure 6 Active elements in the star of v : black circles-labeled vertices, green faces-active faces from ( E → v \ A ) × E ↑ v , blue faces-active faces from A × E ↑ v , thick black edges-active vertical edges that are not incident to v . Each thick edge is incident to a labeled vertex which is the opposite to v in this face.
Figure 6 Active elements in the star of v : black circles-labeled vertices, green faces-active faces from ( E → v \ A ) × E ↑ v , blue faces-active faces from A × E ↑ v , thick black edges-active vertical edges that are not incident to v . Each thick edge is incident to a labeled vertex which is the opposite to v in this face.CC-BY · From the PDF

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Still being checked.

Research works printed but not linked: 64

  1. R. G. Gallager, Low-density parity-check codes. M.I.T. Press, Cambridge, MA, 1963.
  2. D. J. C. MacKay, G. Mitchison, and P. L. McFadden, "Sparse-graph codes for quantum error correction," IEEE Transactions on Information Theory, vol. 50, no. 10, pp. 2315-2330, Oct. 2004.
  3. T. Kaufman and M. Sudan, "Sparse random linear codes are locally decodable and testable," in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), Oct. 2007, pp. 590-600.
  4. D. Aharonov and L. Eldar, "Quantum locally testable codes," SIAM Journal on Computing, vol. 44, no. 5, pp. 1230-1262, Jan. 2015.
  5. L. Eldar and A. W. Harrow, "Local hamiltonians whose ground states are hard to approximate," 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 427- 438, Oct. 2017.
  6. O. Goldreich, "Short locally testable codes and proofs: A survey in two parts," in Property Testing: Current Research and Surveys, ser. Lecture Notes in Computer Science, O. Goldreich, Ed. Berlin, Heidelberg: Springer, 2010, pp. 65-104.
  7. A. Leverrier, V. Londe, and G. Zémor, "Towards local testability for quantum coding," Mar. 2021. [Online]. Available: http://arxiv.org/abs/1911.03069 · arXiv
  8. A. R. Calderbank and P. W. Shor, "Good quantum error-correcting codes ex- ist," Phys. Rev. A, vol. 54, pp. 1098-1105, Aug 1996. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.54.1098 · DOI · Paper page
  9. A. M. Steane, "Error correcting codes in quantum theory," Phys. Rev. Lett., vol. 77, pp. 793-797, Jul 1996. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.77.793 · DOI · Paper page
  10. I. Dinur, "The PCP theorem by gap amplification," Journal of the ACM, vol. 54, no. 3, pp. 12-es, Jun. 2007.
  11. Y. Dikstein, I. Dinur, P. Harsha, and N. Ron-Zewi, "Locally testable codes via high- dimensional expanders," May 2020. [Online]. Available: http://arxiv.org/abs/2005.01045 · arXiv
  12. O. Goldreich and M. Sudan, "Locally testable codes and PCPs of almost-linear length," in The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., Nov. 2002, pp. 13-22.
  13. N. P. Breuckmann and J. N. Eberhardt, "Quantum low-density parity-check codes," PRX Quantum, vol. 2, no. 4, p. 040101, Oct. 2021.
  14. D. Bacon, S. T. Flammia, A. W. Harrow, and J. Shi, "Sparse quantum codes from quantum circuits," IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 2464-2479, 2017.
  15. T. C. Bohdanowicz, E. Crosson, C. Nirkhe, and H. Yuen, "Good approximate quantum ldpc codes from spacetime circuit hamiltonians," in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ser. STOC 2019. New York, NY, USA: Association for Computing Machinery, Jun. 2019, pp. 481-490. [Online]. Available: https://doi.org/10.1145/3313276.3316384 · DOI
  16. M. B. Hastings, J. Haah, and R. O'Donnell, "Fiber bundle codes: breaking the N 1/2 polylog(N ) barrier for quantum LDPC codes," in Proceedings of the 53rd Annual ACM SIGACT Sympo- sium on Theory of Computing. New York, NY, USA: Association for Computing Machinery, Jun. 2021, pp. 1276-1288.
  17. P. Panteleev and G. Kalachev, "Quantum LDPC codes with almost linear minimum distance," IEEE Transactions on Information Theory, pp. 1-1, 2021.
  18. N. P. Breuckmann and J. N. Eberhardt, "Balanced product quantum codes," IEEE Transac- tions on Information Theory, vol. 67, no. 10, pp. 6653-6674, Oct. 2021.
  19. M. B. Hastings, "On quantum weight reduction," Sep. 2021. [Online]. Available: http://arxiv.org/abs/2102.10030 · arXiv
  20. E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, "Topological quantum memory," Journal of Mathematical Physics, vol. 43, no. 9, pp. 4452-4505, 2002.
  21. M. H. Freedman, D. A. Meyer, and F. Luo, "Z 2 -systolic freedom and quantum codes," in Math- ematics of quantum computation, R. K. Brylinski and G. Chen, Eds. New York: Chapman & Hall/CRC, 2002, ch. 12, pp. 287-320.
  22. J. Tillich and G. Zémor, "Quantum LDPC codes with positive rate and minimum distance proportional to n 1/2 ," in 2009 IEEE International Symposium on Information Theory, June 2009, pp. 799-803.
  23. L. Guth and A. Lubotzky, "Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds," Journal of Mathematical Physics, vol. 55, no. 8, p. 082202, Aug. 2014.
  24. S. Evra, T. Kaufman, and G. Zémor, "Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders," in 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Nov. 2020, pp. 218-227.
  25. T. Kaufman and R. J. Tessler, "New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω( √ n log k n) distance," in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. New York, NY, USA: Association for Computing Machinery, Jun. 2021, pp. 1317-1329.
  26. A. Leverrier, J.-P. Tillich, and G. Zémor, "Quantum expander codes," in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Oct. 2015, pp. 810-824.
  27. E. Ben-Sasson and M. Sudan, "Robust locally testable codes and products of codes," Random Structures & Algorithms, vol. 28, no. 4, pp. 387-402, 2006. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20120 · DOI
  28. J. Tillich and G. Zémor, "Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength," IEEE Transactions on Information Theory, vol. 60, no. 2, pp. 1193-1202, Feb. 2014.
  29. K. S. Brown, "Some homological algebra," in Cohomology of Groups, ser. Graduate Texts in Mathematics, K. S. Brown, Ed. New York, NY: Springer, 1982, pp. 4-32.
  30. P. Panteleev and G. Kalachev, "Degenerate quantum ldpc codes with good finite length performance," Quantum, vol. 5, p. 585, Nov. 2021. [Online]. Available: https://quantum-journal.org/papers/q-2021-11-22-585/
  31. M. Sipser and D. Spielman, "Expander codes," IEEE Transactions on Information Theory, vol. 42, no. 6, pp. 1710-1722, Nov. 1996.
  32. R. Tanner, "A recursive approach to low complexity codes," Information Theory, IEEE Trans- actions on, vol. 27, no. 5, pp. 533-547, 1981.
  33. I. Dinur, M. Sudan, and A. Wigderson, "Robust local testability of tensor products of ldpc codes," in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, ser. Lecture Notes in Computer Science, J. Díaz, K. Jansen, J. D. P. Rolim, and U. Zwick, Eds. Berlin, Heidelberg: Springer, 2006, pp. 304-315.
  34. A. Lubotzky, R. Phillips, and P. Sarnak, "Ramanujan graphs," Combinatorica, vol. 8, no. 3, pp. 261-277, Sep. 1988. [Online]. Available: https://doi.org/10.1007/BF02126799 · DOI
  35. G. A. Margulis, "Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators," Problemy peredachi informatsii, vol. 24, no. 1, pp. 51-60, 1988.
  36. T. Kaufman, D. Kazhdan, and A. Lubotzky, "Ramanujan complexes and bounded degree topological expanders," in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Oct. 2014, pp. 484-493.
  37. T. Kaufman and A. Lubotzky, "High dimensional expanders and property testing," in Pro- ceedings of the 5th conference on Innovations in theoretical computer science, ser. ITCS '14. New York, NY, USA: Association for Computing Machinery, Jan. 2014, pp. 501-506.
  38. R. Meshulam, "Graph codes and local systems," Mar. 2018. [Online]. Available: https://arxiv.org/abs/1803.05643v1 · arXiv
  39. D. T. Wise, "Complete square complexes," Commentarii Mathematici Helvetici, vol. 82, no. 4, pp. 683-724, Dec. 2007. [Online]. Available: https://ems.press/journals/cmh/articles/1470
  40. I. Dinur, S. Evra, R. Livne, A. Lubotzky, and S. Mozes, "Locally testable codes with constant rate, distance, and locality," Nov. 2021. [Online]. Available: http://arxiv.org/abs/2111.04808 · arXiv
  41. S. Bravyi and M. B. Hastings, "Homological product codes," in Proceedings of the forty-sixth annual ACM symposium on theory of computing, ser. STOC '14. New York, NY, USA: ACM, 2014, pp. 273-282.
  42. W. Zeng and L. P. Pryadko, "Higher-dimensional quantum hypergraph-product codes with finite rates," Physical Review Letters, vol. 122, no. 23, p. 230501, Jun. 2019.
  43. M. Hagiwara and H. Imai, "Quantum quasi-cyclic LDPC codes," in 2007 IEEE international symposium on information theory, Jun. 2007, pp. 806-810.
  44. J. Haah, "Local stabilizer codes in three dimensions without string logical operators," Physical Review A, vol. 83, no. 4, p. 042330, Apr. 2011.
  45. A. A. Kovalev and L. P. Pryadko, "Quantum kronecker sum-product low-density parity-check codes with finite rate," Physical Review A, vol. 88, no. 1, p. 012311, Jul. 2013.
  46. S. Hoory, N. Linial, and A. Wigderson, "Expander graphs and their applications," Bull. Amer. Math. Soc., vol. 43, no. 04, pp. 439-562, Aug. 2006.
  47. J. Friedman, "A proof of Alon's second eigenvalue conjecture," in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ser. STOC '03. New York, NY, USA: Association for Computing Machinery, 2003, pp. 720-724. [Online]. Available: https://doi.org/10.1145/780542.780646 · DOI
  48. G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ra- manujan Graphs, ser. London Mathematical Society Student Texts. Cambridge: Cambridge University Press, 2003.
  49. A. Lubotzky, "High dimensional expanders," in Proceedings of the International Congress of Mathematicians (ICM 2018). WORLD SCIENTIFIC, Jun. 2018, pp. 705-730.
  50. J. L. Gross and T. W. Tucker, Topological graph theory, ser. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, 1987.
  51. N. Agarwal, K. Chandrasekaran, A. Kolla, and V. Madan, "On the expansion of group-based lifts," SIAM Journal on Discrete Mathematics, vol. 33, no. 3, pp. 1338-1373, 2019. [Online]. Available: https://doi.org/10.1137/17M1141047 · DOI
  52. P. J. Hilton and S. Wylie, "Homology theory of a simplicial complex," in Homology Theory: An Introduction to Algebraic Topology. Cambridge: Cambridge University Press, 1960, pp. 53-94.
  53. P. McMullen and E. Schulte, Abstract Regular Polytopes. Cambridge University Press, Dec. 2002.
  54. J. Wolf, "On codes derivable from the tensor product of check matrices," IEEE Transactions on Information Theory, vol. 11, no. 2, pp. 281-284, Apr. 1965.
  55. R. Chien and S. Ng, "Dual product codes for correction of multiple low-density burst errors," IEEE Transactions on Information Theory, vol. 19, no. 5, pp. 672-677, Sep. 1973.
  56. A. Barg and G. D. Forney, "Random codes: minimum distances and error exponents," IEEE Transactions on Information Theory, vol. 48, no. 9, pp. 2568-2573, 2002.
  57. F. G. Jeronimo, T. Mittal, R. O'Donnell, P. Paredes, and M. Tulsiani, "Explicit abelian lifts and quantum ldpc codes," Dec. 2021. [Online]. Available: http://arxiv.org/abs/2112.01647 · arXiv
  58. L. Eldar and A. W. Harrow, "Local hamiltonians whose ground states are hard to approximate," in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), Oct. 2017, pp. 427-438.
  59. E. T. Campbell, "A theory of single-shot error correction for adversarial noise," Quantum Science and Technology, vol. 4, no. 2, p. 025006, Feb. 2019. [Online]. Available: https://doi.org/10.1088/2058-9565/aafc8f · DOI
  60. E. R. Berlekamp, Algebraic Coding Theory. New York: McGraw-Hill, 1968.
  61. N. Aydin, I. Siap, and D. K. Ray-Chaudhuri, "The structure of 1-generator quasi-twisted codes and new linear codes," Designs, Codes and Cryptography, vol. 24, no. 3, pp. 313-326, Dec. 2001.
  62. Y. Jia, "On quasi-twisted codes over finite fields," Finite Fields and Their Applications, vol. 18, no. 2, pp. 237-257, Mar. 2012.
  63. J. Lv, R. Li, and J. Wang, "Constructions of quasi-twisted quantum codes," Quantum Infor- mation Processing, vol. 19, no. 8, p. 274, Jul. 2020.
  64. M. M. Deza and E. Deza, "Distances in algebra," in Encyclopedia of Distances, M. M. Deza and E. Deza, Eds. Berlin, Heidelberg: Springer, 2013, pp. 183-195.

Cited by

Sorted by citations

Metadata

Authors
Panteleev, P., & Kalachev, G.
Affiliations
Lomonosov Moscow State University (RU)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2021
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2111.03654
arXiv
2111.03654
OpenAlex
W4225906929
Cited by
9
References
0
Citations by year
2026: 1 · 2025: 1 · 2024: 2 · 2023: 4 · 2022: 1
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Funders
Ministry of Science and Higher Education of the Russian Federation (075-15-2020, 075‐15‐2020‐801, 075-15-)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
  • Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
Keywords
quantum LDPC codes, asymptotically good codes, non-abelian groups, locally testable codes, soundness

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review