تقرير
Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders
العنوان: | Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders |
---|---|
المؤلفون: | Evra, Shai, Kaufman, Tali, Zémor, Gilles |
سنة النشر: | 2020 |
المجموعة: | Computer Science Mathematics Quantum Physics |
مصطلحات موضوعية: | Quantum Physics, Computer Science - Information Theory, Mathematics - Combinatorics |
الوصف: | 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. |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2004.07935 |
رقم الأكسشن: | edsarx.2004.07935 |
قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!