{"id":"c8203a23-4df0-4204-9f72-c999ecc06480","arxiv_id":"2608.05092","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every perfect binary-output communication game reduces to graph coloring and orthogonal representation problems, and perfect qubit strategies never beat a classical bit.","lead":"This paper proves that every binary-output prepare-and-measure communication game is exactly equivalent to a graph coloring or orthogonal representation problem, and that every perfect qubit game can be perfectly simulated with a single classical bit. The result gives explicit minimal examples where a three-level quantum message beats a three-level classical one, connecting communication complexity, graph theory, and contextuality.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Structural theorems appear correct; the flagship G13 minimality claims rest on finite exhaustive searches that are asserted but not yet publicly reproducible.","rationale":"I checked the proofs of Theorem 3, Theorem 6, Proposition 5, the apex calculations, and the Torpedo and antidistinguishability bounds; they are internally consistent. The reader's weakest assumption correctly identifies the finite enumerations around G13 as the main unverified element. Because those enumerations support only the flagship minimality claims and not the structural theorems, the appropriate verdict remains CONDITIONAL pending an independent rerun or a deposited, machine-checked script. No mathematical error in the central reduction was found.","tokens_in":16903,"tokens_out":20922,"duration_ms":241959,"concrete_test":"Run an independent exact backtracking/SAT check on the edge list in Eq. (A1): compute chi(G13), alpha(G13), bc(G13), and chi(H_T) for all 8192 tested sets T. Accept the paper's numerical claims only if chi=4, alpha=5, bc=8, min{|T|:chi(H_T)>3}=8, and the only size-8 minimizers are the three sets listed in Eq. (51). Any discrepancy would require correcting the minimality statements in Section V.C.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The two structural theorems and the analytic Torpedo/SIC bounds are well supported by the proofs given. The load-bearing soft spot is the finite-data layer around G13. The paper's own Data and Code Availability section promises a standalone verification script only 'no later than publication,' so the exhaustive searches behind bc(G13)=8 and behind the minimum-tested-set enumeration are currently asserted rather than independently checkable. Section V.C and Appendix A supply a 4-coloring (A4), explicit 3-colorings of all one-vertex deletions (Table II), and the edge list (A1), but they do not supply a no-3-coloring certificate for G13, a witness that alpha(G13)<=5, or a certificate that the three listed size-8 tested sets are the only minimizers. The C3=39 and Q3=40 values do not depend on these searches: they follow from chi(G13)=4, T8 being a vertex cover, and the near-coloring (41), together with the explicit orthogonal representation. What would fail if an enumeration error existed is the headline 'eight Bob inputs are minimal' (Proposition 5 plus bc(G13)=8) and the exact minimizer classification. If, for instance, G13 actually had an independent set of size 6, then tau(G13)=7 and bc(G13)<=7, invalidating Y=8 minimality while leaving the structural theorems intact.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies finite prepare-and-measure games in which the only constraints are forbidden outputs (support games). It proves a complete structural characterization for binary outputs: perfect classical d-level realization is equivalent to d-colorability of a canonically defined conflict graph, perfect d-dimensional quantum realization is equivalent to a d-dimensional orthogonal representation, and the minimum number of Bob inputs over all binary-output realizations of a fixed conflict graph equals its edge biclique-cover number (Theorem 3 and Proposition 5). It further proves that every perfect qubit strategy with an arbitrary finite output alphabet admits a perfect deterministic classical-bit realization (Theorem 6). The remainder constructs explicit examples: the 13-ray Yu-Oh graph gives (X,Y,B)=(13,8,2) with C3=39<Q3=S=40 and eight Bob inputs claimed minimal; apex joins give similar separations in every dimension; the qutrit Torpedo relation yields exact classical loss bounds and a seven-preparation minimal separation; and a SIC-based antidistinguishability game gives a closed-form classical bound. Robustness thresholds under depolarizing noise, preparation noise, and detection inefficiency are also derived.","tokens_in":17123,"tokens_out":33928,"duration_ms":419029,"significance":"Assuming correctness, the two structural theorems are valuable and cleanly proven. Theorem 3 elevates the known graph-construction principle for exact communication to a complete classification of arbitrary binary-output support games, and Proposition 5 gives an exact operational compression in terms of edge biclique covers. Theorem 6 is a sharp and somewhat surprising separation between exact support constraints and full-statistics simulation: the classical cost of reproducing arbitrary qubit statistics is four messages, yet every perfectly realizable qubit support relation needs only two. The explicit G13 compressed game is a compact witness (13 preparations, 8 inputs, 2 outputs) of a perfect qutrit-over-trit separation. I checked the key steps of Theorems 3, 6, and 12 and of Propositions 5, 13, and 16, including the support-to-eigenspace argument, the Bloch-hemisphere argument, the affine-plane triple lemma, and the convex balancing in Appendix C; they are sound. The paper is parameter-free and does not fit data. The main caveat is the reproducibility of the finite enumerations supporting the G13 minimality claims.","major_comments":[{"comment":"The exact claims bc(G13)=8 and the classification of minimum tested sets rest on exhaustive searches that are asserted but not accompanied by code or by certificates for the negative statements. The 5-set {1,10,11,12,13} and the 4-coloring (A4) are certificates for α(G13)≥5 and χ(G13)≤4, but the manuscript gives no certificate for α(G13)≤5, no certificate for χ(G13)>3, and no certificate that Eq. (51) is exhaustive. These statements are load-bearing for the headline value Y=8 via Eq. (48) and Proposition 5, and for the minimizer classification; an enumeration error would change those claims but not the structural Theorems 3 and 6 or the values C3=39 and Q3=40, which depend only on χ(G13)=4, the vertex-cover property of T8, and the explicit orthogonal representation. The Data and Code Availability section promises a verification script only 'no later than publication,' so the exhaustive layer is not independently checkable in the submitted manuscript. Please make the script available with the revision or add human-verifiable certificates for all negative/exhaustive claims.","section":"§V.C, Eqs. (44)–(51); Appendix A"}],"minor_comments":[{"comment":"There are typographical and spacing issues in mathematical expressions, for example 'classicald-levelmessage' in the abstract and 'x∼ ΓG x′ ⇐ ⇒' in Eq. (9); please proofread the LaTeX.","section":"Abstract and Eq. (9)"},{"comment":"Theorem 12 says perfect classical winning on seven Torpedo preparations requires four message values, while Corollary 15 calls seven preparations minimal for a qutrit-over-trit separation; the wording is correct, but a clarifying sentence that the separation is specifically against a trit (three message values) would prevent confusion.","section":"§VII, Theorem 12 and Corollary 15"},{"comment":"The no-4-cycle check for G13 is stated as 'direct verification'; since this fact is used to identify bicliques with stars, adding a one-line certificate (for example, that no pair of vertices has two common neighbors) would make the claim easier to verify.","section":"Appendix A, item 1"},{"comment":"The statement that all finite combinatorial data needed to reproduce the results are contained in the article is not fully accurate for the negative exhaustive statements, as noted in the major comment; the availability statement should be updated to reflect what is actually provided in the revision.","section":"Data and Code Availability"}],"recommendation":"major_revision","confidential_remarks":"The structural contributions are solid and the paper is a good fit for quant-ph. The only blocking issue is the reproducibility of the finite enumerations behind the G13 minimality claims; this is easily fixable by supplying the verification script or certificates. If the enumerations are confirmed, I would be happy to accept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick read: the structural results are the real contribution and they look correct; the numerical minimality claims around G13 are plausible but not yet independently checkable.\n\nThe main new content is Theorem 3, the complete reduction of arbitrary binary-output prepare-and-measure support games to conflict graphs, with classical perfection equivalent to d-colorability and quantum perfection to a d-dimensional orthogonal representation. Proposition 5, identifying the minimal number of Bob inputs with the edge biclique-cover number, is also new and sharp. Theorem 6, the arbitrary-output qubit impossibility, cleanly separates support constraints from full-statistics simulation. These are genuine advances over the graph-defined special case in Refs [5,6,7].\n\nThe proofs of Theorems 3, 6, 12 and Propositions 5, 13, 16 appear solid. I checked the key steps: the support-to-eigenspace argument, the Bloch-sphere hemisphere argument, the affine-plane triple lemma, and the convex balancing in Appendix C. The Torpedo message-cost formula and the SIC classical bound are analytic, parameter-free, and the small finite-field cases are cross-checked by enumeration in Appendix A. The G13 edge list, the explicit 4-coloring, and the one-vertex-deletion 3-coloring certificates are included in the article, and those do give the reader real material to verify the graph-theoretic core.\n\nThe soft spot is the finite-data layer around G13. The claims that bc(G13)=8, that the minimum tested-set size is 8, and that there are exactly three minimizers all depend on exhaustive backtracking enumerations that are asserted but not backed by public code. The edge list and several certificates are there, but there is no no-3-coloring certificate for G13, no independent-set certificate for alpha(G13)<=5, and no certificate for minimizer uniqueness. The paper's own data/code statement promises a standalone verification script only 'no later than publication.' An undetected error in those searches would invalidate the specific values Y=8 and C3=39/Q3=40 as stated, while leaving Theorems 3 and 6 intact. This is a real but bounded weakness, not a load-bearing flaw in the central argument.\n\nThe noise-threshold calculations in Section V.C are honestly labeled as canonical-strategy thresholds, not globally optimized, so I do not hold that against the paper. Citation patterns look fair; the graph-defined special case is attributed properly and the new contribution is stated as the universal reduction.\n\nWho is this for? Anyone working on exact communication complexity, zero-error information theory, or dimension witnesses in prepare-and-measure scenarios. The structural theorems deserve a serious referee. My recommendation: accept for review, and require the code deposit as a condition of publication. The paper will be stronger if every enumerated claim is machine-checkable by the reader.","headline":"Structural theorems are the real contribution and look correct; the flagship G13 minimality numbers rest on enumerations that need public code before I'd call them independently verified.","tokens_in":17675,"tokens_out":1435,"would_cite":true,"duration_ms":18700,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C70","81P45"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every binary-output perfect prepare-and-measure game reduces to a conflict graph: perfect classical play is $d$-colorability, perfect quantum play is a $d$-dimensional orthogonal representation.","keywords":["prepare-and-measure games","perfect games","quantum communication advantage","conflict graph","graph coloring","orthogonal representation","edge biclique cover","qutrit"],"falsifier":"Run an independent exact 3-colorability check on $G_{13}$ and its 13 one-vertex deletions: a 3-coloring of $G_{13}$ would refute $\\chi(G_{13})=4$, and a tested set of seven vertices whose incident-edge subgraph is not 3-colorable would refute the claimed eight-vertex minimum; likewise, an edge biclique cover of $G_{13}$ using seven bicliques, or a binary-output support game realizing $G_{13}$ with seven Bob inputs, would refute $\\mathrm{bc}(G_{13})=8$.","tokens_in":16660,"feed_emoji":"🎲","tokens_out":12115,"duration_ms":126684,"temperature":0.7,"pith_summary":"Perfect prepare-and-measure games are tasks in which a $d$-dimensional quantum message satisfies every prescribed winning constraint while no classical $d$-level message can. This paper proves that, for tasks with a binary output alphabet, such games are exactly conflict-graph problems: a perfect classical $d$-level strategy exists precisely when the conflict graph is $d$-colorable, and a perfect $d$-dimensional quantum strategy exists precisely when the graph admits a $d$-dimensional orthogonal representation. The same theorem identifies the minimum number of Bob inputs needed to realize a fixed conflict graph as its edge biclique-cover number. The paper also proves that for any finite output alphabet, every perfectly realizable qubit support relation can be implemented perfectly with one classical bit, so a perfect qubit advantage over a classical bit is impossible. These results turn exact communication advantages into checkable graph parameters and yield an explicit qutrit game with 13 preparations, 8 Bob inputs, and binary output whose classical score is 39 and perfect quantum score is 40.","feed_headline":"Binary perfect games collapse to graph coloring","feed_subtitle":"Perfect classical play is d-colorability; perfect quantum play is an orthogonal representation of the same graph.","key_machinery":"The central object is the conflict graph $\\Gamma_G$ of a binary-output support game, whose vertices are preparations and whose edges join pairs that some Bob input can force to opposite outputs. The binary theory is carried by two graph parameters: the chromatic number $\\chi(\\Gamma_G)$, which decides perfect classical $d$-level messages through the intersection criterion of Proposition 1, and the complex orthogonal rank $\\xi_{\\mathbb{C}}(\\Gamma_G)$, the smallest dimension admitting nonzero vectors that are orthogonal on adjacent vertices, which decides perfect quantum strategies through projectors onto the span of same-output preparations. For input compression the load-bearing quantity is the edge biclique-cover number $\\mathrm{bc}(G)$, which Proposition 5 equates with the minimum number of Bob inputs realizing a fixed conflict graph. For the arbitrary-output qubit impossibility, the mechanism is a Bloch-sphere hemisphere argument: a generic direction separates the finite set of pure preparation Bloch vectors into two open hemispheres, and if one classical bit class failed to have a common winning output, the identity $\\sum_b M_{b|y}=I$ would force a positive linear combination of vectors from a single open hemisphere to vanish.","core_discovery":"The paper's central structural claim is Theorem 3: for any binary-output support game $G$ with conflict graph $\\Gamma_G$, perfect classical realization with a $d$-level message is equivalent to $\\chi(\\Gamma_G)\\le d$, perfect $d$-dimensional quantum realization is equivalent to $\\xi_{\\mathbb{C}}(\\Gamma_G)\\le d$, and the minimum number of Bob inputs among all binary-output realizations of $\\Gamma_G$ is its edge biclique-cover number $\\mathrm{bc}(\\Gamma_G)$. A same-dimension perfect separation therefore exists exactly when $\\xi_{\\mathbb{C}}(\\Gamma_G)\\le d<\\chi(\\Gamma_G)$. The second main claim, Theorem 6, is that for every finite support game $G$ with any finite output alphabet, $Q_2(G)=S_G$ implies $C_2(G)=S_G$: a perfect qubit strategy always admits a perfect deterministic classical-bit strategy. The manuscript instantiates the binary mechanism on the 13-ray qutrit graph $G_{13}$, obtaining $(X,Y,B)=(13,8,2)$ with $C_3=39<Q_3=S=40$, proves $Y=8$ is minimal via $\\mathrm{bc}(G_{13})=8$, and extends the construction to all dimensions by apex joins. The Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime, with exact classical values $C_3=33$ and $C_3^{\\mathrm{AD}}=249$ against perfect qutrit values $36$ and $252$.","pith_inferences":["Beyond the paper, the $(13,8,2)$ inequality $I^{\\mathrm{comp}}_{13}\\le 39$ is directly testable: under the perfect-support promise, any observed violation would certify a qutrit message, turning the graph-theoretic equivalence into a dimension witness.","Beyond the paper, because orthogonal rank never exceeds chromatic number, searching for the smallest graph whose orthogonal rank is strictly below its chromatic number is a concrete combinatorial optimization problem that could yield more compact perfect games than $G_{13}$; the paper does not claim $G_{13}$ is minimal in order.","Beyond the paper, the qubit hemisphere proof suggests asking whether every perfectly realizable $d$-dimensional support relation admits a perfect classical $d$-message realization for $d>2$; this is not established in the paper and would delineate how far the support-versus-statistics distinction extends."],"forward_implications":["For any binary-output support game, deciding whether a perfect $d$-level classical or $d$-dimensional quantum strategy exists is exactly deciding whether the conflict graph is $d$-colorable or admits a $d$-dimensional orthogonal representation.","The minimum number of Bob inputs realizing a fixed conflict graph is exactly its edge biclique-cover number, so no binary-output realization of the $G_{13}$ conflict graph can use fewer than eight inputs, and the compressed $(13,8,2)$ game attains that bound.","No perfect qubit protocol over any finite output alphabet can beat a single classical bit: every perfectly realizable qubit support relation has a perfect deterministic classical-bit realization.","Apex-join families yield binary perfect same-dimensional games in every dimension $d\\ge 3$, with the compressed family $(13+t,8+t,2)$ achieving $C_{d_t}=S-1<Q_{d_t}=S$.","The qutrit Torpedo and SIC antidistinguishability games show the higher-output regime is governed by affine-plane and exclusion combinatorics rather than ordinary graph coloring, with seven preparations minimal for a qutrit-over-trit Torpedo separation."],"supporting_citations":[{"why":"Establishes the chromatic-number and complex-orthogonal-rank characterization for graph promise-equality problems that Theorem 3 lifts to a complete classification.","marker":"[5]"},{"why":"Gives the systematic exact-communication treatment of these graph parameters, providing the framework Theorem 3 extends.","marker":"[6]"},{"why":"Supplies a recent quantum-finite-automaton graph promise problem, the closest known realization whose converse Theorem 3 makes universal.","marker":"[7]"},{"why":"Provides the 13-ray set whose orthogonality graph is the flagship $G_{13}$.","marker":"[8]"},{"why":"Studies $G_{13}$ as a graph, contributing the chromatic number $\\chi(G_{13})=4$ and the apex-graph construction used in Section VI.","marker":"[9]"},{"why":"Supplies the prime-power finite-field formulation and the perfect quantum strategy for the Torpedo game analyzed in Section VII.","marker":"[11]"},{"why":"Constructs the qutrit SIC whose triples are all antidistinguishable, supporting the antidistinguishability game.","marker":"[13]"},{"why":"Connects state antidistinguishability to communication complexity and justifies the unavoidable-loss form of the antidistinguishability score.","marker":"[14]"},{"why":"Provides the DSATUR-style backtracking algorithm used for the exact coloring certificates in Appendix A.","marker":"[19]"}],"fun_headline_variants":["Perfect binary games are graph coloring problems","Perfect qubit strategies always become classical bits","13-ray game: quantum 40 beats classical 39","Game size equals edge biclique cover number","Quantum advantage in games reduces to chromatic number"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the exact backtracking enumerations in Appendix A are correct: the paper gives explicit certificates only for the 4-colorability of every one-vertex deletion of $G_{13}$ and for one 4-coloring, while the exhaustive 3-colorability searches and the tested-set and biclique-cover minima are asserted without public code, so an undetected error in those counts would change the flagship values $C_3=39$, $Q_3=40$, $\\mathrm{bc}(G_{13})=8$, and the eight-input minimality claim, although Theorems 3 and 6 would remain intact.","fun_headline_variants_meta":{"raw":{"variants":["Perfect binary games are graph coloring problems","Perfect qubit strategies always become classical bits","13-ray game: quantum 40 beats classical 39","Game size equals edge biclique cover number","Quantum advantage in games reduces to chromatic number"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000244,"raw_usage":{"total_tokens":1596,"prompt_tokens":1075,"completion_tokens":521,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":691,"completion_tokens_details":{"reasoning_tokens":452}},"tokens_in":691,"tokens_out":521,"duration_ms":6421,"temperature":1.0,"reasoning_tokens":452,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T05:27:37.189710+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an independent exact 3-colorability check on $G_{13}$ and its 13 one-vertex deletions: a 3-coloring of $G_{13}$ would refute $\\chi(G_{13})=4$, and a tested set of seven vertices whose incident-edge subgraph is not 3-colorable would refute the claimed eight-vertex minimum; likewise, an edge biclique cover of $G_{13}$ using seven bicliques, or a binary-output support game realizing $G_{13}$ with seven Bob inputs, would refute $\\mathrm{bc}(G_{13})=8$.","supporting_citations":[{"cited_title":"Stahlke, Quantum zero-error source-channel coding and non-commutative graph theory, IEEE Trans","cited_arxiv_id":null,"evidence_quote":"Establishes the chromatic-number and complex-orthogonal-rank characterization for graph promise-equality problems that Theorem 3 lifts to a complete classification."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the systematic exact-communication treatment of these graph parameters, providing the framework Theorem 3 extends."},{"cited_title":"de Wolf,Quantum Computing and Communication Complexity, Ph.D","cited_arxiv_id":null,"evidence_quote":"Provides the 13-ray set whose orthogonality graph is the flagship $G_{13}$."},{"cited_title":"Briët, H","cited_arxiv_id":null,"evidence_quote":"Studies $G_{13}$ as a graph, contributing the chromatic number $\\chi(G_{13})=4$ and the apex-graph construction used in Section VI."},{"cited_title":"Yu and C","cited_arxiv_id":null,"evidence_quote":"Supplies the prime-power finite-field formulation and the perfect quantum strategy for the Torpedo game analyzed in Section VII."},{"cited_title":"Huang, G.-Y","cited_arxiv_id":null,"evidence_quote":"Constructs the qutrit SIC whose triples are all antidistinguishable, supporting the antidistinguishability game."},{"cited_title":"Emeriau, M","cited_arxiv_id":null,"evidence_quote":"Connects state antidistinguishability to communication complexity and justifies the unavoidable-loss form of the antidistinguishability score."},{"cited_title":"Ramanathan and P","cited_arxiv_id":null,"evidence_quote":"Provides the DSATUR-style backtracking algorithm used for the exact coloring certificates in Appendix A."}],"review_version":1}