Name
Title | ||
|---|---|---|
Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders |
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
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2</sup>
logn, 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
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2</sup>
log
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2</sup>
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/FOCS46700.2020.00029 | 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Quantum code,Ramanujan Complex,expander | Conference | 1523-8288 |
ISBN | Citations | PageRank |
978-1-7281-9622-0 | 1 | 0.35 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shai Evra | 1 | 4 | 1.47 |
| Tali Kaufman | 2 | 499 | 38.33 |
| Gilles Zémor | 3 | 29 | 5.60 |