REVIEW 5 minor 2 references
Algebraic expander codes yield quantum CSS codes with transversal CCZ and sublinear-weight Z-stabilizers.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-15 10:38 UTC pith:JSQ5WXMD
load-bearing objection Solid algebraic fix that recovers linear dimension and one-sided sublinear Z-checks for transversal CCZ; worth engaging.
Quantum Codes with Transversal CCZ Gates and Sublinear Z-Stabilizers
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For every fixed m ≥ 3 the algebraic expander codes of local rate r < 1/3 produce explicit growing-alphabet CSS codes of length N, dimension Θ(N) and distance Ω(N^{1/m}) that support transversal CCZ, and whose Z-stabilizer space is generated by checks of weight O(N^{1/m}). After projective-multiplicity alphabet reduction the same codes exist over any fixed prime field with near-linear dimension, distance n^{1/m} up to polylog factors, and Z-generator weight still sublinear up to polylog factors.
What carries the argument
The refined puncturing theorem: an A-dependent dual-distance condition d_A(C^ op) replaces the usual global dual-distance bound, allowing a linear-size interpolation set A taken from a lower-rate algebraic expander code while still guaranteeing that every nonzero dual word retains Ω(N^{1/m}) weight outside A.
Load-bearing premise
The construction treats the algebraic expander codes as black-box inputs whose duals are generated by the local Reed-Solomon duals of length O(N^{1/m}) and that keep positive rate and linear distance even in the low-rate regime needed for triple Schur products.
What would settle it
Exhibit an algebraic expander code family with the claimed Tanner parameters for which no linear-size interpolation set A of a lower-rate sibling satisfies d_A(C^ op) = Ω(N^{1/m}), or compute that every generating set of the resulting Z-stabilizer space after puncturing has weight Ω(N).
If this is right
- One-sided sublinear stabilizer locality is achievable inside the classical Schur-product puncturing framework for transversal CCZ.
- Growing-alphabet CSS codes with linear dimension, polynomial distance and transversal CCZ exist for every fixed m ≥ 3.
- Alphabet reduction to any fixed prime field preserves transversal CCZ and sublinear Z-generator weight up to polylogarithmic factors.
- The Z-checks admit an explicit combinatorial description (single-orbit duals plus two-orbit gluing checks) that can be written down from the Tanner structure alone.
Where Pith is reading between the lines
- If an efficient decoder for the underlying algebraic expander codes can be lifted through the refined puncturing map, the same family would give an efficiently decodable quantum code with transversal CCZ.
- The asymmetry between X- and Z-stabilizer weights suggests that a dual construction or a different choice of logical set might produce two-sided sublinear locality without leaving the algebraic setting.
- The same refined puncturing idea may apply to other classical codes whose dual distance is small but whose duals still have large support outside carefully chosen interpolation sets.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs CSS codes with transversal CCZ from algebraic expander codes of Kopparty–Tamo. The main technical step is a refined puncturing theorem (Theorem 3.1) that replaces the global dual-distance hypothesis of Golowich–Guruswami by an A-dependent distance d_A(C^⊥). Instantiating with an interpolation set A for a lower-rate expander code C_{r0} yields growing-alphabet codes [[N, Θ(N), Ω(N^{1/m})]]_q supporting transversal CCZ, together with an explicit generating set for the Z-stabilizers of weight O(N^{1/m}) (Theorem 4.6, Proposition 4.7). Alphabet reduction via projective-multiplicity multiplication-friendly codes then produces fixed-prime-field triples of length n with dimension Ω(n/(log n)^4), distances Ω(n/(log n)^4) and Ω(n^{1/m}/(log n)^{4/m}), and Z-generator weight O(n^{1/m}(log n)^{1−4/m}) (Theorem 5.4).
Significance. The work shows that the algebraic Schur-product puncturing framework can produce one-sided sublinear stabilizer locality without sacrificing linear dimension. The refined puncturing theorem is a clean, reusable abstraction; the explicit gluing generators g_a for the shortened dual and the weight-tracking through projective-multiplicity alphabet reduction are concrete contributions. While the codes are not qLDPC and locality is only one-sided, the construction sits in a natural technical lineage (KT19, GG25a, KT26) and supplies parameters that were previously unavailable inside that lineage. The dependence on the concurrent classical expander family is properly flagged and does not undermine the quantum arguments once those classical properties are granted.
minor comments (5)
- Abstract and Theorem 4.6 state d_X = Θ(N) while the body of the theorem only lower-bounds the CSS distance by min{δ_r N − |A|, ⌊(r−r0)L⌋+1}; the matching upper bound on d_X follows from Remark 4.8 but should be stated explicitly in the theorem statement for consistency with the abstract.
- In Proposition 4.7 the claim |A ∩ O| ≤ k_O(r0) is correct, yet the subsequent inequality k_O(r0)+k_O(r) ≤ |O| for large N is used without an explicit N0; a one-line quantitative bound would make the argument fully self-contained.
- Section 5.1 introduces projective-multiplicity codes over P^1(F_q); a short comparison with the affine multiplicity codes of GJX17 would help readers unfamiliar with the projective formulation.
- A few bibliographic inconsistencies appear (GG24 vs GG25a in the abstract versus body; arXiv dates). Standardize the citations.
- The open-problem paragraph on decoding is welcome; a sentence on whether the Tanner structure of C_r already yields an efficient classical decoder that could be lifted would strengthen the discussion.
Circularity Check
Minor load-bearing self-citation of coauthored algebraic expander codes [KT26]; refined puncturing, low-weight Z-generators, and alphabet reduction are independent of that input.
specific steps
-
self citation load bearing
[§2.3 Thm 2.7; invoked throughout §4 (esp. Lem 4.1–4.2, Prop 4.4, Prop 4.7, Thm 4.6)]
"We now provide the needed notation and results of the algebraic expander code construction given in [KT26]. ... Theorem 2.7. [KT26, Theorem 4.3] For any fixed m≥3, r∈(0,1), and characteristic p, there exists an explicit family of algebraic expander codes C_r of length N ... with the following properties ... 1. C_r is a Tanner code. ... C^⊥_r = ∑_{O∈O} R_O(r)^⊥ ... 3. The global relative distance is at least (1−r)^2. 4. The global rate is at least r^{2m+1}/(2m+1)!."
The entire quantum construction (linear dimension via refined puncturing, sublinear Z-generators via local duals, Schur-product distance for CCZ) treats the existence and listed properties of C_r as black-box inputs. Those inputs come from a paper coauthored by Tamo. Without them the A-dependent distance claim and the orbit-supported generators collapse. This is load-bearing self-citation, but only of classical structural facts that do not themselves encode the target quantum parameters; the new theorems remain independent once the black box is granted.
full rationale
This is a pure constructive coding-theory paper with no fitted parameters, no empirical predictions, no uniqueness theorems, and no ansatz smuggling. The derivation chain is: (i) black-box classical algebraic expander codes C_r from [KT26, Thm 4.3] (Tanner structure, dual generated by local RS duals of length O(N^{1/m}), rate/distance bounds, Schur containment C_r^{*3} ⊆ C_{3r} for r<1/3); (ii) new refined puncturing theorem (Thm 3.1) that replaces global dual-distance by an A-dependent condition d_A(C^⊥); (iii) choice of A as interpolation set for lower-rate C_{r0} (Prop 4.4) yielding linear dimension; (iv) explicit low-weight generators for the shortened dual via orbit sparsity (Prop 4.7); (v) projective-multiplicity multiplication-friendly codes + GG alphabet reduction with weight tracking (Thm 5.4). Steps (ii)–(v) are self-contained once the classical black-box properties are granted; they do not redefine those properties or force the quantum parameters by construction. The only circularity-adjacent item is the coauthored citation [KT26] (Tamo) that supplies the classical family; this is ordinary domain input, parameter-free, and does not include the target quantum claims, so it raises the score only to the minor-self-citation level (2). No reduction of the form “Eq. X = Eq. Y by definition” or “fitted quantity renamed prediction” exists.
Axiom & Free-Parameter Ledger
free parameters (3)
- m ≥ 3 (orbit-size exponent)
- local rates r0 < r < 1/3 and fraction α
- multiplicity profile (ℓ_P) and τ ≤ p
axioms (4)
- domain assumption Algebraic expander codes C_r of [KT26, Thm 4.3] have Tanner dual generation by local RS duals, rate ≥ r^{2m+1}/(2m+1)!, relative distance ≥(1−r)^2, and local length O(N^{1/m}).
- standard math CSS puncturing/shortening dualities (Eq. 1) and GG transversal-CCZ identity (Def. 2.4 / Lemma 2.5).
- domain assumption Subadditivity of u-base degree (Lemma 2.6 from [KT26]) for products of polynomials under g- and h-base degrees.
- domain assumption Guruswami–Golowich alphabet-reduction / concatenation with restriction (Prop 5.3 / [GG25a, Prop 5.1]).
invented entities (3)
-
A-punctured distance d_A(C)
no independent evidence
-
Projective-multiplicity multiplication-friendly codes over P^1(F_q)
independent evidence
-
Gluing Z-checks g_a = h_{G·a,a} − h_{H·a,a}
independent evidence
read the original abstract
We construct asymmetric quantum CSS codes with transversal \(CCZ\) gates from algebraic expander codes \cite{KT26}. For every fixed \(m\ge 3\), our growing-alphabet codes have length \(N\), dimension \(\Theta(N)\), and distances \[ d_X=\Theta(N), \qquad d_Z=\Theta(N^{1/m}). \] Moreover, the \(Z\)-stabilizer space has an explicit generating set of weight \(O(N^{1/m})\). We build on the algebraic puncturing framework of Golowich and Guruswami \cite{GG24}, which turns classical codes with the required Schur-product and distance conditions into CSS codes with transversal \(CCZ\). However, applying the framework directly to the algebraic expander codes runs into their small dual distance, and therefore produces only sublinear dimension. Our main technical step is a refined puncturing theorem in which the global dual-distance assumption is replaced by a condition only on the selected puncturing set. We also reduce the alphabet to a fixed prime field using a projective-multiplicity version of multiplication-friendly codes. The resulting fixed-prime-field CSS code triples, of length \(n\), still have transversal \(CCZ\) gates. Their dimension is \(\Theta(n/(\log n)^4)\), with distances \[ d_X=\Omega\!\left(\frac{n}{(\log n)^4}\right), \qquad d_Z=\Omega\!\left(\frac{n^{1/m}}{(\log n)^{4/m}}\right), \] and the \(Z\)-stabilizer generating set remains sublinear.
Reference graph
Works this paper leans on
-
[1]
Quantum LDPC codes with transversal non-clifford gates via products of algebraic codes
[GL25] Louis Golowich and Ting-Chun Lin. Quantum LDPC codes with transversal non-clifford gates via products of algebraic codes. InProceedings of the 57th Annual ACM Sympo- sium on Theory of Computing, STOC 2025, pages 689–696. Association for Computing Machinery,
2025
-
[2]
[Ngu25] Quynh T. Nguyen. Good binary quantum codes with transversal CCZ gate. InProceed- ings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, pages 697–706. Association for Computing Machinery,
2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.