{"id":"510cbca8-edd6-4282-8e9e-597acfca3070","arxiv_id":"1909.02479","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Shared entanglement between senders strictly boosts the capacity of certain classical multiple-access channels, and deciding their capacity regions is NP-hard or undecidable.","lead":"This paper builds communication channels from two-player puzzles and proves that shared quantum entanglement between two senders can enlarge the capacity of a purely classical channel. It also shows that computing or deciding these capacities is NP-hard, and deciding the finite-dimensional entanglement version is undecidable.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 3 is applied to d-dimensional entanglement-assisted coding strategies without proving the induced question-answer correlation obeys the d-dimensional game bound; this gap underlies the unbounded-entanglement and undecidability converses.","rationale":"The reader's weakest_assumption correctly identifies the unproven extension of Proposition 3 to quantum strategies as the main gap. My review sharpens this: the problem is not just replacing the classical omega_U by a quantum one, but ensuring that arbitrary post-processed coding strategies induce valid d-dimensional game correlations. If a coding strategy can produce a signaling conditional distribution on (x_1,y_1,x_2,y_2), the Slofstra-Vidick dimension bound does not directly apply, and the converses of Propositions 5 and 8 could fail. This is the single most load-bearing concern because the paper's headline claims of unbounded entanglement requirements and undecidability both rely on those converses. The concern is likely fixable by stating and proving a generalized proposition for quantum strategy sets with a uniform dimension-dependent losing-probability bound, which the paper currently omits. The magic-square separation uses Proposition 3 only in the classical regime, so it stands even if the quantum extension fails; the NP-hardness result similarly uses only classical strategies. The constructive achievability results (Propositions 6 and Corollary 7) and the explicit numerical bounds provide independent support for the paper's main intuition and are not affected by this gap. For these reasons I do not move the reader's verdict: the paper should remain conditional pending a rigorous generalized Proposition 3 and a proof that induced coding correlations inherit the relevant dimension bound.","tokens_in":21328,"tokens_out":33279,"duration_ms":357588,"concrete_test":"Prove or disprove the following generalized lemma: for every d-dimensional EA coding strategy E (POVMs plus post-processing, as in Appendix A.3) and every product input distribution p_A1 p_B1, define the induced conditional distribution p(y_1,y_2|x_1,x_2) and its uniform-questions losing probability q_L(E); show q_L(E) >= eta_d, where eta_d is the infimum losing probability over d-dimensional quantum strategies for the game. A direct computational check for the CHSH-based MAC: optimize over all two-qubit strategies with post-processing the single-use sum rate I(A_1 B_1;Z) for N_CHSH and compare with the bound obtained by plugging the CHSH quantum winning probability cos^2(pi/8) into Eq. (22) with eta = 1 - cos^2(pi/8); if the optimized rate exceeds that bound, the unproven transfer fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the unproven transfer of Proposition 3 (Appendix B) from classical probabilistic game strategies to arbitrary d-dimensional entanglement-assisted coding strategies for the MAC N_G. Proposition 3's proof uses the data-processing inequality to compare the losing probability p_L under the coding distribution with q_L, the losing probability of the same strategy under uniform questions, and then lower-bounds q_L by 1-omega_U(G), the classical maximum winning probability. For quantum strategies, the correct lower bound would have to be 1-omega_U^q_d(G), the maximum over d-dimensional quantum game strategies. Appendix D.1 (Prop. 5) and Prop. 8 replace this with the Slofstra-Vidick bound 1-omega_U(G_SV) >= C_1/d^6, but they never prove that an arbitrary coding strategy E (per Appendix A.3) induces a conditional distribution p(y_1,y_2|x_1,x_2) that is itself a d-dimensional game strategy, or even that its uniform-questions losing probability satisfies q_L >= C_1/d^6. Because x_1,x_2 are outputs of the post-processed measurement rather than external questions, conditioning on them can produce signaling correlations that are not constrained by the non-local game's dimension bound. If this generalized statement fails, the converses in Proposition 5 and Proposition 8 (and hence the unbounded-entanglement and undecidability headline claims) are unsupported; the magic-square separation and the NP-hardness result are unaffected because they concern classical strategies only.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper constructs, for any two-player non-local game G, a classical two-sender multiple access channel N_G whose output is the question pair when the players win the game and a uniformly random question pair when they lose. The central identity (Proposition 2) expresses the sum-rate mutual information as H(Z) − p_L log(|X_1||X_2|), tying the channel noise directly to the game losing probability. Proposition 3 converts this identity into a quantitative gap for games with no perfect classical strategy. Using this tool, the authors claim four results: (i) the magic-square game gives a classical MAC whose unassisted sum rate is strictly below 2 log 3 while an entanglement-assisted strategy achieves 2 log 3; (ii) a linear-system game of Slofstra and Vidick yields MACs whose d-dimensional entanglement-assisted single-letter rate region approaches the perfect rate pair only in the limit d→infty; (iii) via Slofstra's undecidability theorem, deciding whether the perfect rate pair lies in the finite-dimensional entanglement-assisted single-letter region is undecidable; and (iv) via the PCP theorem, deciding whether the unassisted capacity region contains a point is NP-hard to inverse-cubic precision.","tokens_in":21602,"tokens_out":34602,"duration_ms":331459,"significance":"The game-to-MAC construction is elegant and connects non-local games to network information theory in a way that yields surprising consequences: entanglement assistance for a classical MAC, unbounded entanglement requirements, undecidability, and NP-hardness for a channel family covered by a single-letter capacity formula. The identity in Proposition 2 is clean, the numerical work for the magic square is reproducible from the supplied code, and the provenance of the construction is transparently credited to Quek-Shor and Nötzel-Winter. The classical applications (magic-square separation and NP-hardness) are already interesting. However, the quantum converse claims rest on an unproven extension of Proposition 3 to entanglement-assisted coding strategies, and the proof of Proposition 3 itself contains an unjustified entropic step. If the authors repair these points, the paper would be a strong contribution; as it stands, the formal support for the unbounded-entanglement and undecidability statements is incomplete.","major_comments":[{"comment":"Proposition 3 is stated and proved only for classical probabilistic strategies, but Propositions 5 and 8 apply it to arbitrary d-dimensional entanglement-assisted coding strategies of the form in Appendix A.3. The proof of Proposition 3 relies on the bound q_L ≥ 1 − ω_U(G) for the losing probability of the same strategy under uniformly drawn questions; for a coding strategy E the paper never proves that the induced conditional distribution p(y1,y2|x1,x2) is a d-dimensional quantum game strategy, nor that its uniform-question losing probability satisfies q_L ≥ 1 − ω_U^q_d(G). Because x1 and x2 are outputs of the post-processed measurement rather than external questions, the conditional distribution can in principle depend on the message pair, so the Slofstra–Vidick bound (50), which applies to game strategies, does not by itself constrain coding strategies. Without a proof of the quantum generalization of Proposition 3, the converse directions of Propositions 5 and 8 (and hence the unbounded-entanglement and undecidability headline claims) are unsupported. The magic-square separation and the NP-hardness result are classical and are not affected.","section":"Appendix D.1 / D.3 (Propositions 5 and 8)"},{"comment":"The expansion of H(ZW) in Eq. (29) replaces H(X1X2|W=1) with H(X1X2). The inequality (1−pL)H(X1X2|W=1) ≥ (1−pL)H(X1X2) is not valid in general; conditioning on the win/loss event can either increase or decrease the entropy of the question variables, depending on how the question distribution is tilted toward winning or losing question pairs. This step is what produces the divergence bound D(πX1πX2‖πU) ≤ γ in Eq. (31), on which the data-processing argument for the gap in Eq. (22) depends. The proof should be repaired, for instance by bounding I(X1X2;W) ≤ h(pL) and absorbing the additional terms, and the statement of Proposition 3 should be checked against the repaired proof.","section":"Appendix B, proof of Proposition 3, Eq. (29)"}],"minor_comments":[{"comment":"The channel definition (38) has codomain R×S and uses the factor δ_s\\hat{s}, but the output of N_G must be the question pair (r,c), so the codomain should be R×C and the delta should be δ_c\\hat{c}. The subsequent entropy calculation log 9 and the comparison with 2 log 3 assume the output is the question pair, so this is a typographical error in the displayed channel definition.","section":"Appendix C.3, Eq. (38)"},{"comment":"In the definition of the second sender's measurements, 'for b1∈A1' should read 'for b1∈B1'; the same alphabet misassignment appears in a later sentence describing the post-processing f2.","section":"Appendix A.3"},{"comment":"In the line 'the trivial bound H(X2|W = 1)≤ log|X2| = n', the right-hand side should be log n, not n; otherwise the dimension and the logarithm are conflated.","section":"Appendix D.2, proof of Proposition 6"},{"comment":"The statement says the sum rate capacity is bounded away from the perfect value 'by Θ(1/d^13)'. The proof gives only an upper bound on the sum capacity, i.e., the gap is Ω(1/d^13). The achievable strategy in Proposition 6 has gap O(1/d^2), so the gap is not established to be Θ(1/d^13); the notation should be Ω(1/d^13) or 'at least', unless a matching upper bound on the gap is supplied.","section":"Proposition 5"},{"comment":"The symbol δ is overloaded: it is the additive parameter in Eq. (22) and also the binary relative entropy function δ(·‖·) in Eq. (23) and Eq. (32). Using a different symbol for the divergence, e.g., D_2, would remove ambiguity.","section":"Proposition 3, Eq. (23)"},{"comment":"The introduction describes the gap as (1−ω*)^3 with ω*=1−(1−c)/n, which is Θ((1−c)^3/n^3), while Proposition 10 takes δ=(1−c)/n^3. These are asymptotically compatible but the constants differ; the two displays should be harmonized.","section":"Section 2.3 and Proposition 10"}],"recommendation":"major_revision","confidential_remarks":"I believe the results are likely correct after repair, but the missing quantum version of Proposition 3 is central to the unbounded-entanglement and undecidability claims, and the proof of Proposition 3 itself has a fixable but real gap. I would not accept the paper until Proposition 3 is either proved for the entanglement-assisted strategies used in Appendices D.1 and D.3 or the statements there are restricted accordingly. The magic-square separation and the NP-hardness result, which use only the classical version, are not affected by this concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere is my read on Leditzky et al. The new content that matters: they apply the non-local game construction of MACs (credited to Quek–Shor and Nötzel–Winter) to prove that shared entanglement between senders strictly increases the capacity region of a classical MAC, that unbounded entanglement may be needed to approach the ideal rate, that membership in the finite-dimensional entanglement-assisted rate region is undecidable, and that approximating the unassisted capacity region is NP-hard. The magic-square separation and the PCP-based NP-hardness result are the most robust, since they rely only on classical strategies. The construction is clean, the paper credits prior work honestly, and the point about single-letter formulas not implying computational tractability is well made.\n\nThe soft spot is exactly what the stress-test flagged. Proposition 3 is proved for classical probabilistic strategies, but Appendix D.1 (Proposition 5) and the converse direction of Proposition 8 apply it to d-dimensional entanglement-assisted coding strategies without proving the needed generalization. The induced question-answer correlation after post-processing need not itself be a d-dimensional game strategy, so the uniform-questions losing probability could behave differently than the classical bound assumes. If that generalized statement fails, the unbounded-entanglement and undecidability converses lose support. The classical results are not affected. This looks like a repairable gap rather than a fatal flaw: one likely needs a quantum version of Proposition 3, proven by a similar data-processing argument with the appropriate d-dimensional quantum winning probability. But it must be addressed before those headline claims are accepted.\n\nThe citation pattern is fair and the mathematics in the parts I checked is sound. The numerical optimization in Appendix C is clearly labeled as a heuristic lower bound, not a proof. I saw no circularity.\n\nWho should read this? Network information theorists and quantum information researchers interested in entanglement assistance and the complexity of capacity regions. It deserves a serious referee. My recommendation: send it to peer review, but make sure the referee requires a generalized Proposition 3 before the unbounded-entanglement and undecidability claims are taken as established. I would cite the paper, mainly for the game-MAC construction and the classical NP-hardness result.","headline":"A mostly solid and important paper that shows entanglement can strictly boost classical MAC capacity and that capacity regions are computationally hard; the main caveat is an unproven generalization of Proposition 3 to quantum strategies that is load-bearing for the unbounded-entanglement and undecidability claims.","tokens_in":22147,"tokens_out":1898,"would_cite":true,"duration_ms":20461,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","81P68","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Entanglement shared by two senders can strictly increase the capacity region of a classical multiple access channel, and deciding this capacity can be NP-hard or even undecidable.","keywords":["multiple access channel","non-local games","entanglement assistance","capacity region","magic square game","linear system games","undecidability","NP-hardness"],"falsifier":"Pick a non-local game $G$ with $\\omega_U(G)<1$ and small alphabet sizes, then exhaustively optimize over all product input distributions and all strategies to compute the exact sum capacity of $N_G$; if it equals $\\log|X_1|+\\log|X_2|$ for any such game, Theorem 1 is false. For the unbounded-entanglement claim, exhibit a finite-$d$ quantum strategy for the particular linear system game used in the paper whose losing probability is exactly zero; then the claimed $\\Omega(1/d^{13})$ gap would be contradicted.","tokens_in":2045,"feed_emoji":"📡","tokens_out":3074,"duration_ms":130619,"temperature":0.7,"pith_summary":"This paper proves that a two-sender classical multiple access channel can be built from any two-player non-local game so that the channel's noise is exactly the players' losing probability. The central theorem states that whenever the game cannot be won with certainty using the resources available to the senders, the achievable sum rate is strictly below the maximum $\\log|X_1|+\\log|X_2|$. That single gap mechanism yields four concrete consequences: entanglement shared between senders strictly increases the capacity of some classical MACs; some MACs with bounded input alphabets require unbounded entanglement to approach their ideal rates; checking whether the ideal rate pair is achievable with finite-dimensional entanglement is undecidable; and checking membership in the unassisted capacity region to inverse-cubic precision is NP-hard. This refutes the assumption that the computable single-letter formula for MAC capacity makes the problem easy.","feed_headline":"Entanglement boosts two-sender channel rates past classical limits","feed_subtitle":"Game-to-channel construction separates classical and entanglement-assisted rates; capacity checks become NP-hard.","key_machinery":"The load-bearing construction is the game-to-MAC encoding (2): the input alphabets are question-answer pairs $(X_1\\times Y_1)$ and $(X_2\\times Y_2)$, the output alphabet is $X_1\\times X_2$, and on a winning tuple the channel outputs the question pair $(x_1,x_2)$ deterministically while on a losing tuple it outputs a uniformly random pair. The identity (3), $I(X_1Y_1X_2Y_2;Z)=H(Z)-p_L(\\log|X_1|+\\log|X_2|)$, reduces the sum-rate bound from the classical single-letter MAC capacity formula to a statement about the losing probability $p_L$. Proposition 3 converts the condition $\\omega_U(G)<1$ into a quantitative entropy bound, giving Theorem 1. All four main results are corollaries of that single separation mechanism.","core_discovery":"The paper's central claim is that a two-sender classical MAC $N_G$ can be defined from any non-local game $G$ so that the channel is noiseless exactly when Alice and Bob win the game and maximally noisy otherwise. The decisive result (Theorem 1) is that whenever $G$ has no perfect strategy using the same resources available to the communication strategy, the sum rate $R_1+R_2$ is strictly smaller than $\\log|X_1|+\\log|X_2|$. The same gap then yields four results: the magic square game gives a classical MAC whose entanglement-assisted rate region contains a point $(\\log 3,\\log 3)$ that is provably outside the unassisted capacity region; a particular linear system game gives a MAC whose $d$-dimensional entanglement-assisted rate regions are bounded away from the ideal point for every finite $d$ but approach it as $d\\to\\infty$; deciding whether the ideal rate pair belongs to the finite-dimensional entanglement-assisted region is undecidable; and deciding whether an arbitrary rate point lies in the unassisted capacity region, to inverse-cubic precision, is NP-hard.","pith_inferences":["The same construction would likely turn any Bell-type inequality violation into a communication-rate separation: any game whose classical and quantum winning probabilities differ should produce a MAC whose entanglement-assisted and unassisted regions differ, so quantitative gaps such as CHSH could yield an explicit family of small separations.","The unbounded-entanglement phenomenon suggests a resource-theoretic reading: if entanglement is priced per dimension, the optimal rate-cost tradeoff for these MACs has no finite optimum, and one can only approach the ideal rate asymptotically.","The NP-hardness proof targets the unassisted capacity region; a parallel hardness result for the entanglement-assisted region or for quantum MACs would complete the picture across the two settings.","The numerical gap between the proven upper bound ($3.13694$) and the computed lower bound ($2.84195$) for the magic square channel suggests that the true classical-quantum separation is larger than the theorem guarantees, so a direct proof of a tighter bound would be a natural test of the mechanism."],"forward_implications":["Any pseudo-telepathy game (no perfect classical strategy, but a perfect quantum one) yields a classical MAC whose entanglement-assisted rate region strictly contains its unassisted capacity region; the magic square example separates $3.13694$ from $2\\log 3\\approx 3.17$.","There are MACs for which, for every fixed entanglement dimension $d$, the sum rate is bounded away from $\\log m+\\log n$ by $\\Omega(1/d^{13})$, yet the achievable region approaches that point as $d\\to\\infty$, so bounded input alphabets can demand unbounded entanglement.","Deciding whether the ideal rate pair $(\\log m,\\log n)$ lies in the finite-dimensional entanglement-assisted achievable region is undecidable for MACs built from linear system games.","Deciding whether a rate pair belongs to the unassisted capacity region of a classical MAC, to additive error $\\Theta(1/n^3)$, is NP-hard; hence the single-letter formula does not provide an efficient algorithm.","Unless $\\mathrm{P}=\\mathrm{NP}$, there is no polynomial-time algorithm for computing the boundary of the capacity region of a general discrete MAC; under the exponential-time hypothesis, no subexponential algorithm exists either."],"supporting_citations":[{"why":"supplies the classical single-letter capacity-region formula for multiple access channels, the foundation for the sum-rate identity used in Theorem 1.","marker":"[2]"},{"why":"independently supplies the same single-letter formula, which the paper's capacity bounds are extracted from.","marker":"[3]"},{"why":"gives the magic square game's optimal classical winning probability and a perfect quantum strategy, establishing the entanglement-assistance separation.","marker":"[14]"},{"why":"provides a linear system game whose near-perfect quantum strategies require arbitrarily large dimension, yielding the unbounded-entanglement example and the approximating strategies.","marker":"[16]"},{"why":"proves undecidability of the existence of perfect finite-dimensional quantum strategies for linear system games, which transfers to the rate-region membership problem.","marker":"[17]"},{"why":"provides a non-local game version of 3SAT with a constant gap between perfect and near-perfect winning probabilities, the input to the NP-hardness reduction.","marker":"[18]"},{"why":"supplies the PCP theorem that makes deciding between perfect and badly failing 3SAT games NP-hard.","marker":"[19, 20]"}],"fun_headline_variants":["Entanglement lifts multiple access channel rates","Quantum link boosts two-sender capacity","MAC capacity: entanglement wins, then breaks complexity","Bounded inputs need unbounded entanglement on MACs","Finite entanglement fails; capacity check is NP-hard"],"cache_read_input_tokens":24192,"weakest_assumption_plain":"The upper-bound proofs take a bound proved for classical probabilistic strategies and apply it to arbitrary $d$-dimensional quantum entanglement-assisted coding strategies, replacing the classical maximal winning probability by the quantum one; if that generalized bound fails, the unbounded-entanglement and undecidability claims lose their converse direction.","fun_headline_variants_meta":{"raw":{"variants":["Entanglement lifts multiple access channel rates","Quantum link boosts two-sender capacity","MAC capacity: entanglement wins, then breaks complexity","Bounded inputs need unbounded entanglement on MACs","Finite entanglement fails; capacity check is NP-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000198,"raw_usage":{"total_tokens":1353,"prompt_tokens":913,"completion_tokens":440,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":529,"completion_tokens_details":{"reasoning_tokens":371}},"tokens_in":529,"tokens_out":440,"duration_ms":5241,"temperature":1.0,"reasoning_tokens":371,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:52:28.311010+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Pick a non-local game $G$ with $\\omega_U(G)<1$ and small alphabet sizes, then exhaustively optimize over all product input distributions and all strategies to compute the exact sum capacity of $N_G$; if it equals $\\log|X_1|+\\log|X_2|$ for any such game, Theorem 1 is false. For the unbounded-entanglement claim, exhibit a finite-$d$ quantum strategy for the particular linear system game used in the paper whose losing probability is exactly zero; then the claimed $\\Omega(1/d^{13})$ gap would be contradicted.","supporting_citations":[{"cited_title":"Multi-way communication channels","cited_arxiv_id":null,"evidence_quote":"supplies the classical single-letter capacity-region formula for multiple access channels, the foundation for the sum-rate identity used in Theorem 1."},{"cited_title":"Multiple access channels PhD thesis (Department of Electrical Engineering, University of Hawaii, 1972)","cited_arxiv_id":null,"evidence_quote":"independently supplies the same single-letter formula, which the paper's capacity bounds are extracted from."},{"cited_title":"& Tapp, A","cited_arxiv_id":null,"evidence_quote":"gives the magic square game's optimal classical winning probability and a perfect quantum strategy, establishing the entanglement-assistance separation."},{"cited_title":"& Vidick, T","cited_arxiv_id":null,"evidence_quote":"provides a linear system game whose near-perfect quantum strategies require arbitrarily large dimension, yielding the unbounded-entanglement example and the approximating strategies."},{"cited_title":"The set of quantum correlations is not closed","cited_arxiv_id":null,"evidence_quote":"proves undecidability of the existence of perfect finite-dimensional quantum strategies for linear system games, which transfers to the rate-region membership problem."},{"cited_title":"Some Optimal Inapproximability Results","cited_arxiv_id":null,"evidence_quote":"provides a non-local game version of 3SAT with a constant gap between perfect and near-perfect winning probabilities, the input to the NP-hardness reduction."}],"review_version":1}