Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders

• URL: http://arxiv.org/abs/2004.07935v1
• Date: Thu, 16 Apr 2020 20:36:28 GMT
• Title: Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders
• Authors: Shai Evra, Tali Kaufman and Gilles Z\'emor
• Abstract summary: We construct quantum LDPC codes with a minimum distance that grows faster than a square root of the length. 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. We devise the first algorithm that decodes above the square root barrier for quantum LDPC codes.
• Score: 0.5929956715430168
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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^{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.

Related papers

• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  We present Safe Surgery by Identifying Pushouts (SSIP), an open-source lightweight Python package for automating surgery between qubit CSS codes. Under the hood, it performs linear algebra over $mathbbF$ governed by universal constructions in the category of chain complexes. We show that various logical measurements can be performed cheaply by surgery without sacrificing the high code distance.
  arXiv  Detail & Related papers  (2024-07-12T16:50:01Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes [5.224344210588583]
  We introduce a high-dimensional cubical complex, for any dimension t>0, and apply it to quantum locally testable codes. For t=4 our construction gives a new family of "almost-good" quantum LTCs -- with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks.
  arXiv  Detail & Related papers  (2024-02-12T08:32:13Z)
• Taming Quantum Time Complexity [50.10645865330582]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Geometrically Local Quantum and Classical Codes from Subdivision [10.357542321841887]
  A geometrically local quantum code is an error correcting code situated within $mathbbRD$, where the checks only act on qubits within a fixed spatial distance. Recently, Portnoy made a significant breakthrough with codes achieving optimal dimension and distance up to polylogs. This paper bypasses this step and streamlines the construction by noticing that a family of good quantum low-density parity-check codes, balanced product codes, naturally carries a two-dimensional structure.
  arXiv  Detail & Related papers  (2023-09-28T02:12:38Z)
• Local Quantum Codes from Subdivided Manifolds [0.0]
  We demonstrate the existence of quantum codes which are local in dimension $n$ with $V$ qubits, distance $Vfracn-1n$, and dimension $Vfracn-2n$, up to a $polylog(V)$ factor. The proof combines the existence ofally good quantum codes, a procedure to build a manifold from a code by Freedman-Hastings, and a quantitative embedding by Gromov-Guth.
  arXiv  Detail & Related papers  (2023-03-12T21:04:38Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Morphing quantum codes [77.34726150561087]
  We morph the 15-qubit Reed-Muller code to obtain the smallest known stabilizer code with a fault-tolerant logical $T$ gate. We construct a family of hybrid color-toric codes by morphing the color code.
  arXiv  Detail & Related papers  (2021-12-02T17:43:00Z)
• Quantifying nonlocality: how outperforming local quantum codes is expensive [0.06091702876917279]
  Quantum low-density parity-check (LDPC) codes are a promising avenue to reduce the cost of constructing scalable quantum circuits. We show that quantum LDPC codes implemented through local interactions obey restrictions on their dimension $k$ and distance $d$. In particular, in 2D we show that a quantum LDPC with distance $n1/2 + epsilon$ code requires $Omega(n1/2 + epsilon)$ interactions of length $widetildeOmega(nepsilon)$.
  arXiv  Detail & Related papers  (2021-09-22T18:55:45Z)
• Connectivity constrains quantum codes [0.06091702876917279]
  We study the limitations of quantum LDPC codes associated with local graphs in $D$-dimensional hyperbolic space. We find that unless the connectivity graph contains an expander, the code is severely limited. As an application, we present novel bounds on quantum LDPC codes associated with local graphs in $D$-dimensional hyperbolic space.
  arXiv  Detail & Related papers  (2021-06-01T20:03:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.