论文标题
使用高维扩张器的$ \ sqrt {n} $距离障碍物以外的可解码量子LDPC代码
Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders
论文作者
论文摘要
构建最小距离的量子LDPC代码比长度的平方根快得多，这是该场的主要挑战。考虑到这一挑战，我们研究了来自高维扩张器，尤其是Ramanujan Complexes的结构。这些自然会产生非常不平衡的量子误差校正代码，该代码具有较大的$ x $持续情况，但$ z $ distance少得多。但是，我们与量子代码的Tillich-Zemor构造构造的经典扩展器LDPC代码和张紧方法，我们获得了量子LDPC代码，其最小距离超过代码长度的平方根，其尺寸接近代码长度的平方根。当该成分是三维的Ramanujan复合体时，我们表明其2骨的表现就像复杂大小的日志的正方形，这导致总体量子代码为最小距离$ n^{1/2} \ log n $，并为量子LDPC代码设置了新记录。当我们使用二维Ramanujan复合物或3维Ramanujan Complex的2-Skeleton时，我们获得了最小距离$ n^{1/2} \ log^{1/2} n $的量子LDPC代码。然后，我们利用复合物的膨胀特性来设计第一个多项式时间算法，该算法将量子LDPC代码的平方根屏障上方解码。
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.
