Perfect Games in Dimension-Bounded Communication

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 three 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. Third, with at most two Bob inputs every perfect qutrit strategy admits a perfect classical-trit realization. An explicit seven-preparation qutrit game with three Bob inputs satisfies $C_3=20<Q_3=S=21$, so three Bob inputs are necessary and sufficient in dimension three. Conversely, a two-input, six-output game in dimension five satisfies $C_5=39<Q_5=S=40$. Thus the smallest dimension admitting a two-input perfect same-dimensional separation is either four or five; the four-dimensional case remains open. As a flagship binary 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.