Metraipolis › archive › dc_03759dae4020

On the Quantum Chromatic Gap II — arXiv:2610.40571

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.40571
License (as archived): CC0-1.0
Archived: 2026-11-01T02:38:23.628Z
SHA-256 of the archived text: b43be5c1cb5545383c1ca35e27e7d445e4f3301802e55349f09bf00eeec2fc51
Stable URL of this page: https://metraipolis.com/documento/dc_03759dae4020

How to cite

On the Quantum Chromatic Gap II — arXiv:2610.40571 — arXiv (en), https://arxiv.org/abs/2610.40571 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_03759dae4020 (Metraipolis archive dc_03759dae4020, sha256 b43be5c1cb5545383c1ca35e27e7d445e4f3301802e55349f09bf00eeec2fc51)

BibTeX

@misc{dc03759dae4020,
  title = {On the Quantum Chromatic Gap II — arXiv:2610.40571},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40571},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_03759dae4020; sha256 b43be5c1cb5545383c1ca35e27e7d445e4f3301802e55349f09bf00eeec2fc51},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40571. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\epsilon>0$, and every $k\in\mathbb N$, there is a $d$-to-$1$ label-cover game of classical value less than $\epsilon$ 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 $\chi_q$ is $3$ and whose classical chromatic number $\chi$ 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 $\chi$ grows exponentially in $\chi_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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Logic in Computer Science (cs.LO); Combinatorics (math.CO); Operator Algebras (math.OA).
Pagina del lavoro: https://arxiv.org/abs/2610.40571 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:28.327Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).