REVIEW 3 major objections 3 minor 17 references
Reed-Muller Codes for Quantum Pauli and Multiple Access Channels
T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Reed-Muller codes can decode quantum Pauli noise over a whole region, not just single channels.
desk verdict Plausible RM-MAC rate region, but the quantum universality claim leans on an asserted reduction that needs a real proof. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof generalizes the bending and boosting arguments from single-user RM capacity proofs to the two-user setting. Bending shows that a pair of RM codes with total rate below the channel's mutual information achieves merged weak local decoding, meaning some bit of one codeword, the other codeword, or their XOR can be guessed with accuracy $1/2+\Omega(1)$. Boosting then amplifies this weak local guess into full recovery of one codeword with probability $1-o(1)$. Finally, a reduction argument shows that after recovering one codeword or their XOR, the remaining codeword is decoded on an effective binary channel whose capacity exceeds its rate, completing the proof.
What would settle it
For a concrete noise distribution on a Q-MAC, compute the four mutual informations, pick RM code rates satisfying all inequalities of Theorem 2, and run a maximum-likelihood joint decoder at moderately large blocklengths; if the empirical error probability does not decay to zero as blocklength grows, the theorem's sufficiency claim is false. Alternatively, find a Pauli channel $(p_X,p_Y,p_Z)$ inside the claimed region of Figure 2(b) for which the quantum CSS RM code with $R_1=R_2=0.8$ fails to decode with high probability.
Extended reading notes
Core claim
The central claim is Theorem 2: if two RM codes of rates $R_1$ and $R_2$ are used on a Q-MAC with correlated noise distribution $P_{\mathrm{noise}}$, and the four conditions $R_1+R_2 < I[(X^{(1)}_0,X^{(2)}_0);Y_0]$, $R_1 < I[X^{(1)}_0;X^{(2)}_0,Y_0]$, $R_2 < I[X^{(2)}_0;X^{(1)}_0,Y_0]$, and $\min(R_1,R_2) < I[X^{(1)}_0;X^{(1)}_0+X^{(2)}_0,Y_0]$ hold, then the receiver can recover both codewords from the channel output with probability $1-o(1)$. Adding the CSS condition $R_1+R_2\ge 1$ makes this a statement about quantum RM codes on Pauli channels: the same code can decode errors for all noise parameters below the hashing bound in a two-dimensional region, rather than only at isolated points.
Load-bearing premise
The paper assumes that decoding the random codeword generated by the Steane method is exactly equivalent to finding the error that occurred on the original quantum state, but this equivalence is stated informally and not proven.
Editorial extensions
If this is right
- If the theorem is correct, quantum CSS RM codes with component rates $R_1$ and $R_2$ achieve the hashing bound over a full two-dimensional region of Pauli noise parameters, making them universal in the sense of being rate-optimal for many channels simultaneously.
- Joint decoding of the two error components strictly dominates successive decoding, which can only touch the optimal rate along one-dimensional curves.
- The necessary conditions in Theorem 1 show that the four inequalities are not just sufficient for RM codes but also required for any code pair, so the achievable region is tight for RM codes.
- The tensor-product variant of RM codes relaxes the condition $\min(R_1,R_2) < I[X^{(1)}_0;X^{(1)}_0+X^{(2)}_0,Y_0]$ to $R_1R_2 < I[X^{(1)}_0;X^{(1)}_0+X^{(2)}_0,Y_0]$, potentially enlarging the achievable region for MAC applications.
- Since the CSS condition $R_1+R_2\ge 1$ is compatible with the theorem's region, quantum RM codes with rate above $0.5$ can be used to correct Pauli noise at rates up to the hashing bound.
Reading between the lines
- A natural testable extension is to simulate joint decoding of RM codes on finite-length Q-MACs to see how quickly the error probability approaches zero as blocklength grows, which would give practical evidence for the asymptotic claim.
- The same bending-boosting framework might extend to more than two users or to non-symmetric channels, since the core mechanism only requires transitivity and a well-defined intersection structure between codes.
- The paper's emphasis on overlapping codes suggests that classical MAC capacity regions for RM codes depend delicately on the intersection $C_1\cap C_2$, and codes engineered to control this intersection (e.g., via tensor products) could achieve rate points outside the standard rectangle.
- If the Steane-method equivalence holds rigorously, then the universality result implies that a single quantum RM code can serve as a robust building block for fault-tolerant protocols where the noise model is not precisely known in advance.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies two-user multiple-access channels with binary inputs and additive correlated noise, which it calls Q-MACs. It presents Theorem 1, a set of necessary conditions for jointly recovering both codewords for arbitrary linear codes, and Theorem 2, which claims that these conditions are sufficient when both component codes are Reed-Muller codes, using the bending and boosting machinery of [1]. The paper then adds the CSS condition R1+R2 >= 1 and claims that a quantum RM code built from the two classical RM codes can correct Pauli noise over a two-dimensional region of channel parameters, whereas successive decoding is optimal only along one-dimensional curves. Figures 2 and 3 illustrate this claimed universality for R1 = R2 = 0.8.
Significance. If the results are correct, the paper would give a nontrivial extension of the known capacity-achieving properties of RM codes from scalar BMS channels to a class of two-user MACs with vector outputs, and it would identify a clean information-theoretic reason why joint decoding of quantum RM codes can beat successive decoding over a whole range of Pauli channels. The rate conditions are explicit and parameter-free, and the plotted regions are reproducible consequences of the displayed inequalities; no parameters are fitted to data. The main caveat is that the quantum bridge from Pauli decoding to Q-MAC decoding is asserted rather than proved, so the quantum significance is conditional on that bridge being formalized.
major comments (3)
- [§II.A, §III.C] The reduction from quantum Pauli decoding to Q-MAC decoding is the load-bearing step for the paper's quantum claims, but it is only asserted. Definition 1 says 'we show' that CSS decoding reduces to Q-MAC decoding, yet no formal statement or proof of this reduction appears anywhere. In §III.C the sole justification is the sentence that Steane's method 'generates a random codeword affected by the original noise vector, and decoding this random codeword is equivalent to finding the error.' This leaves unspecified: which of C1 and C2 (or their duals) is used in each of the two ancilla measurements; why the two ancilla codewords are uniform and independent; how the two n-bit measurement outcomes are identified with Y in Definition 1; and how the CSS condition C1^⊥ ⊆ C2 enters the Q-MAC conditions. Since Figures 2 and 3 and the abstract's universality claim are all derived from this bridge, the quantum conclusion is currently unsupported even if Theorem 2 is correct. A formal lemma showing that the two Steane measurements produce (U1 + Δ_X, U2 + Δ_Z) with U1 uniform in C1 and U2 uniform in C2 is needed.
- [§III.B (Theorem 2 proof)] The proof of Theorem 2 is a compressed sketch that does not state the generalized 'bending' and 'boosting' lemmas imported from [1] or verify their hypotheses for a two-user MAC with vector output. In particular, the inference from H[X_i' | Y'_-i] ≤ 2 - Ω(1) to weak local decoding of X_i^(1)', X_i^(2)', or their sum with accuracy 1/2 + Ω(1) needs a quantitative argument; bounding the joint entropy of a pair by 2 - δ does not by itself identify which of the three binary functions is predictable. The boosting step also requires that, after conditioning on the recovered codeword, the residual channel for the remaining component is a binary-input memoryless symmetric channel on which the RM capacity theorem of [1] applies; this is not shown for the conditional channels arising from a general P_noise. These are the core mechanisms of the theorem, not presentation details.
- [§III.A (Theorem 1, condition 4)] The proof of condition (4) of Theorem 1 is sketched imprecisely. Given S = X^(1) + X^(2), the ambiguity in X is a coset of C1 ∩ C2 only if the representative X* is chosen among valid pairs achieving the sum S; the paper's wording allows an arbitrary pair with the right sum, which does not yield δ_x ∈ C1 ∩ C2. The proof also asserts, without derivation, that the per-symbol channel from δ_x to (δ_x, δ_x) + Δ has capacity I[X_0^(1); X_0^(1)+X_0^(2), Y_0]. Both facts are plausible, but they need to be stated and proved, since they support the necessary condition (4) and hence the claimed tightness of the rate region.
minor comments (3)
- [§III.C and Fig. 2] The text says 'the conditions for successful successive decoding considered in Fig. 2b' but Fig. 2b is labeled 'Region of channels decodable by joint decoding'; the reference should be to Fig. 2a.
- [§II.A] The term 'non-degenerate decoding' is used in Definition 1 and Section II.A but is never defined; if it means anything stronger than ordinary decoding, it should be formalized, and if not, it should be removed.
- [§III.A] Theorem 1 writes log_2(|C1 ∩ C2|)/n as if the intersection size were fixed for finite n; in the asymptotic setting the statement should use a limsup or an explicit dependence on n to avoid ambiguity.
Circularity Check
No significant circularity: the Q-MAC rate region is derived from independent inequalities, reliance on [1] is legitimate prior support, and the unproved Steane-to-Q-MAC bridge is a missing-proof concern, not a circular one.
full rationale
The derivation chain is not circular. Theorem 2's achievable region follows from Theorem 1's necessary inequalities plus the bending/boosting lemmas of [1], transitivity of RM codes, and capacity arguments for residual single-user channels; no parameter is fitted to data and the 2D decodable region is a consequence of the inequalities, not an input. The only self-citation is [1] (Abbe and Sandon, FOCS 2023) for bending and boosting; that is an independent published proof, and the paper extends it to a MAC rather than importing the target claim, so it does not raise the circularity score. The flagged weakness is the asserted MAC-to-quantum reduction in Sections II.A and III.C: 'the Steane method for syndrome extraction [13], as this method generates a random codeword affected by the original noise vector, and decoding this random codeword is equivalent to finding the error.' This reduction is not proved here, and the quantum universality figures depend on it; however, that is an omitted-support/correctness gap, not a case where the quantum conclusion is used to define the Q-MAC conditions or where the prediction reduces by construction to a fit. Thus no circular step is exhibited.
Assumptions & free parameters
assumptions (4)
- domain assumption Reed-Muller codes are transitive and nested, with X^(1)+X^(2) a codeword of RM(max(r1,r2),m)
- domain assumption The bending and boosting lemmas from [1] extend to vector-output Q-MAC channels
- domain assumption Steane syndrome extraction reduces quantum Pauli decoding to codeword decoding on the Q-MAC
- standard math Standard Shannon information inequalities and chain rules hold for the defined random variables
Cite this review
Pith. "Pith review of Reed-Muller Codes for Quantum Pauli and Multiple Access Channels." pith.science (2026). https://pith.science/paper/X6OMWVHE
@misc{pith2026250608651,
author = {Pith},
title = {Pith review of: Reed-Muller Codes for Quantum Pauli and Multiple Access Channels},
year = {2026},
howpublished = {\url{https://pith.science/paper/X6OMWVHE}},
note = {Machine review of arXiv:2506.08651}
}
read the original abstract
Reed-Muller (RM) codes have undergone significant analytical advancements over the past decade, particularly for binary memoryless symmetric (BMS) channels. We extend the scope of RM codes development and analysis to multiple-access channels (MACs) and quantum Pauli channels, leveraging a unified approach. Specifically, we first derive the achievable rate region for RM codes on so-called Q-MACs, a class of MACs with additive correlated noise. This is achieved via a generalization of the bending and boosting arguments defined in arXiv:2304.02509. We then put forward a connection between the rate region of these QMACs and quantum RM codes designed for Pauli noise channels. This connection highlights a universality property of quantum RM codes, demonstrating their rate-optimal performance across a range of channel parameters, rather than for a single Pauli channel.
Figures
Reference graph
Works this paper leans on
-
[1]
A proof that Reed-Muller codes achieve shannon capacity on symmetric channels,
E. Abbe and C. Sandon, “A proof that Reed-Muller codes achieve shannon capacity on symmetric channels,” in2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, pp. 177–193
work page 2023
-
[2]
A class of multiple-error-correcting codes and the decoding scheme,
I. Reed, “A class of multiple-error-correcting codes and the decoding scheme,”Transactions of the IRE Professional Group on Information Theory, vol. 4, no. 4, pp. 38–49, 1954
work page 1954
-
[3]
Application of boolean algebra to switching circuit design and to error detection,
D. E. Muller, “Application of boolean algebra to switching circuit design and to error detection,”Transactions of the I.R.E. Professional Group on Electronic Computers, vol. EC-3, no. 3, pp. 6–12, 1954
work page 1954
-
[4]
Reed–Muller codes: Theory and algorithms,
E. Abbe, A. Shpilka, and M. Ye, “Reed–Muller codes: Theory and algorithms,”IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3251–3277, 2020
work page 2020
-
[5]
From polar to Reed- Muller codes: A technique to improve the finite-length performance,
M. Mondelli, S. H. Hassani, and R. L. Urbanke, “From polar to Reed- Muller codes: A technique to improve the finite-length performance,” IEEE Transactions on Communications, vol. 62, no. 9, pp. 3084–3091, 2014
work page 2014
-
[6]
On optimality of css codes for transversal t,
N. Rengaswamy, R. Calderbank, M. Newman, and H. D. Pfister, “On optimality of css codes for transversal t,”IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 2, pp. 499–514, 2020
work page 2020
-
[7]
Reed-Muller codes achieve capacity on erasure channels,
S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. ¸ Sa¸ so ˘glu, and R. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” inProceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 658–669
work page 2016
-
[8]
G. Reeves and H. D. Pfister, “Reed-Muller codes achieve capacity on bms channels,”arXiv preprint arXiv:2110.14631, vol. 4, no. 6, p. 7, 2021
work page Pith review arXiv 2021
Show all 17 references
-
[9]
Scheme for reducing decoherence in quantum computer memory,
P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,”Phys. Rev. A, vol. 52, pp. R2493–R2496, Oct 1995. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.52.R2493
1995 doi
-
[10]
Good quantum error-correcting codes exist,
A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,”Physical Review A, vol. 54, no. 2, p. 1098, 1996
1996
-
[11]
Error correcting codes in quantum theory,
A. M. Steane, “Error correcting codes in quantum theory,”Physical Review Letters, vol. 77, no. 5, p. 793, 1996
1996
-
[12]
Qubit css code,
“Qubit css code,” inThe Error Correction Zoo, V . V . Albert and P. Faist, Eds., 2024. [Online]. Available: https://errorcorrectionzoo.org/ c/qubit_css
2024
-
[13]
An introduction to quantum error correction and fault-tolerant quantum computation,
D. Gottesman, “An introduction to quantum error correction and fault-tolerant quantum computation,” 2009. [Online]. Available: https: //arxiv.org/abs/0904.2557
2009 arXiv
-
[14]
Mixed-state entanglement and quantum error correction,
C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, “Mixed-state entanglement and quantum error correction,”Physical Review A, vol. 54, no. 5, p. 3824, 1996
1996
-
[15]
Quantum Reed-Muller codes,
A. Steane, “Quantum Reed-Muller codes,” 1996. [Online]. Available: https://arxiv.org/abs/quant-ph/9608026
1996 arXiv
-
[16]
Quantum Reed-Muller codes,
L. Zhang and I. Fuss, “Quantum Reed-Muller codes,” 1997. [Online]. Available: https://arxiv.org/abs/quant-ph/9703045
1997 arXiv
-
[17]
Quantum polar codes,
A. Goswami, “Quantum polar codes,” Ph.D. dissertation, Université Grenoble Alpes, 2021
2021
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.