On the Quantum Chromatic Gap II
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≥ 4, every ε>0, and every k∈ℕ, 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.
Related
- On the exact quantum chromatic number of generalized Johnson graphs
- Chromatic Constraints on Quantum Observables: Gaps, Contextuality, and Separability
- Structural Realizations and Invariants of Universal Obstruction Cohomology: Goodwillie Towers, Chromatic Filtrations, and Quantum Contextuality
- On the k-Distance Chromatic Number of Unicyclic Graphs
- Minimal Cayley graphs with large chromatic number
BibTeX
@misc{ciardo2026quantum,
title = {{On the Quantum Chromatic Gap II}},
author = {Lorenzo Ciardo and Antoine Mottet},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40571},
eprint = {2610.40571},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40571},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Quantum Chromatic Gap II
AU - Lorenzo Ciardo
AU - Antoine Mottet
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40571
UR - https://arxiv.org/abs/2610.40571
AB - 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∈ℕ, 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.
ER -