PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Tanner codes

Anthony Leverrier, Gilles Zémor

arXiv:2202.13641v3quant-phcs.CCcs.IT

TL;DR

The paper addresses how to construct quantum LDPC codes with constant rate and linear distance while connecting them to locally testable codes. It applies Tanner codes to two shared-edge graphs derived from a left-right Cayley complex, obtaining asymptotically good quantum codes and recovering Dinur et al.’s local testability. The construction is conceptually simpler than related product constructions but has larger generator weights and unresolved explicitness and degree-dependence limitations.

  • Problem

    The work targets the construction of quantum LDPC codes with constant rate and constant relative distance, alongside the challenge of relating them to strong locally testable codes.

  • Method

    It views a left-right Cayley complex as two graphs sharing edges and defines one classical Tanner code on each graph to form a quantum code.

  • Results

    The construction gives asymptotically good quantum LDPC codes with constant rate and linear minimum distance, while a unifying theorem recovers Dinur et al.’s locally testable code.

  • Takeaways & Limitations

    The approach provides a geometric, conceptually simpler variant of the Panteleev–Kalachev construction and links its quantum-code distance to Dinur et al.’s local testability.

  • Takeaways & Limitations

    The construction has generator weights Θ(∆2) rather than Θ(∆), and completely explicit constructions remain desirable.

Abstract

from arXiv · show

Tanner codes are long error correcting codes obtained from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices of the graph. Combining good short codes together with a spectral expander graph yields the celebrated expander codes of Sipser and Spielman, which are asymptotically good classical LDPC codes. In this work we apply this prescription to the left-right Cayley complex that lies at the heart of the recent construction of a $c^3$ locally testable code by Dinur et al. Specifically, we view this complex as two graphs that share the same set of edges. By defining a Tanner code on each of those graphs we obtain two classical codes that together define a quantum code. This construction can be seen as a simplified variant of the Panteleev and Kalachev asymptotically good quantum LDPC code, with improved estimates for its minimum distance. This quantum code is closely related to the Dinur et al. code in more than one sense: indeed, we prove a theorem that simultaneously gives a linearly growing minimum distance for the quantum code and recovers the local testability of the Dinur et al. code.

1 Introduction

The paper constructs quantum LDPC codes from a left-right Cayley complex by applying Tanner-code ideas to two shared-edge graphs. It connects the resulting quantum code to Dinur et al.’s locally testable code through a theorem giving linear quantum distance and recovering local testability.

  • 1 Introduction: Quantum LDPC codes require sparse parity-check matrices while maintaining constant rate and constant relative distance, an open question answered positively by Panteleev and Kalachev.Quantum distance is the minimum of the X- and Z-error distances.
  • 1 Introduction: The construction places qubits on squares of a left-right Cayley complex and enforces constraints at its vertices using dual tensor-code structure.The quantum compatibility condition prevents directly using small tensor-code constraints.
  • 1 Introduction: The construction yields asymptotically good quantum LDPC codes with constant rate and linear minimum distance when the complex expands sufficiently and dual tensor codes are robust.Robustness holds with high probability for random component codes.
  • 1 Introduction: The left-right Cayley complex can be viewed as two ordinary graphs sharing the same edges, enabling two classical Tanner codes to define the quantum code.This applies the Tanner-code strategy directly to a geometric square complex.
  • 1 Introduction: For any fixed code rate, the resulting quantum minimum distance scales as n/∆3/2+ε, with ε arbitrarily close to 0.Here n is the code length and ∆ is the degree of the underlying Cayley graphs.
  • 1 Introduction: A unifying theorem simultaneously proves linear minimum distance for the quantum code and recovers Dinur et al.’s locally testable code.The paper presents this construction as a connection between the Panteleev–Kalachev quantum-code construction and Dinur et al.’s LTC.

2 Overview

The paper applies Tanner-code constructions to left-right Cayley complexes, viewing each complex as two graphs whose Tanner codes form a quantum CSS code. Under expansion and robustness conditions, the construction yields asymptotically good quantum LDPC codes while connecting their distance to the local testability of Dinur et al.'s code.

  • The left-right Cayley complex: A left-right Cayley complex is a bipartite square complex whose A- and B-edges form double covers of left and right Cayley graphs.Its squares have vertices {(g,0),(ag,1),(gb,1),(agb,0)}.
  • Two Tanner graphs: Restricting the complex to either vertex part turns its squares into edges of two graphs, G◻0 and G◻1, which share the square coordinate set.The two graphs are replicas, with g and g′ adjacent when g′ = agb for a ∈ A and b ∈ B.
  • Classical Tanner codes: The Tanner code on G◻0 with base code CA ⊗ CB recovers the locally testable code of Dinur et al.Local views are assignments on A × B constrained to lie in the tensor code.
  • Quantum Tanner codes: The quantum CSS code uses Tanner codes C0 and C1 on the two graphs, with C1 built from the dual tensor code and satisfying C1 ⊃ C⊥0.The component codes have rates ρ and 1 − ρ, giving quantum rate at least (2ρ − 1)^2.
  • Connections and limitations: The construction simultaneously recovers Dinur et al.'s local testability and provides improved quantum minimum-distance estimates, while words outside C⊥0 can have weight below n/∆.The latter bound leaves limited room for improving the dependence on ∆.

3 Preliminaries

The preliminaries introduce expander graphs, left-right Cayley complexes, Tanner codes, and quantum CSS codes. These ingredients provide the graph structure, local constraints, and algebraic compatibility used in the paper’s construction.

  • Expander graphs: A Ramanujan graph is a regular graph whose nontrivial adjacency eigenvalues are bounded by 2√(∆−1).The expander mixing lemma relates this spectral condition to edge distribution between vertex sets.
  • Left-right Cayley complexes: A left-right Cayley complex is built from a group G and generator sets A and B, with vertices, A-edges, B-edges, and squares.Squares have the form {g, ag, gb, agb}; under TNC, each vertex link is identified with A × B, organized into rows and columns.
  • Left-right Cayley complexes: Double covers make the Cayley graphs bipartite, after which squares connect vertices through the group action and define the associated complex.The quadripartite variant uses four copies of G and avoids reliance on the symmetry condition A = A−1 and B = B−1.
  • Left-right Cayley complexes: The construction also uses graphs G∪ and G□ derived from the complex, where G□ has degree ∆2 and two connected components.The graphs’ expansion follows from the commuting adjacency matrices of the underlying Cayley graphs.
  • Tanner codes: A Tanner code consists of edge-indexed vectors whose local view at every vertex belongs to a fixed length-∆ component code.For a graph G and component code C0, the local view is the restriction to the incident edges E(v).
  • Tanner codes: 60: Tanner codes on sufficiently expanding graphs have rate and minimum distance both Ω(n) when the component code has rate above 1/2 and graph expansion is strong enough.This is the asymptotically good expander-code regime established by Sipser and Spielman.
  • Quantum CSS codes: A quantum CSS code is defined from classical codes C0 and C1 satisfying C⊥0 ⊂ C1, equivalently H0H1^T = 0 when parity-check matrices define them.This compatibility condition ensures the resulting quantum code is a valid subspace of n-qubit space.

4 Asymptotically good quantum Tanner codes

The paper constructs a quantum CSS code from two Tanner codes on a left-right Cayley complex, using tensor-derived local constraints. Under expansion, component-code distance, and dual-tensor robustness assumptions, it proves asymptotically good quantum LDPC families with linearly growing distance.

  • Construction: The construction views the left-right Cayley complex as two graphs sharing square coordinates and places qubits on squares with constraints imposed on vertex neighborhoods.Local neighborhoods are indexed as A × B arrays; neighboring views share rows or columns.
  • Construction: The two classical codes are Tanner codes defined from tensor-related local codes, with C0 = CA ⊗ CB and C1 built from the dual tensor code.The generator construction enforces orthogonality between X- and Z-type generators, yielding the CSS condition.
  • Parameters: The code is LDPC with length n = ∆2∣G∣/2, generator weight at most ∆2, and positive rate whenever ρ ≠ 1/2.The number of generators gives a dimension lower bound, with equality if all generators are independent.
  • Distance proof: Theorem 1 gives a local reduction for every nonzero C1 codeword of weight below δn/4∆3/2+ε, producing a supported codeword that strictly decreases weight.The reduction relies on expanding Cayley graphs, component-code minimum distance, and robust dual tensor codes with resistance to puncturing.
  • Distance proof: The distance proof classifies vertices as normal or exceptional and uses expansion to show that exceptional vertices form a small set.Robustness restricts low-weight local views to few rows and columns, enabling the subsequent local correction argument.

A Appendix: proof of Theorem 9

The appendix proves that random dual tensor codes exclude low-weight matrices except those confined to few rows and columns, using rank bounds and punctured-code probability estimates. These results establish robustness and, with high probability, the theorem’s stated distance behavior.

  • Random-code estimates: For independent vectors, random parity checks place all vectors in the code with probability 1/2^{r|V|}, while puncturing weakens this to at most 1/2^{(r−p)|V|}.The estimates follow from independence of syndromes and conditioning on the span generated by the punctured coordinates.
  • Puncturing probability: Lemma 29 bounds the probability that a fixed puncturing pattern contains a dual-tensor-code matrix by 1/2^{(r_B−p)α}.After puncturing p coordinates, membership requires every row of H_A X_p to lie in the punctured random code; Corollary 26 supplies the necessary rank.
  • Theorem 30: Theorem 30 shows that, with probability at least 1 − 1/2^{c∆^{3/2}}, every low-weight matrix is either supported by at most δ∆/2 rows and columns or lies outside the dual tensor code.The proof partitions matrices by heavy columns, applies Lemma 29, and bounds the expected number of exceptional sets.
  • Support control: Lemma 31 converts row-and-column support bounds on a dual-tensor codeword into bounds of |c|/d_A columns and |c|/d_B rows.This decomposition controls the support of the two tensor components using the minimum distances of the constituent codes.
  • Theorem 9: Theorem 9 applies Theorem 30 to random component codes and obtains the claimed high-probability robustness and minimum-distance behavior for the dual tensor code.The component-code distances are controlled using the Gilbert–Varshamov bound, then the argument is repeated over sufficiently large coordinate subsets to obtain resistance to puncturing.
Loading 2202.13641v3…