PaperlayerView exact revision on arXiv

Source-linked AI summary

Good Quantum Locally Testable Codes from Lossless Cubical Complexes

Itay Cohen, Itai Leigh, Assaf Reiner, Amnon Ta-Shma, Elad Tzalik

arXiv:2610.00525v1quant-phcs.CCcs.ITmath.IT

TL;DR

Higher-dimensional cubical complexes with the needed directional lossless expansion remain to be constructed explicitly. The paper proves that suitable direction-wise lossless expansion and imbalance yield robust small-set level coboundary expansion, which in dimension four gives quantum locally testable codes.

  • Problem

    Explicit higher-dimensional direction-wise lossless decorated cubical complexes remain to be constructed.

    Source: §1.3 · p. 9

  • Method

    The paper proves that suitable directional lossless expansion and imbalance imply robust small-set level coboundary expansion.

    Source: §1.3 · p. 8

  • Results

    In dimension four, robust small-set level coboundary expansion yields a quantum locally testable code.

    Source: §1.3 · p. 9

  • Takeaways & Limitations

    The coding-theoretic consequence is conditional on obtaining the required lossless cubical complexes.

    Source: §1.3 · p. 9

    The work does not construct the required complexes; constructing explicit higher-dimensional direction-wise lossless decorated cubical complexes remains the challenge.

    Source: §1.3 · p. 9

Abstract

from arXiv · show

Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes. In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.

1 Introduction

The introduction presents a local-to-global route from one-dimensional lossless expansion in directional graphs, with links as the local structures enabling the reduction, to robust small-set coboundary expansion. It also describes the dimension-four implication for quantum locally testable codes under the theorem’s assumptions, notes the challenge of constructing suitable complexes, and contrasts the geometric approach with concurrent work.

1 Introduction

  • Classical LTCs require constant-query testing with rejection probability proportional to distance, and quantum LTCs require low-energy states to be close to the code space.Classical LTC constructions recently achieved constant rate, relative distance, and query complexity [PK22].Source: §1 · pp. 3–4

1.1 The gradual emergence of expansion and homology in coding theory

  • Higher-dimensional cubical complexes with suitable two-sided lossless expansion are not known even probabilistically, whereas Dinur, Lin and Vidick constructed quantum locally testable codes with polylogarithmic overhead this way.Source: §1.1 · p. 6

1.2 The combinatorial framework

  • The level chain complex uses vector spaces supported on levels and maps induced by adjacency between consecutive levels; weak completion makes successive boundary maps compose to zero.Expansion is defined for small minimal cochains, or robustly for locally minimal cochains, thereby excluding trivial cohomological obstructions.Source: §1.2 · pp. 7–8

1.3 The result

  • Under suitable lossless-expansion and imbalance assumptions, every direction-wise lossless decorated cubical complex is a robust small-set level coboundary expander.The theorem establishes this higher-dimensional expansion property from assumptions on the individual direction graphs.Source: §1.3 · p. 8
  • In dimension four, robust small-set level coboundary expansion yields quantum locally testable codes when the chain complex is interpreted as a CSS code.The same framework recovers LTCs and quantum LDPC codes from square complexes in dimension two, following Lin and Hsieh.Source: §1.3 · p. 9
  • EFMP bigraphs fail two-sided lossless expansion: adapting the closed orbit method reveals nonexpanding sets arising from subgroups, not subfields.The associated imbalanced cubical complexes therefore fail the theorem’s directional lossless-expansion hypothesis.Source: §1.3 · pp. 9–10
  • The introduction motivates combining a cubical complex with one-dimensional lossless expansion along direction graphs to obtain a genuinely higher-dimensional expansion theorem.It frames this combination as the reason the higher-dimensional lossless approach can work.Source: §1.3 · p. 10

1.4 The technique

  • The global-to-local theorem decomposes each sufficiently small cochain into link-supported local cochains whose coboundaries lower-bound the global coboundary up to an error vanishing with the loss parameters.Links are upward-closed subcomplexes containing a vertex and its monotone-path-connected higher-level vertices; local minimality is needed for local expansion, not for the decomposition.Source: §1.4 · pp. 10, 12
  • The reduction controls overlaps among local coboundaries by bounding excess arising from directional-expansion failures and square completion to non-heavy vertices.The authors distinguish this light/heavy decomposition from, which bounded all squares; they say the distinction handles cancellations over F2 in higher-dimensional cochain coboundaries.Source: §1.4 · p. 11
  • Under lossless-square-complex and imbalance hypotheses, the theorem establishes robust small-set coboundary expansion at arbitrary levels, with constants independent of |X(0)|.The introduction describes this as the consequence of combining expansion in links with the global-to-local reduction.Source: §1.4 · p. 12

1.5 Relation to concurrent work

  • Unlike Gay and Jeronimo [GGJ26], who use a cosheaf complex and Reed–Solomon local codes, this approach places the burden on geometry and uses lossless directional expansion.The authors present it as a distinct, purely combinatorial route to quantum local testability and expect suitably imbalanced lossless cubical complexes to have broader applications.Source: §1.5 · pp. 12–13

2 Cubical complexes

This section sets up decorated cubical complexes and a level-based chain/cochain framework for stating small-set coboundary expansion. It defines completion, links, minimality, and directional lossless expansion.

2.1 Simplicial and cubical complexes

  • A Boolean-cube decoration organizes vertex blocks, declared cubes are closed under subcubes, and three unique-completion conditions are equivalent.Source: §2.1 · p. 14

2.2 The level chain complex

  • Chains and cochains are vertex functions on Boolean-cube levels; square completion makes successive boundary and coboundary maps compose to zero.The weighted support norm is equivalent to Hamming weight up to a factor depending only on the degrees.Source: §2.2 · pp. 15–17

2.3 Links

  • A vertex's link consists of vertices above it, with restricted boundary and coboundary maps that also satisfy the chain-complex identities.Source: §2.3 · pp. 17–18

2.4 Small-set coboundary expansion

  • Small-set coboundary expansion requires locally minimal cochains of norm at most α to have coboundary norm at least β times their norm; minimal cochains are locally minimal.Source: §2.4 · p. 18

2.5 Lossless expansion

  • Directional graphs are required to be one-sided lossless from lower to upper levels; two-sided losslessness also requires losslessness after reversing the complex with the same parameters.The section also records lossless-edge and large-degree bounds for one-sided lossless bigraphs.Source: §2.5 · pp. 18–19

3 Expansion of the links

The section shows that links in lossless cubical complexes inherit expansion from complete multipartite complexes, with an additive error depending on the loss. It establishes this transfer by analyzing ordered paths, embedding non-colliding vertices, and extending the link comparison to relative links.

3 Expansion of the links

  • Lossless square complexes inherit complete multipartite link expansion, with an additive error controlled by the loss.Complete d-partite complexes expand minimal cochains at the relevant levels, providing the expansion being transferred.Source: §3 · p. 20

3.1 Ordered paths and collisions

  • Square switches biject paths across adjacent direction swaps, making endpoint fibers equal-sized across orderings and every ordered endpoint map surjective.Adjacent transpositions generate all direction orderings, and the switch preserves the endpoint.Source: §3.1 · p. 21

3.2 Embedding the non-colliding part

  • Every non-colliding vertex has a Boolean-cube interval below it, and φ gives a type-preserving poset isomorphism onto its image.Each subset of the vertex's type corresponds to a unique interval vertex, with order given by subset inclusion.Source: §3.2 · pp. 22–23

3.3 Transfer of multipartite expansion

  • The multipartite comparison transfers to relative links by dimension-reduced slices whose link levels and norms are unchanged.The proof applies the empty-type link estimate to a lower-dimensional slice around an arbitrary-type vertex.Source: §3.3 · pp. 25–26

4 Small-set coboundary expansion from square complexes

This section proves small-set coboundary expansion at every level below the top for imbalanced lossless square complexes, establishing expansion for sufficiently small locally minimal cochains. The proof controls overlap among local coboundaries using terminal ambiguity, heavy-vertex structure, lossless expansion, and imbalance assumptions.

4.1 Heavy and terminal vertices

  • In the small-set range, the heavy-vertex construction makes almost all heavy vertices belong to a unique terminal, keeping total terminal excess small.Starting from the initial cochain, heavy vertices are recursively defined using heavy-parent thresholds; vertices without heavy children are terminal.Source: §4.1 · pp. 27–28

4.2 The global to local reduction

  • The local-to-global comparison bounds global coboundary size using terminal-cluster coboundaries, with terminal excess accounting for overcounting and overlap.The identified overlap problems are multiple terminal membership and cancellation among cluster coboundaries at the next level.Source: §4.2 · pp. 28–29

4.3 Excess

  • Terminal ambiguity at a heavy vertex can arise only from ambiguity below it and new same-type or light-square charges; iterating this bound controls excess across levels.Same(a) and Light(a) capture the two identified ways heavy branches can fail to merge.Source: §4.3 · pp. 30–31

4.4 Same Type Collisions

  • Lossless expansion controls same-type collisions, one of the two level charges that must be bounded relative to the preceding heavy level.The other charge, from light squares, is handled using additional imbalance assumptions.Source: §4.4 · p. 32

4.5 Light Squares

  • Light-square charges are bounded by counting squares from their light lower vertices, assuming every set used in lossless estimates lies within its applicable lossless range.The section identifies additional imbalance assumptions as the ingredient for controlling this second type of error.Source: §4.4 · p. 32, §4.5 · p. 33

4.6 Heavy-mass propagation

  • Heavy-mass propagation relates error bounds at intermediate levels to the initial cochain norm by iterating a one-step comparison down the complex.The propagation lemma applies for levels 1 through r, and also for r+1 under the stated convention for γr.Source: §4.6 · p. 35

4.7 Choice of parameters and final error bound

  • The final parameter choice combines the imbalance condition and a conservative initial norm bound to ensure the lossless estimates apply throughout the proof.The text notes that this choice of c is conservative and could be improved by tracking heavy-mass propagation more closely.Source: §4.7 · p. 36
  • Imbalanced lossless k-dimensional square complexes yield small-set coboundary expansion at every level below the top for locally minimal cochains within the stated small-norm range.The theorem assumes the complex satisfies the imbalance condition and the initial cochain norm is at most c times the norm of the level set.Source: §4 · p. 26, §4.7 · p. 36
  • For 1 ≤ i ≤ r+1, ||Same_i||=O_k(ε⋆)||H_{i−1}||; for 2 ≤ i ≤ r+1, ||Light_i||=O_k(γ_{i−2})||H_{i−1}||.Source: §4.7 · p. 36
  • For every 0 ≤ r < k, locally minimal H_r with norm at most c||V_r|| expands by at least m_{k,r−1}−O_k.The constant c is as in (4.26).Source: §4.7 · p. 37

5 qLTC

This section shows that sufficiently imbalanced four-dimensional decorated square complexes yield quantum locally testable codes and a linear-time decoder for nearby cochains. It proves the decoder’s correctness using a queue invariant and induction to keep intermediate errors within the small-error regime.

5.1 Definitions

  • The section uses weighted local testability, with words and syndromes measured by their underlying complex’s level norms, comparable to Hamming weight up to constant factors.The CSS code is locally testable when both constituent classical codes are locally testable.Source: §5.1 · pp. 38–39

5.2 Construction and Proof

  • The proof uses greedy flipping and Theorem 4.10 for constant distance and soundness, while bottom-vertex-link local minimality adapts the decoder to this setting.Constant rate follows from an additional imbalance condition; the construction also extends to k ≥ 4 and three consecutive layers with specified stretch/shrinkage conditions.Source: §5.2 · pp. 39, 41
  • For a (4, 2)-cubical complex X, if X and Xrev satisfy Theorem 4.10’s assumptions with ε⋆ sufficiently small, μ1, μ2 ≥ 4, and μ3, μ4 ≤ 1, the resulting quantum error-correcting code has constant rate, relative distance, and local-testability soundness.Source: §5.2 · p. 40

5.3 Linear Time Decoder

  • For cochains sufficiently close to ker(δ2), Algorithm 2 runs in time linear in the syndrome norm and outputs a correction yielding a closest cochain in ker(δ2).The proposition also supplies a boundary adjustment; the running time is linear in the number of qubits.Source: §5.3 · p. 42
  • The queue invariant makes the terminal syndrome locally minimal, so Theorem 4.10’s expansion forces it to be zero.Any link-supported cochain that reduces the syndrome keeps its vertex in the queue, either because its coboundary overlaps a change made during the iteration or because it also reduces the preceding syndrome.Source: §5.3 · p. 43
  • An induction keeps the error within the small-error threshold because each iteration changes at most β=12 bits and the syndrome norm never increases.The proof uses the per-iteration change bound and nonincreasing syndrome norm to preserve the hypothesis needed to conclude that the final error is zero.Source: §5.3 · pp. 43–44
Loading 2610.00525v1…