Quantum strategies solve games classical methods cannot with small quantum resources
On the Quantum Chromatic Gap II
Computational ComplexityLogic in Computer Science
Summary
The paper investigates how quantum mechanics allows players to perfectly win certain games that are impossible to win classically. The authors confirm a previous prediction showing that for some complex games, quantum players can always win using a limited type of quantum entanglement and measurements involving distant elements. This leads to examples of networks (graphs) that seem simple when viewed quantumly but are very complex classically. Their work deepens our understanding of quantum advantages in game theory and graph coloring problems.
What this means in practice
- •For quantum protocol designers: Build quantum communication strategies for complex coordination problems that no classical method can perfectly solve.
- •For quantum algorithm developers: Use the constructions of pseudo-telepathic games to identify quantum resources needed to outperform classical algorithms in decision problems.
A theory result. No direct application yet.
Authors
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.