We prove that, to each synchronous non-local game \(\mathcal {G}=(I,O,\lambda )\) with \(|I|=n\) and \(|O|=m \ge 3\) , there is an associated graph \(G_{\lambda }\) for which approximate winning strategies for the game \(\mathcal {G}\) and the 3-coloring game for \(G_{\lambda }\) are preserved. That is, using a similar graph to previous work of the author (Ann Henri Poincaré, 2024), any synchronous strategy for \(\text {Hom}(G_{\lambda },K_3)\) that wins the game with probability \(1-\varepsilon \) with respect to the uniform probability distribution on the edges, yields a strategy in the same model that wins the game \(\mathcal {G}\) with respect to the uniform distribution with probability at least \(1-h(n,m)\varepsilon ^{\frac{1}{2}}\) , where h is a polynomial in n and \(2^m\) . As an application, we prove that the gapped promise problem for quantum 3-coloring is undecidable, with doubly inverse exponential gap. Moreover, we show that the problem of determining whether a synchronous non-local game \(\mathcal {G}\) has quantum value 1 or quantum value less than \(1-\varepsilon \) , when promised that one of those occur, can be reduced to a related promise problem for the non-commutative Max-3-Cut of a graph |E|, giving a partial answer to a problem posed by Culf et al. (Approximation algorithms for noncommutative constraint satisfaction problems, 2014. arXiv:2312.16765), along with evidence for a sharp computability gap in the non-commutative Max-3-Cut problem. This also gives evidence that the non-commutative (respectively, commuting operator framework) Max-3-Cut of a graph is uncomputable. All of these results avoid use of the unique games conjecture.
