REVIEW 1 major objections 4 minor 33 references
Perfect Games in Dimension-Bounded Communication
T0 review · 1 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. 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 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.
What would settle it
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$.
Extended reading notes
Core claim
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$.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (1)
- [§V.C, Eqs. (44)–(51); Appendix A] 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.
minor comments (4)
- [Abstract and Eq. (9)] 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.
- [§VII, Theorem 12 and Corollary 15] 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.
- [Appendix A, item 1] 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.
- [Data and Code Availability] 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.
Circularity Check
No significant circularity: the central reductions are proven from the operational definitions, and the imported graph facts are independently certified in Appendix A.
full rationale
The paper's derivation chain is self-contained. Theorem 3 proves the conflict-graph equivalence directly: for binary outputs, Proposition 1 reduces classical perfection to a partition with nonempty intersections, and the equivalence with proper d-colorability follows from the observation that empty intersections occur exactly when both {0} and {1} are present; the quantum direction constructs orthogonal supports from kernels of losing effects (Eqs. (14)-(15)) and conversely builds a POVM from an orthogonal representation (Eqs. (16)-(17)). Proposition 5 proves Y_min(G)=bc(G) by showing that each Bob input generates exactly the edges of a complete bipartite graph and that any biclique cover can be turned into a game; this is an equivalence proved in both directions, not a conclusion fed into itself. Theorem 6 uses only the Bloch-sphere geometry of qubit effects and does not cite any prior result as a premise. The numeric G13 layer is supported by explicit vectors, the explicit 4-coloring (A4), the near-coloring (41), and Table II certificates for all one-vertex deletions. The cited fact chi(G13)=4 from Ref. [9] is independently re-established by the Appendix A backtracking result (no 3-coloring plus a 4-coloring), so no load-bearing self-citation or imported uniqueness assumption occurs. The exhaustive enumerations behind alpha(G13)=5, bc(G13)=8, and the tested-set minima are asserted rather than code-public, but an unverified finite search is a reproducibility limitation, not circularity; none of the paper's equations reduce to their own inputs by construction.
Assumptions & free parameters
assumptions (5)
- domain assumption Quantum strategies are modeled by density operators and POVMs on C^d.
- domain assumption The qutrit Torpedo relation admits a perfect quantum strategy.
- domain assumption Every triple of qutrit SIC states is antidistinguishable.
- standard math G13 has chromatic number 4 and no 4-cycle.
- standard math A graph with a 2-dimensional orthogonal representation is bipartite.
Cite this review
Pith. "Pith review of Perfect Games in Dimension-Bounded Communication." pith.science (2026). https://pith.science/paper/KO5ZX7YP
@misc{pith2026260805092,
author = {Pith},
title = {Pith review of: Perfect Games in Dimension-Bounded Communication},
year = {2026},
howpublished = {\url{https://pith.science/paper/KO5ZX7YP}},
note = {Machine review of arXiv:2608.05092}
}
abstract
Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension $d$ satisfies every prescribed winning constraint, whereas a classical $d$-level message cannot. We establish two structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a $d$-level message is equivalent to $d$-colorability, perfect $d$-dimensional quantum realization is equivalent to a $d$-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. As a flagship application, the $13$-ray qutrit graph yields a compressed game $(X,Y,B)=(13,8,2)$ with $C_3=39<Q_3=S=40$, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.
Figures
Reference graph
Works this paper leans on
-
[1]
A perfect classical strategy with ad-level message exists if and only if χ(ΓG)≤d.(11)
-
[2]
For B = {0, 1}, every nonempty subset of B is {0}, {1}, or {0, 1}
A perfectd-dimensional quantum strategy exists if and only if ξC(ΓG)≤d.(12) Proof. For B = {0, 1}, every nonempty subset of B is {0}, {1}, or {0, 1}. A family of such sets has empty intersection if and only if it contains both a{0} set and a {1} set. Hence all classical conflicts are pairwise, and Proposition 1 is exactly the proper-coloring condition in ...
2025
-
[3]
This geometry yields both the exact perfect-message cost and the general classical loss boundLTor ≥X− 2M. In particular, seven preparations are minimal for a qutrit-over-trit perfect separation within the Torpedo construction when all four Bob inputsq∈F 3 ∪ {∞}are retained. II. EXACT-SUPPORT PREPARE-AND-MEASURE GAMES A. Operational definition For a positi...
-
[4]
Gallego, N
R. Gallego, N. Brunner, C. Hadley, and A. Acín, Device- independent tests of classical and quantum dimensions, Phys. Rev. Lett.105, 230501 (2010)
2010
-
[5]
Stahlke, Quantum zero-error source-channel coding and non-commutative graph theory, IEEE Trans
D. Stahlke, Quantum zero-error source-channel coding and non-commutative graph theory, IEEE Trans. Inf. Theory62, 554–577 (2016). 11
work page 2016
-
[6]
M. J. Renner, A. Tavakoli, and M. T. Quintino, Classical cost of transmitting a qubit, Phys. Rev. Lett.130, 120801 (2023)
work page 2023
-
[7]
S. Schlösser and M. Kleinmann, Bounding the classical cost of simulating quantum behaviors in the prepare-and- measure scenario, arXiv:2603.01255 (2026)
arXiv 2026
-
[8]
de Wolf,Quantum Computing and Communication Complexity, Ph.D
R. de Wolf,Quantum Computing and Communication Complexity, Ph.D. thesis, University of Amsterdam, ILLC Dissertation Series DS-2001-06 (2001)
work page 2001
Show all 33 references
-
[9]
Briët, H
J. Briët, H. Buhrman, D. Leung, T. Piovesan, and F. Speelman, Round elimination in exact communication complexity, in10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015), Leibniz International Proceedings in Informat- ics, Vol. 44 (Sc...
2015 doi
-
[10]
Prakash, Robust quantum memory advantage from contextuality, arXiv:2607.00507 (2026)
S. Prakash, Robust quantum memory advantage from contextuality, arXiv:2607.00507 (2026)
2026 arXiv
-
[11]
Yu and C
S. Yu and C. H. Oh, State-independent proof of Kochen– Specker theorem with 13 rays, Phys. Rev. Lett.108, 030402 (2012)
2012
-
[12]
Mančinska and D
L. Mančinska and D. E. Roberson, Oddities of quantum colorings, Baltic J. Mod. Comput.4, 846–859 (2016)
2016
-
[13]
Huang, G.-Y
C.-J. Huang, G.-Y. Xiang, Y. Guo, K.-D. Wu, B.-H. Liu, C.-F. Li, G.-C. Guo, and A. Tavakoli, Nonlocality, steer- ing, andquantumstatetomographyinasingleexperiment, Phys. Rev. Lett.127, 020401 (2021)
2021
-
[14]
Emeriau, M
P.-E. Emeriau, M. Howard, and S. Mansfield, Quantum advantage in information retrieval, PRX Quantum3, 020307 (2022)
2022
-
[15]
Diviánszky, I
P. Diviánszky, I. Márton, E. Bene, and T. Vértesi, Certi- fication of qubits in the prepare-and-measure scenario with large input alphabet and connections with the Grothendieck constant, Sci. Rep.13, 13200 (2023)
2023
-
[16]
J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves, Symmetric informationally complete quantum mea- surements, J. Math. Phys.45, 2171–2180 (2004)
2004
-
[17]
Havlíček and J
V. Havlíček and J. Barrett, Simple communication com- plexity separation from quantum state antidistinguisha- bility, Phys. Rev. Research2, 013326 (2020)
2020
-
[18]
J. Bae, K. Flatt, T. Heinosaari, O. Kerppo, K. Mohan, A. Muñoz-Moller, and A. Rai, Random exclusion codes: Quantum advantages of single-shot communication, Phys. Rev. Research8, 013171 (2026)
2026
-
[19]
Ramanathan and P
R. Ramanathan and P. Horodecki, Necessary and suffi- cient condition for state-independent contextual measure- ment scenarios, Phys. Rev. Lett.112, 040404 (2014)
2014
-
[20]
Cabello, M
A. Cabello, M. Kleinmann, and C. Budroni, Necessary and sufficient condition for quantum state-independent contextuality, Phys. Rev. Lett.114, 250402 (2015)
2015
-
[21]
Cabello, Simplest bipartite perfect quantum strategies, Phys
A. Cabello, Simplest bipartite perfect quantum strategies, Phys. Rev. Lett.134, 010201 (2025)
2025
-
[22]
Brélaz, New methods to color the vertices of a graph, Commun
D. Brélaz, New methods to color the vertices of a graph, Commun. ACM22, 251–256 (1979), DOI: 10.1145/359094.359101. Appendix A: Explicit graph data and finite certificates The edge set corresponding to Eq. (39) is E(G13) ={{1,2},{1,3},{1,4},{1,5}, {2,3},{2,6},{2,7},{3,8}, {3,9...
1979
-
[23]
Hence τ (G13) = 8
Enumeration of all213 vertex subsets gives α(G13) = 5,(A2) with certificate{1, 10, 11, 12, 13}. Hence τ (G13) = 8. Direct enumeration of common-neighbor pairs finds no4-cycle. Consequently every biclique ofG13 is a star and bc(G13) =τ(G 13) = 8,(A3) which certifies the minimum...
-
[24]
Exact backtracking finds no3-coloring and finds the 4-coloring (1,2,3,2,3,1,3,2,1,2,3,1,4),(A4) where entries are listed in vertex order
-
[25]
Enumeration of the313 trit encodings gives δ3(G13, V(G13)) = 2, δ 3(G13, T8) = 1.(A5) The encoding (41) attains both minima
-
[26]
For each of the thirteen one-vertex deletions, exact back- tracking returns a3-coloring
Enumeration of all tested sets gives Eq.(51). For each of the thirteen one-vertex deletions, exact back- tracking returns a3-coloring. Explicit certificates are listed in Table II
-
[27]
12 TABLE II
The script verifies Lemma 11 for all 9 3 = 84triples and independently cross-checks the analytic values C3 = 33for the full qutrit Torpedo game andC3 = 27for each of its 9 7 = 36seven-point restrictions. 12 TABLE II. Explicit3-colorings of every one-vertex deletion ofG13. Each...
-
[28]
The symmetric and compressedG 13 inequalities For convenience, the neighborhoods of the vertices in the labeling of Eq. (39) are 1:{2,3,4,5}8 :{3,9,12,13} 2:{1,3,6,7}9 :{3,8,10,11} 3:{1,2,8,9}10:{5,7,9} 4:{1,5,11,12}11:{4,6,9} 5:{1,4,10,13}12:{4,7,8} 6:{2,7,11,13}13:{5,6,8} 7:...
-
[29]
, at} be the apex set and recall that dt = 3 +t
All-dimensional apex inequalities Let At = {a1, . . . , at} be the apex set and recall that dt = 3 +t. For a base Bob inputy∈ {1, . . . ,13}define Φ(t) y [p] :=p(1|y, y) + X x∈NG13 (y) p(0|x, y) + tX j=1 p(0|aj, y), (D5) and for an apex Bob inputaj define Ψ(t) j [p] :=p(1|a j,...
-
[31]
Equiv- alently, ITor,9[p] := 36−L Tor,9[p]≤33,(D11) with qutrit value36
Full qutrit Torpedo inequality For the full preparation setF2 3, define LTor,9[p] := X (x,z)∈F2 3 X q∈{∞,0,1,2} p(hq(x, z)|(x, z), q).(D9) Every classical trit satisfies LTor,9[p]≥3,(D10) whereas the perfect qutrit strategy hasLTor,9 = 0. Equiv- alently, ITor,9[p] := 36−L Tor,...
-
[32]
Seven-preparation restriction Take the preparation set X7 ={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0)}. (D12) For each preparation, the forbidden outputshq(x, z)are (x, z) q=∞q= 0q= 1q= 2 (0,0) 0 0 0 0 (0,1) 0 2 2 2 (0,2) 0 1 1 1 (1,0) 1 0 1 2 (1,1) 1 2 0 1 (1,2) 1 1 2 0 (2,0)...
-
[33]
Bob’s inputs are the84triples R∈ [9] 3 , each written in increasing order as R = (r1, r2, r3)
Qutrit SIC antidistinguishability inequality Label the nine preparations by[9]. Bob’s inputs are the84triples R∈ [9] 3 , each written in increasing order as R = (r1, r2, r3). The classical-trit inequality has the compact loss form LSIC[p] := X R∈( [9] 3 ) 3X b=1 p(b|rb, R)≥3.(...
-
[61]
The compressed family is 9X y=2 Φ(t) y [p] + tX j=1 Ψ(t) j [p]≤t 2 + 21t+ 39,(D8) while a dt-dimensional quantum system reachest2 + 21t + 40
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.