Imagine you're building a fence out of prefabricated panels. Each panel is a permutation matrix — a rigid, pre-shaped piece that slots in neatly. You tile a whole grid of them, J rows by L columns, hoping the resulting fence is strong everywhere. Kasai proves that no matter how many panels you add, the fence always has a weak spot that stays roughly the same absolute size while the fence grows arbitrarily long. The relative strength goes to zero. The committed claim: CSS quantum LDPC codes constructed as full J×L arrays of uniformly random P×P permutation matrices, subject to the commutativity constraint required for CSS codes, have relative minimum distance converging to zero in probability as P→∞. This is a negative result — it rules out a construction, not enables one. The proof strategy is elegant and information-theoretic. Kasai analyzes weight enumerators that count nontrivial logical operators (codewords modulo stabilizers). He establishes a coefficientwise lower bound showing that at every fixed relative weight 0<α<1 along even-weight sequences, exponentially many such logical representatives exist with high probability. The exponent lower bound is h₂(α)/2, where h₂ is the binary entropy function. Because these representatives exist at every fixed relative weight δ for any δ>0, the minimum distance cannot be a constant fraction of block length n=LP. The comparison with classical LDPC weight enumerators is instructive: classical random regular LDPC codes DO achieve linear minimum distance. The commutativity constraint is the poison pill. Where does this sit in the field? The quantum LDPC code community has been hunting for explicit, efficiently decodable codes with constant rate and linear distance — the quantum analogue of what Gallager codes achieve classically. Panteleev-Kalachev (2022) and others have shown such codes exist via more sophisticated constructions (lifted product codes, balanced product codes). The permutation-matrix-array construction studied here is simpler and more natural, but Kasai shows it cannot deliver. This is a clean boundary result: it tells the community exactly which road is a dead end. The integrity of this result is high. It is a mathematical proof, not a simulation. The weight-enumerator lower bound is derived analytically, and the distance conclusion follows deterministically from the existence of low-weight logical operators. There is no cherry-picking risk — the result holds for all fixed J≥3 and even L>2J. The comparison with classical LDPC and dense CSS exponents provides context, though no numerical benchmarking is involved because this is a theorem, not an algorithm. The milestone question for the broader quantum LDPC field is whether explicit constructions with constant rate AND linear distance can be made efficiently decodable with practical circuit depth. Panteleev-Kalachev codes exist but decoding them at scale remains open. Kasai's contribution is to close a door — permutation-matrix arrays won't get you there — which redirects effort toward the constructions that might. The obvious next experiment Kasai did not run: extending the analysis to partial arrays (not full J×L grids) or to structured (non-uniform) distributions over permutation matrices. The full-array, uniform-random setting is the cleanest analytically, and relaxing either constraint would require substantially different techniques. My read: this is (a) — the cleaner setting was tractable, the extensions are genuinely harder, and Kasai chose to prove the strongest clean result first.
The analogy
You're tiling a floor with identical square tiles, hoping the pattern is strong everywhere. Each tile is a permutation matrix — a rigid, symmetric unit. Kasai proves that no matter how large the floor gets, the tiled pattern always has a crack that doesn't shrink relative to the floor size. The tiles' rigidity, which makes them easy to lay, is exactly what prevents them from covering all weaknesses.
Tile floor
Identical rigid tiles laid in a full grid — easy to assemble but always leaves a proportionally-fixed weak seam
Permutation CSS
Full J×L arrays of P×P permutation matrices — easy to construct but always admit low-weight logical operators
Honest assessment
A clean, well-executed negative result that tells the quantum LDPC community to stop looking for good codes in the permutation-matrix-array bin. The proof technique — weight-enumerator lower bounds showing exponentially many low-weight logical operators — is rigorous and general within its scope. This won't excite anyone building hardware tomorrow, but it's exactly the kind of boundary-drawing that saves years of wasted effort. Theorists working on quantum code constructions should read it; everyone else can file it under 'road closed.'
What Is CLAIMS?
70
/ 100
BedrockNews applies a structured analytical framework called CLAIMS to academic papers and technical research releases.
How CLAIMS worksClaim
3/5
Ladder
4/5
Architecture
4/5
Integrity
5/5
Milestone
2/5
Successor
3/5
What is this paper actually committing to?
Clean negative result: proves a natural quantum LDPC construction family cannot achieve linear distance. Not a first-of-kind breakthrough, but a definitive boundary marker that the community needs.
The field fight
Can simple, structured constructions (permutation arrays, bicycle codes) achieve good quantum LDPC codes, or do you need algebraically sophisticated constructions (lifted products, balanced products)?
Side A
Simple constructions may suffice with the right parameter choices; they're easier to decode and implement
Held by: Bicycle codes, permutation-array proponents, hardware-first groups
Side B
Algebraic sophistication is unavoidable for constant-rate linear-distance quantum LDPC; simple constructions hit fundamental walls
Held by: Panteleev-Kalachev, Leverrier-Zémor, this paper
Milestone tracker
Unlocks: Practical fault-tolerant quantum computing with constant overhead
Current
0
relative distance
permutation-array CSS codes (this paper proves limit)
Next
Θ(n)
distance
decodable quantum LDPC at ~1000 qubits
Unknown — decoder engineering is the bottleneck, not existence proofs
Verified Facts (5)
CSS check matrices formed as full J×L arrays of arbitrary P×P permutation matrices, sampled uniformly subject to commutation
For fixed column weight J≥3 and fixed even row weight L>2J, relative minimum distance converges to zero in probability as P→∞, with block length n=LP
At every fixed relative weight 0<α<1 along even-weight sequences, exponentially many nontrivial logical representatives exist with high probability
Typical and mean counts have exponent lower bound h₂(α)/2, where h₂ is the binary entropy function
17 pages, 1 figure
Practical Implications (3)
Groups exploring permutation-matrix-array quantum LDPC codes for near-term hardware should pivot to more algebraically complex constructions like lifted product or balanced product codes
The h₂(α)/2 exponent bound on logical operator counts provides a quantitative tool for analyzing weight distributions in related CSS code families
Reinforces that the commutativity constraint in CSS codes is a fundamental structural obstacle absent in classical coding theory — not just a technical nuisance
More latest news
Read all