TY - GEN

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

AU - Evra, Shai

AU - Kaufman, Tali

AU - Zemor, Gilles

N1 - Funding Information:
SE is supported by NSF grant number DMS-1638352. TK Aknowledges support by ERC, and GZ is supported by ANR project ANR-18-CE47-0010 (QUDATA).
Publisher Copyright:
© 2020 IEEE.

PY - 2020/11

Y1 - 2020/11

N2 - 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.

AB - 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.

KW - Quantum code

KW - Ramanujan Complex

KW - expander

UR - http://www.scopus.com/inward/record.url?scp=85100341880&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85100341880&partnerID=8YFLogxK

U2 - 10.1109/FOCS46700.2020.00029

DO - 10.1109/FOCS46700.2020.00029

M3 - Conference contribution

AN - SCOPUS:85100341880

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 218

EP - 227

BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020

PB - IEEE Computer Society

T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020

Y2 - 16 November 2020 through 19 November 2020

ER -