betaFeedback

WorksPhysics and Astronomy

Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs

Abstract

We construct explicit two-sided lossless expanders whose binary adjacency matrices have full rank, and use them to obtain explicit asymptotically good quantum LDPC codes whose specified X- and Z-check matrices have full row rank and satisfy small-set soundness, or confinement, on a linear range. Our lossless expanders are a variant of those of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang, with a free action of a finite 2-group. Under such an action, injectivity and surjectivity of the adjacency matrix are detected on a fixed-size matrix indexed by vertex orbits. Adding a sparse factor to the gadget at the middle vertices of a single type then enforces full rank, with a controlled loss in expansion. To obtain the 2-group action, we observe that reducing the generators of the Lubotzky-Phillips-Sarnak Ramanujan graphs modulo powers of 2, instead of modulo an odd prime, gives Ramanujan Cayley graphs on finite 2-groups. This construction may be of independent interest. Plugging two such expanders into the balanced product of Lin and Hsieh gives the quantum codes, since full rank of the input graphs is inherited by the check matrices. Our construction supplies the code family sought by Hong, Guo, and Lucas. Applying their analysis, within their framework and under their dynamical assumptions, gives quantum memories whose free-energy density is analytic at every positive temperature and whose guaranteed lifetime is exp(Ω(N))exp(Ω(N)) at sufficiently low fixed positive temperature, where N is the blocklength. This improves the previously guaranteed stretched-exponential timescale.

Contents

1 Introduction 3

1.1 Small-set local testability and independent checks 3

1.2 Techniques 6

1.3 Concluding remarks 10

2 The Lin–Hsieh construction preserves full rank 10

2.1 The balanced product 10

2.2 Rank inheritance 12

3 A full-rank modification of HLMRZ 12

3.1 The HLMRZ construction 13

3.2 Equivariant maps and rank detection 14

3.3 The orbit matrix of the line product 15

3.4 The full-rank modification 16

4 LPS Ramanujan graphs on 2-groups 17

4.1 The graphs 18

4.2 The cubical complexes 22

5 Full-rank lossless graphs and the quantum code construction 23

5.1 Lossless graphs with a free 2-group action 24

5.2 Full-rank lossless expanders 25

5.3 The quantum codes 25

A Arithmetic background 29

A.1 Integral quaternions and the product structure 29

A.2 The LPS group and the tree 30

A.3 The Ramanujan property of congruence quotients 31

Introduction

Hong, Guo, and Lucas [6] showed that quantum information can remain protected for long times at low positive temperature even when the free-energy density is analytic at every positive temperature. Their construction brings together two properties of quantum LDPC codes: small-set confinement and independence of the specified sparse checks. Confinement supplies an energy penalty for errors, while independence makes the partition function exactly computable. Their work thus separates the dynamical protection of quantum information from the presence of a thermodynamic phase transition.

Their quantum examples have positive rate, but their distance and confinement range are of order N\sqrt{N}, where NN is the number of physical qubits, and their analysis guarantees a stretched-exponential memory timescale. They leave open whether the same combination can be achieved with asymptotically good quantum codes and confinement on a linear range. We answer this coding-theoretic question by constructing an explicit family of asymptotically good binary CSS quantum LDPC codes whose specified XX- and ZZ-check matrices have full row rank and satisfy confinement on a linear range. The requirement is simultaneous: independence and confinement hold for the same sparse checks.

The physical consequences follow by applying the analysis of [6] with our improved code parameters, within their framework and under their dynamical assumptions. This gives a guaranteed memory lifetime of exp⁡(Ω(N))\exp(\Omega(N)) at sufficiently low fixed positive temperature, while preserving thermodynamic analyticity. We refer to [6] for the physical interpretation and dynamical analysis. We now explain the coding problem and the challenges in obtaining both properties simultaneously.

Small-set local testability and independent checks

The classical case. A binary linear code is specified by a parity-check matrix

H:F2n⟶F2m,C=ker⁡H.H : \mathbb{F}_2^n \longrightarrow\mathbb{F}_2^m,\qquad C = \ker H.

The code is low-density parity-check (LDPC) when the row and column weights of HH are bounded by constants: each check reads constantly many bits, and each bit participates in constantly many checks. Full row rank means that the specified checks are linearly independent, in which case dim⁡C=n−m\dim C = n-m.

Suitable random biregular Tanner graphs give asymptotically good classical LDPC codes. Let dd be the degree of a bit vertex and d′>dd^{\prime} > d the degree of a check vertex, so that m=(d/d′)nm = (d/d^{\prime})n. For suitable fixed degrees, the random graph has, with high probability, lossless expansion on a linear range: there are constants α>0\alpha> 0 and ε<1/2\varepsilon< 1/2 such that

∣Γ(S)∣≥(1−ε)d∣S∣for every S⊆[n] with ∣S∣≤αn.|\Gamma(S)| \ge(1-\varepsilon)d|S| \qquad\text{for every } S \subseteq[n] \text{ with } |S| \le\alpha n.

At least (1−2ε)d∣S∣(1-2\varepsilon)d|S| check vertices then have exactly one neighbor in SS. Each such check is violated by the error supported on SS. Consequently,

∣He∣≥γ∣e∣whenever ∣e∣≤αn,γ=(1−2ε)d.(1)|He| \ge\gamma|e| \qquad\text{whenever } |e| \le\alpha n,\qquad\gamma= (1-2\varepsilon)d. \tag*{(1)}

In particular, every nonzero codeword has weight greater than αn\alpha n.

This also gives small-set local testability. If dist⁡(y,C)≤αn\operatorname{dist}(y,C) \le\alpha n, choose a nearest codeword c∈Cc \in C and apply (1) to e=y+ce = y + c. Since He=HyHe = Hy, we obtain

∣Hy∣≥γdist⁡(y,C).|Hy| \ge\gamma\operatorname{dist}(y,C).

As m=Θ(n)m = \Theta(n), a uniformly sampled check rejects yy with probability at least a constant times its relative distance from CC, throughout this small-set range.

When dd is odd, suitable random biregular ensembles also give full-row-rank matrices with high probability; see Appendix A of the preprint of [6]. Oddness avoids an immediate dependency: if every column has even weight, the sum of all rows is zero. Thus asymptotically good classical LDPC codes can simultaneously have independent sparse checks and small-set local testability.

Testing over the full range. To obtain an LTC tester from the specified matrix HH, one requires a constant κ>0\kappa> 0, independent of nn, such that

∣Hy∣≥κdist⁡(y,C)for every y∈F2n.|Hy| \ge\kappa\operatorname{dist}(y,C) \qquad\text{for every } y \in\mathbb{F}_2^n.

For asymptotically good codes, such a constant-query tester must use linearly many redundant checks beyond a basis of the dual code, as shown by Ben-Sasson, Guruswami, Kaufman, Sudan, and Viderman [3].

For the full-rank lossless matrices above, the obstruction can be seen directly. Choose the parameters so that γ>1\gamma> 1. Surjectivity of HH gives a word yy whose syndrome has weight one. By (1), every vector with this syndrome has weight greater than αn\alpha n. Adding a codeword preserves the syndrome, so

dist⁡(y,C)>αn,∣Hy∣=1.\operatorname{dist}(y,C) > \alpha n, \qquad|Hy| = 1.

Hence the specified checks cannot provide a constant-soundness test over the full range. This obstruction concerns the matrix HH; it does not rule out a different tester using redundant checks for the same code.

The quantum problem. We seek the same combination for quantum codes: positive rate, linear distance, small-set soundness on a linear range, and independent sparse checks. A binary CSS code is specified by two matrices

HX∈F2mX×N,HZ∈F2mZ×N,HXHZT=0.H_X \in\mathbb{F}_2^{m_X \times N}, \qquad H_Z \in\mathbb{F}_2^{m_Z \times N}, \qquad H_X H_Z^{T} = 0.

Their rows specify commuting XX- and ZZ-type checks, respectively, and their columns correspond to qubits. Commutation couples the two matrices, so the classical random construction cannot simply be applied independently to the two types of checks.

There is a further distinction: a nonzero error can be a stabilizer and therefore act trivially on the code. Error size must consequently be measured after reduction modulo stabilizers. For pure XX- and ZZ-errors, represented by x,z∈F2Nx,z \in\mathbb{F}_2^N, define

rX(x)=min⁡a∈F2mX∣x+HXTa∣,rZ(z)=min⁡b∈F2mZ∣z+HZTb∣.(2)r_X(x) = \min_{a \in\mathbb{F}_2^{m_X}} |x + H_X^{T}a|, \qquad r_Z(z) = \min_{b \in\mathbb{F}_2^{m_Z}} |z + H_Z^{T}b|. \tag*{(2)}

We require constants α,γ>0\alpha,\gamma> 0 such that

∣HZx∣≥γrX(x)whenever rX(x)≤αN,∣HXz∣≥γrZ(z)whenever rZ(z)≤αN.(3)\lvert H_Zx\rvert\ge\gamma r_X(x) \qquad\text{whenever } r_X(x) \le\alpha N, \\ \lvert H_Xz\rvert\ge\gamma r_Z(z) \qquad\text{whenever } r_Z(z) \le\alpha N. \tag*{(3)}

We call these the small-set soundness inequalities, with soundness coefficient γ\gamma on the range αN\alpha N. They give the small-set quantum local testability guarantee used here. In the physics literature this property is called confinement [6]. The reductions in (2) are modulo stabilizers, not modulo the entire syndrome kernels. A nontrivial logical operator has zero syndrome but positive reduced weight, so (3) also implies quantum minimum distance greater than αN\alpha N.

The additional requirement is

rank⁡HX=mX,rank⁡HZ=mZ.\operatorname{rank} H_X = m_X,\qquad\operatorname{rank} H_Z = m_Z.

As in the classical case, independence and soundness must hold for the same specified sparse checks. Deleting dependent checks preserves the code and sparsity, but can substantially decrease syndrome weights. Selecting a basis of the check rows therefore does not by itself establish the desired combination.

Previous quantum constructions. The hypergraph-product examples studied by Hong, Guo, and Lucas [6] already combine positive constant rate, independent sparse checks, and small-set soundness. Their soundness guarantee, however, holds only up to reduced weight cNc\sqrt{N}, for a constant c>0c > 0, and their distance is O(N)O(\sqrt{N}). The problem is to achieve linear distance and small-set soundness on a linear range while retaining independence of the specified checks.

Our results. Our first result is a family of explicit lossless expanders with full-rank adjacency matrices. A (ΔL,ΔR)(\Delta_L,\Delta_R)-biregular bipartite graph on L⊔RL \sqcup R is two-sided (c,ε)(c,\varepsilon)-lossless if every set SS of at most c∣L∣c\lvert L\rvert left vertices has at least (1−ε)ΔL∣S∣(1-\varepsilon)\Delta_L\lvert S\rvert neighbors, and symmetrically for sets of right vertices.

Theorem 1.1 (Full-rank lossless expanders). For every integer t≥1t \ge1, every ε>0\varepsilon> 0, and every amin⁡≥1a_{\min} \ge1, there are a positive integer a≥amin⁡a \ge a_{\min}, a constant c>0c > 0, and an explicit infinite family of (a,ta)(a,ta)-biregular bipartite graphs on L⊔RL \sqcup R with ∣L∣=t∣R∣\lvert L\rvert= t\lvert R\rvert, such that:

  1. each graph is two-sided (c,ε)(c,\varepsilon)-lossless;

  2. its binary adjacency map F2L→F2R\mathbb{F}_2^L \to\mathbb{F}_2^R has full row rank, and is invertible when t=1t=1;

  3. it admits a free action of a finite 22-group with a bounded number of orbits.

The neighbors of every vertex can be computed in time polynomial in the logarithm of the number of vertices.

Plugging two such graphs into the Lin–Hsieh balanced product gives quantum LDPC codes with the combination described above. The rate can be made arbitrarily close to one, and the soundness coefficient can be prescribed in advance.

Theorem 1.2 (Independent checks and small-set quantum local testability). Let t1,t2≥2t_1, t_2 \ge2 be integers and let γ0>0\gamma_0 > 0. There are constants α>0\alpha> 0 and w∈Z>0w \in\mathbb{Z}_{>0}, and an explicit infinite family of binary CSS codes with blocklengths N→∞N \to\infty, whose specified parity-check matrices HX,HZH_X, H_Z satisfy the following properties:

  1. HXHZT=0H_X H_Z^{T} = 0, both matrices have full row rank, and every row and column of either matrix has weight at most ww. Each qubit participates in at most 2w2w checks in total.

  1. The number KK of encoded qubits satisfies

KN=(t1−1)(t2−1)t1t2+1.\frac{K}{N} = \frac{(t_1-1)(t_2-1)}{t_1t_2+1}.
  1. The small-set soundness inequalities (3) hold with γ=γ0\gamma= \gamma_0. In particular, the quantum minimum distance is greater than αN\alpha N.

Every row and column of HX,HZH_X, H_Z can be enumerated in time polynomial in log⁡N\log N, after finite precomputation depending only on t1,t2,γ0t_1, t_2, \gamma_0.

Taking t1=t2=4t_1 = t_2 = 4 gives rate 9/179/17, while taking both integers large makes the rate approach one. The constants α\alpha and ww may depend on the chosen rate and soundness coefficient. The theorem establishes small-set quantum local testability on a linear range; it does not assert quantum local testability over the full range.

Techniques

The construction has two rank reductions. First, we reduce independence of the quantum checks to rank conditions on the input graphs of the Lin–Hsieh balanced product. Second, we show that, in a suitable variant of the HLMRZ construction, these conditions reduce to a rank test on a fixed finite gadget. The second reduction requires a free action of a finite 22-group. To supply this symmetry together with the required expansion, we construct LPS Ramanujan cubical complexes on a common family of finite 22-groups.

Rank inheritance in the Lin–Hsieh construction. Lin and Hsieh use the balanced product to construct a two-dimensional cubical object from two bipartite graphs with a common free group action [1, 9]. Directional losslessness is inherited from the input graphs, and their small-set estimate gives small-set soundness for a suitable choice of parameters (see also [4] for a higher-dimensional version). Our observation is that appropriate rank conditions are inherited as well.

Write the two input adjacency maps as

A:F2A0⟶F2A1,B:F2B0⟶F2B1.A : \mathbb{F}_2^{A_0} \longrightarrow\mathbb{F}_2^{A_1}, \qquad B : \mathbb{F}_2^{B_0} \longrightarrow\mathbb{F}_2^{B_1}.

Their balanced product has vertex blocks

Vij=(Ai×Bj)/G,i,j∈{0,1}.V_{ij} = (A_i \times B_j)/G, \qquad i,j \in\{0,1\}.

and the three-term complex

F2V20→δ0F2V10⊕F2V11→δ1F2V11.\mathbb{F}_2^{V_2^0} \xrightarrow{\delta_0} \mathbb{F}_2^{V_1^0} \oplus\mathbb{F}_2^{V_1^1} \xrightarrow{\delta_1} \mathbb{F}_2^{V_1^1}.

The associated CSS code has check matrices

HX=δ0T,HZ=δ1.H_X = \delta_0^T,\qquad H_Z = \delta_1.

Freeness of the group action makes each directional map a direct sum of copies of the corresponding input map. Consequently, injectivity of AA implies injectivity of δ0\delta_0, and surjectivity of BB implies surjectivity of δ1\delta_1. These are precisely the conditions that make HXH_X and HZH_Z have full row rank. Section 2 gives the argument. The remaining task is therefore to construct two-sided lossless bipartite graphs of suitable opposite imbalances, with full-rank adjacency maps and a common free group action.

References

  1. [1]Nikolas P. Breuckmann and Jens N. Eberhardt. Balanced product quantum codes. IEEE Transactions on Information Theory, 67(10):6653–6674, 2021. doi:10.1109/TIT.2021.3097347. Preprint: arXiv:2012.09271.DOI
  2. [2]Michael A. Bennett, Greg Martin, Kevin O’Bryant, and Andrew Rechnitzer. Explicit bounds for primes in arithmetic progressions. Illinois Journal of Mathematics, 62(1–4):427–532, 2018. doi:10.1215/ijm/1552442669. Preprint: arXiv:1802.00085.DOI
  3. [3]Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, and Michael Viderman. Locally testable codes require redundant testers. SIAM Journal on Computing, 39(7):3230–3247, 2010. doi:10.1137/090779875.
  4. [4]Itay Cohen, Itai Leigh, Assaf Reiner, Amnon Ta-Shma, and Elad Tzalik. Good quantum locally testable codes from lossless cubical complexes. Report TR26-202, Electronic Colloquium on Computational Complexity (ECCC), 2026. Preprint: arXiv:2610.00525.arxiv.org/abs/2610.00525
  5. [5]Leonard E. Dickson. Arithmetic of quaternions. Proceedings of the London Mathematical Society (2), 20:225–232, 1922.DOI
  6. [6]Yifan Hong, Jinkang Guo, and Andrew Lucas. Quantum memory at nonzero temperature in a thermodynamically trivial system. Nature Communications, 16:316, 2025. Article 316. doi:10.1038/s41467-024-55570-7. Preprint: arXiv:2403.10599.DOI
  7. [8]Martin Kneser. Strong approximation. In Algebraic Groups and Discontinuous Subgroups (Boulder, Colo., 1965), volume 9 of Proceedings of Symposia in Pure Mathematics, pages 187–196. American Mathematical Society, Providence, RI, 1966.DOI
  8. [9]Ting-Chun Lin and Min-Hsiu Hsieh. Good quantum LDPC codes with linear time decoder from lossless expanders. arXiv:2203.03581v1, 2022. Version 1. Numbered statements refer to this version.arxiv.org/abs/2203.03581
  9. [10]Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. doi:10.1007/BF02126799.DOI
  10. [11]Alexander Lubotzky and Dan Segal. Strong approximation for linear groups. In Subgroup Growth, volume 212 of Progress in Mathematics, pages 389–407. Birkhäuser, Basel, 2003.DOI

Paper details

vlnc:W_jtf5t6qj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents