{"id":"0811d6c9-ff17-4c12-a3e1-9ba8492affd9","arxiv_id":"2506.08651","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Reed-Muller codes achieve the full achievable rate region on two-user additive-noise channels, and the resulting quantum CSS codes meet the hashing bound across a continuous range of Pauli noise parameters.","lead":"This paper proves new limits on how well Reed-Muller error-correcting codes can transmit two messages at once over a noisy channel, including a model tied to quantum noise. It shows the same quantum code can optimally handle a whole range of noise levels, not just one.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The quantum universality claim rests on an unproved reduction from CSS Steane decoding to Q-MAC decoding in Section III.C; without a formal statement of this reduction, the paper's central quantum conclusion is unsupported even if Theorem 2 is correct.","rationale":"The paper's strongest claim is Theorem 2 plus the quantization step in Section III.C. Theorem 2 is a plausible extension of the FOCS 2023 bending/boosting argument, and the reader already flagged the compressed proof. My stress-test focuses on the quantum bridge. The reduction is likely standard and could be formalized, so rejection is not warranted. However, it is genuinely load-bearing: the numerical regions and the universality claim are all computed from the Q-MAC conditions after assuming the bridge. Supplying the formal reduction (and the missing steps in Theorem 2's proof) is a reasonable condition for acceptance. Thus the reader's CONDITIONAL verdict stands unchanged.","tokens_in":11855,"tokens_out":13586,"duration_ms":162901,"concrete_test":"Analytical check: write the full Steane error-correction circuit for a CSS code with C1 = RM(r1,m), C2 = RM(r2,m), C1^perp subseteq C2, under a Pauli error with distribution (p_I,p_X,p_Y,p_Z). Compute the joint distribution of the two ancilla measurement outcomes and verify it equals a Q-MAC with inputs uniform over C1 and C2 and additive noise (Delta1,Delta2) having the same joint law. In particular, confirm the codeword parts are independent uniform and the noise is additive rather than syndrome-compressed. If the derivation cannot be completed, the quantum universality conclusion should be withdrawn or explicitly marked as conjectural.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section II.A and Section III.C assert that decoding Pauli errors on a CSS quantum RM code can be reduced to decoding a Q-MAC whose two users transmit codewords from C1 and C2 under correlated additive noise. The only justification is the sentence in Section III.C 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 is not a proof. A concrete gap is that the Q-MAC decoder observes the full received word Y = X + Delta, whereas quantum syndrome decoding observes only parity-check outcomes; the paper never shows that Steane's two ancilla measurements produce exactly the full word Y for two independent uniform codewords in C1 and C2, nor which classical code (C1, C2, or a dual) is used in each measurement. If the two ancilla measurements correspond to codes other than the two MAC codes, or if the codewords are not uniform and independent, the rate conditions of Theorem 2 do not transfer. Since all quantum claims (Figures 2 and 3, the 'universality' in the abstract) are derived from this bridge, the central claim is currently unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12017,"tokens_out":21725,"duration_ms":256921,"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":[{"comment":"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.","section":"§II.A, §III.C"},{"comment":"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.","section":"§III.B (Theorem 2 proof)"},{"comment":"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.","section":"§III.A (Theorem 1, condition 4)"}],"minor_comments":[{"comment":"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.","section":"§III.C and Fig. 2"},{"comment":"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.","section":"§II.A"},{"comment":"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.","section":"§III.A"}],"recommendation":"major_revision","confidential_remarks":"The paper is closely built on the authors' own FOCS paper [1], which is legitimate prior support. The classical MAC result and the explicit rate conditions are of independent interest, but the quantum universality claim depends on an unformalized bridge. I would encourage a revision rather than rejection, provided the authors add a formal statement and proof of the Steane-to-Q-MAC reduction and expand the proof of Theorem 2 to state the generalized bending and boosting lemmas. The figures and examples are useful and should be retained."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is Theorem 2's sufficient region for RM codes on two-user additive-noise MACs, and the observation that joint decoding buys a two-dimensional decodable region for a fixed CSS RM code. If the proof holds, that is a real extension of the BMS bending/boosting result, not just a re-labeling.\n\nThe paper deserves credit for a clean converse: Theorem 1's necessary conditions are natural, and the overlap argument for condition 4 is convincing. It is also honest about leaning on [1] for the heavy machinery, and the plots in Figures 2 and 3 make the successive-vs-joint comparison concrete.\n\nThe soft spots are real, though. Theorem 2 is a compressed sketch. The entropy bending and boosting lemmas are imported from [1] without showing they apply to vector-output symmetric MACs, and the step that justifies recovering one of X, X^(2), or their XOR is plausible but not fully written out. The min(R1,R2) condition in particular needs more detail. This alone would justify asking for a full proof.\n\nThe bigger problem is the quantum bridge. Section II.A asserts that decoding Pauli errors on a CSS RM code reduces to decoding a Q-MAC, and Section III.C repeats it in one sentence about Steane's method. The Q-MAC decoder sees the full received word Y; quantum syndrome decoding sees parity-check outcomes. The paper never proves that Steane's two ancilla measurements produce exactly the two uniform, independent codewords that Theorem 2 needs, nor which classical codes are involved. Without a formal statement of that reduction, the quantum universality claim--the headline result--is unsupported even if Theorem 2 is correct. The stress-test note lands.\n\nAlso, 'rate-optimal' should be read as 'achieves the hashing bound,' not as a proven quantum capacity result. The paper is mostly careful about this but could say it earlier.\n\nI would send this to a serious referee. The classical MAC result is plausible and worth nailing down, and the authors should be pushed to either prove the quantum reduction or state the quantum claim as conditional. As it stands, a reader should not cite the Pauli-channel universality, but the MAC part may well be right.","headline":"Plausible RM-MAC rate region, but the quantum universality claim leans on an asserted reduction that needs a real proof.","tokens_in":12623,"tokens_out":2512,"would_cite":false,"duration_ms":30074,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94A24","81P70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Reed-Muller codes can decode quantum Pauli noise over a whole region, not just single channels.","keywords":["Reed-Muller codes","quantum error correction","Pauli channels","multiple access channels","CSS codes","hashing bound","joint decoding","universality"],"falsifier":"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.","tokens_in":11582,"feed_emoji":"⚛️","tokens_out":2495,"duration_ms":30500,"temperature":0.7,"pith_summary":"This paper extends the theory of Reed-Muller (RM) codes from single-user binary symmetric channels to two-user multiple-access channels with correlated additive noise, called Q-MACs. It proves an achievable rate region for RM codes on Q-MACs, generalizing the bending and boosting arguments that previously established capacity for RM codes on symmetric channels. Applying this to quantum CSS codes built from RM codes, the paper shows that a single quantum RM code can reliably decode Pauli noise for a continuous range of channel parameters, not just one. This universality contrasts with successive decoding, which achieves the optimal rate only along one-dimensional curves.","feed_headline":"One quantum RM code decodes Pauli noise across a whole region","feed_subtitle":"Joint decoding lets Reed-Muller CSS codes hit the hashing bound for a range of channels, not just one.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the bending and boosting machinery that the paper generalizes to the two-user Q-MAC setting.","marker":"[1]"},{"why":"Establishes that RM codes achieve capacity on BMS channels, which underlies the reduction step where remaining codewords are decoded on effective binary channels.","marker":"[8]"},{"why":"Provides the Steane syndrome-extraction method that bridges Q-MAC decoding to quantum Pauli error correction.","marker":"[13]"},{"why":"Defines the hashing bound via coherent information, the benchmark that the quantum RM codes are claimed to achieve universally.","marker":"[14]"},{"why":"Introduces quantum Reed-Muller codes, the specific code family whose CSS structure is used here.","marker":"[15]"},{"why":"Another foundational construction of quantum RM codes, supporting the existence and features of CSS RM codes.","marker":"[16]"},{"why":"Shows how a Pauli channel maps to two correlated BMS channels, the classical model that becomes the Q-MAC.","marker":"[17]"}],"fun_headline_variants":["RM codes hit hashing bound for a whole Pauli noise region","Quantum RM codes achieve optimal rates across a channel region","One code, many Pauli channels: RM codes are universal","Reed-Muller codes decode Pauli noise across a whole region","Universal quantum RM codes cover multiple Pauli channels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["RM codes hit hashing bound for a whole Pauli noise region","Quantum RM codes achieve optimal rates across a channel region","One code, many Pauli channels: RM codes are universal","Reed-Muller codes decode Pauli noise across a whole region","Universal quantum RM codes cover multiple Pauli channels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000912,"raw_usage":{"total_tokens":3906,"prompt_tokens":924,"completion_tokens":2982,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":2899}},"tokens_in":540,"tokens_out":2982,"duration_ms":21825,"temperature":1.0,"reasoning_tokens":2899,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:08:03.953574+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A proof that Reed-Muller codes achieve shannon capacity on symmetric channels,","cited_arxiv_id":null,"evidence_quote":"Supplies the bending and boosting machinery that the paper generalizes to the two-user Q-MAC setting."},{"cited_title":"Reed-Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for All Rates Below Capacity","cited_arxiv_id":"2110.14631","evidence_quote":"Establishes that RM codes achieve capacity on BMS channels, which underlies the reduction step where remaining codewords are decoded on effective binary channels."},{"cited_title":"Quantum Reed-Muller Codes","cited_arxiv_id":"quant-ph/9608026","evidence_quote":"Introduces quantum Reed-Muller codes, the specific code family whose CSS structure is used here."},{"cited_title":"Quantum Reed-Muller Codes","cited_arxiv_id":"quant-ph/9703045","evidence_quote":"Another foundational construction of quantum RM codes, supporting the existence and features of CSS RM codes."},{"cited_title":"Quantum polar codes,","cited_arxiv_id":null,"evidence_quote":"Shows how a Pauli channel maps to two correlated BMS channels, the classical model that becomes the Q-MAC."}],"review_version":1}