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$.
No sign of AI-generated text
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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≥4, every ε>0, and every k∈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.
The paper asks whether the classical chromatic number χ(G) can be bounded by any function of the finite-dimensional quantum chromatic number χq(G). It proves that for every c∈N there is a graph with χq(G)=3 and χ(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≥4, ϵ>0, and k∈N, there is an exact d-to-1 label-cover instance with classical value below ϵ 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.
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.
This paper deals with graph colouring games, an example of pseudo-telepathy, in which two provers can convince a verifier that a graph G is c-colourable where c is less than the chromatic number of the graph. They win the game if they convince the verifier. It is known that the players cannot win if they share only classical information, but they can win in some cases by sharing entanglement. The smallest known graph where the players win in the quantum setting, but not in the classical setting, was found by Galliard, Tapp and Wolf and has 32,768 vertices. It is a connected component of the Hadamard graph GN with N=c=16. Their protocol applies only to Hadamard graphs where N is a power of 2. We propose a protocol that applies to all Hadamard graphs. Combined with a result of Frankl, this shows that the players can win on any induced subgraph of G12 having 1609 vertices, with c=12. Combined with a result of Frankl and Rodl, our result shows that all sufficiently large Hadamard graphs yield pseudo-telepathy games.
The Mermin-Peres magic square game is a cooperative two-player nonlocal game in which shared quantum entanglement allows the players to win with certainty, while players limited to classical operations cannot do so, a phenomenon dubbed "quantum pseudo-telepathy". The game has a referee separately ask each player to color a subset of a 3x3 grid. The referee checks that their colorings satisfy certain parity constraints that can't all be simultaneously realized. We define a generalization of these games to be played on an arbitrary arrangement of intersecting sets of elements. We characterize exactly which of these games exhibit quantum pseudo-telepathy, and give quantum winning strategies for those that do. In doing so, we show that it suffices for the players to share three Bell pairs of entanglement even for games on arbitrarily large arrangements. Moreover, it suffices for Alice and Bob to use measurements from the three-qubit Pauli group. The proof technique uses a novel connection of Mermin-style games to graph planarity.
Nonlocal games provide a unified framework for studying the distinction between classical, quantum, and more general no-signaling correlations. This review connects the Bell-locality framework to several complementary mathematical representations of nonlocal games and quantum strategies. We begin with local hidden-variable models, the CHSH inequality, and the role of Bell nonlocality as a device-independent witness of entanglement. We then introduce nonlocal games through the standard predicate/verifier formalism and discuss representative examples, including XOR games, the GHZgame, graph-based colouring games, the Mermin–Peres magic square game, and Hardy’s paradox as a related logical manifestation of nonlocality. The central contribution of the article is a comparative organisation of four closely related representation frameworks: conditional-probability andcorrelation descriptions, Bell-functional formulations, entangled-value optimisation, and the quantum-operator approach together with the Navascu´es–Pironio–Ac´ın hierarchy. These viewpoints are instantiated for the CHSH, magic square, and GHZ games, showing how each representation emphasises a different aspect of the same underlying task. The resulting synthesis clarifies the relation between Bell inequality violations, perfect quantum strategies, pseudo-telepathy, and semidefinite relaxations of quantum correlations.
Nonlocal games provide a unified framework for studying the distinction between classical, quantum, and more general no-signaling correlations. In this work, we develop this perspective by connecting the Bell-locality framework to several complementary mathematical representations of nonlocal games and quantum strategies. We begin with local hidden-variable models, the CHSH inequality, and the role of Bell nonlocality as a device-independent witness of entanglement, and then introduce nonlocal games through the standard predicate/verifier formalism.
We next examine a set of representative examples, including XOR games, the GHZ game, graph-based coloring games, the Mermin-Peres magic square game, and Hardy's paradox as a related logical manifestation of nonlocality. Building on this foundation, we compare four closely related representation frameworks: conditional-probability and correlation descriptions, Bell-functional formulations, entangled-value optimization, and the quantum-operator approach together with the Navascues-Pironio-Acin (NPA) hierarchy. These viewpoints are then instantiated for the CHSH, magic square, and GHZ games, showing how each representation emphasizes a different aspect of the same underlying task.
Taken together, these examples show that nonlocal games can be studied simultaneously as geometric objects in correlation space, optimization problems over entangled resources, and operator-theoretic constructions. This multi-representation viewpoint clarifies the relation between Bell inequality violations, perfect quantum strategies, pseudo-telepathy, and semidefinite relaxations of quantum correlations.
Pseudo-telepathy provides an intuitive way of looking at Bell's inequalities, in which it is often obvious that feats achievable by use of quantum entanglement would be classically impossible. A~two-player pseudo-telepathy game proceeds as follows: Alice and Bob are individually asked a question and they must provide an answer. They are \emph{not} allowed any form of communication once the questions are asked, but they may have agreed on a common strategy prior to the execution of the game. We~say that they \emph{win} the game if the questions and answers fulfil a specific relation. A~game exhibits \emph{pseudo-telepathy} if there is a quantum strategy that makes Alice and Bob win the game for all possible questions, provided they share prior entanglement, whereas it would be impossible to win this game systematically in a classical setting. In~this paper, we show that any two-player pseudo-telepathy game requires the quantum players to share an entangled quantum system of dimension at least~\mbox{3×3}. This is optimal for two-player games, but the most efficient pseudo-telepathy game possible, in terms of total dimension, involves \emph{three} players who share a quantum system of dimension~\mbox{2×2×2}.