Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with $Omega(sqrt{n}log^kn)$ Distance
202
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this work we introduce a new notion of expansion in higher dimensions that is stronger than the well studied cosystolic expansion notion, and is termed {em Collective-cosystolic expansion}. We show that tensoring two cosystolic expanders yields a new cosystolic expander, assuming one of the complexes in the product, is not only cosystolic expander, but rather a collective cosystolic expander. We then show that the well known bounded degree cosystolic expanders, the Ramanujan complexes are, in fact, collective cosystolic expanders. This enables us to construct new bounded degree cosystolic expanders, by tensoring of Ramanujan complexes. Using our new constructed bounded degree cosystolic expanders we construct {em explicit} quantum LDPC codes of distance $sqrt{n} log^k n$ for any $k$, improving a recent result of Evra et. al. cite{EKZ}, and setting a new record for distance of explicit quantum LDPC codes. The work of cite{EKZ} took advantage of the high dimensional expansion notion known as cosystolic expansion, that occurs in Ramanujan complexes. Our improvement is achieved by considering tensor product of Ramanujan complexes, and using their newly derived property, the collective cosystolic expansion.
rate research
Read More
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.
We present a quantum LDPC code family that has distance $Omega(N^{3/5}/operatorname{polylog}(N))$ and $tildeTheta(N^{3/5})$ logical qubits. This is the first quantum LDPC code construction which achieves distance greater than $N^{1/2} operatorname{polylog}(N)$. The construction is based on generalizing the homological product of codes to a fiber bundle.
We utilize a concatenation scheme to construct new families of quantum error correction codes that include the Bacon-Shor codes. We show that our scheme can lead to asymptotically good quantum codes while Bacon-Shor codes cannot. Further, the concatenation scheme allows us to derive quantum LDPC codes of distance $Omega(N^{2/3}/loglog N)$ which can improve Hastingss recent result [arXiv:2102.10030] by a polylogarithmic factor. Moreover, assisted by the Evra-Kaufman-Zemor distance balancing construction, our concatenation scheme can yield quantum LDPC codes with non-vanishing code rates and better minimum distance upper bound than the hypergraph product quantum LDPC codes. Finally, we derive a family of fast encodable and decodable quantum concatenated codes with parameters ${Q}=[[N,Omega(sqrt{N}),Omega( sqrt{N})]]$ and they also belong to the Bacon-Shor codes. We show that ${Q}$ can be encoded very efficiently by circuits of size $O(N)$ and depth $O(sqrt{N})$, and can correct any adversarial error of weight up to half the minimum distance bound in $O(sqrt{N})$ time. To the best of our knowledge, they are the most powerful quantum codes for correcting so many adversarial errors in sublinear time by far.
Quantum LDPC codes are a promising direction for low overhead quantum computing. In this paper, we propose a generalization of the Union-Find decoder as adecoder for quantum LDPC codes. We prove that this decoder corrects all errors with weight up to An^{alpha} for some A, {alpha} > 0 for different classes of quantum LDPC codes such as toric codes and hyperbolic codes in any dimension D geq 3 and quantum expander codes. To prove this result, we introduce a notion of covering radius which measures the spread of an error from its syndrome. We believe this notion could find application beyond the decoding problem. We also perform numerical simulations, which show that our Union-Find decoder outperforms the belief propagation decoder in the low error rate regime in the case of a quantum LDPC code with length 3600.
We construct an explicit family of 3XOR instances which is hard for $O(sqrt{log n})$ levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time. Our construction is based on the high-dimensional expanders devised by Lubotzky, Samuels and Vishne, known as LSV complexes or Ramanujan complexes, and our analysis is based on two notions of expansion for these complexes: cosystolic expansion, and a local isoperimetric inequality due to Gromov. Our construction offers an interesting contrast to the recent work of Alev, Jeronimo and the last author~(FOCS 2019). They showed that 3XOR instances in which the variables correspond to vertices in a high-dimensional expander are easy to solve. In contrast, in our instances the variables correspond to the edges of the complex.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
