On the Quantum Chromatic Gap II
In the authors' words
We confirm a conjecture of the first author [SODA'26] on a strong form of pseudo-telepathy for Khot's -to- games: for every , every , and every , there is a -to- label-cover game of classical value less than that admits a perfect quantum strategy using finite-dimensional shared entanglement with measurement contexts of radius at least . As a consequence, there exist graphs whose quantum chromatic number is and whose classical chromatic number is arbitrarily large. This is the first improvement on the quantum chromatic gap since the work of Brassard, Cleve, and Tapp [Phys. Rev. Lett.'99], which produced graphs for which grows exponentially in . To prove the conjecture, we proceed as follows. We start with a "stretched" version of the Mermin--Peres magic square, obtained by spacing out its equations and linking them with additional long equation wires. This operation increases the radius of the initial measurement contexts of a perfect quantum strategy for the game, while preserving classical unsatisfiability. We then apply parallel repetition to make the classical value small, and we turn the system into a pseudo-telepathic multi-layered Kneser hypergraph via a PCP construction of Dinur, Guruswami, Khot, and Regev [STOC'03]. Finally, we feed the resulting hypergraph into the reduction of Fei, Minzer, and Wang from hypergraph colouring to -to- games, we establish quantum completeness of this reduction, and we show that it preserves context radius.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.