Decodable quantum ldpc codes beyond the square root distance barrier using high dimensional expanders

Shai Evra, Tali Kaufman, Gilles Zemor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Constructing quantum 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 generalises a construction of Hastings and also the Tillich-Zemor 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 3-dimensional Ramanujan complex, we show that its 2-systole behaves like a square of the log of the complex size, which results in an overall quantum code of minimum distance n{1/2} log n, and sets a new record for quantum LDPC codes. When we use 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.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE Computer Society
Pages218-227
Number of pages10
ISBN (Electronic)9781728196213
DOIs
StatePublished - Nov 2020
Externally publishedYes
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2020-November
ISSN (Print)0272-5428

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
CountryUnited States
CityVirtual, Durham
Period11/16/2011/19/20

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Quantum code
  • Ramanujan Complex
  • expander

Fingerprint Dive into the research topics of 'Decodable quantum ldpc codes beyond the square root distance barrier using high dimensional expanders'. Together they form a unique fingerprint.

Cite this