Curator's Take
AI Commentary
This article shows that the boundary between classical and quantum communication can be captured exactly by familiar graph‑theoretic concepts: a $d$‑level classical message succeeds iff the associated conflict graph is $d$‑colorable, while a $d$‑dimensional quantum system succeeds when the graph admits a $d$‑dimensional orthogonal representation. By proving that any perfect qubit strategy can be simulated with just one classical bit, the authors identify a surprisingly tight limit on how much extra “quantum space’’ is needed for exact communication tasks, sharpening earlier results on contextuality and zero‑error information theory. The construction of minimal‑size games such as the 13‑ray qutrit example provides concrete benchmarks for hardware designers and policymakers seeking to certify genuine quantum advantage under strict dimension constraints.
— Mark Eatherly
Summary
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.