On the Quantum Chromatic Gap

The largest known gap between quantum and classical chromatic number of graphs, obtained via quantum protocols for colouring Hadamard graphs based on the Deutsch–Jozsa algorithm and the quantum Fourier transform, is exponential. We put forth a quantum pseudo-telepathy version of Khot’s $d$-to-1 Games Conjecture and prove that, conditional on its validity, the gap is unbounded: There exist graphs whose quantum chromatic number is 3 and whose classical chromatic number is arbitrarily large. Furthermore, we show that the existence of a certain form of pseudo-telepathic XOR games would imply the conjecture and, thus, the unboundedness of the quantum chromatic gap. As two technical steps of our proof that might be of independent interest, we establish a quantum adjunction theorem for Pultr functors between categories of relational structures, and we prove that the Dinur–Khot–Kindler–Minzer–Safra reduction, recently used for proving the 2-to-2 Games Theorem, is quantum complete.