arXiv:2610.40571
On the Quantum Chromatic Gap II
Lorenzo Ciardo, Antoine Mottet
Abstract
We confirm a conjecture of the first author [SODA'26] on a strong form of pseudo-telepathy for Khot's $d$-to-$1$ games: for every $d\geq 4$, every $ε>0$, and every $k\in\mathbb N$, there is a $d$-to-$1$ 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 $k$. As a consequence, there exist graphs whose quantum chromatic number $χ_q$ is $3$ 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 $χ_q$. 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 $4$-to-$1$ games, we establish quantum completeness of this reduction, and we show that it preserves context radius.
AI Summary
The paper asks whether the classical chromatic number $\chi(G)$ can be bounded by any function of the finite-dimensional quantum chromatic number $\chi_q(G)$. It proves that for every $c\in\mathbb N$ there is a graph with $\chi_q(G)=3$ and $\chi(G)>c$, ruling out every such bound. The quantum value $3$ is optimal because quantum $2$-colourable graphs are bipartite; the previously known separation was exponential in the quantum chromatic number. The central result establishes a pseudo-telepathy analogue of the $d$-to-$1$ conjecture: for every $d\geq4$, $\epsilon>0$, and $k\in\mathbb N$, there is an exact $d$-to-$1$ label-cover instance with classical value below $\epsilon$ and a perfect finite-dimensional quantum assignment whose measurements commute whenever their questions are at constraint-graph distance at most $k$. The construction stretches the Mermin–Peres magic square with long equation wires to obtain arbitrarily large compatibility radius, then applies parallel repetition to reduce classical value. A multilayered Kneser-hypergraph reduction produces $3$-uniform hypergraphs with perfect, highly compatible quantum $2$-colourings but arbitrarily large classical chromatic number. Quantum completeness and compatibility preservation are established for the Fei–Minzer–Wang reduction to at-most-$4$-to-$1$ games, followed by completion to exact $d$-to-$1$ constraints. An earlier reduction chain then yields the graph-colouring separation. The resulting graphs and entanglement dimensions are enormous, and no compact explicit graph family is provided. Finding small or explicit witnesses remains open, as does the pseudo-telepathy conjecture for $d=2,3$.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.