Approximate Quantum 3-Colorings of Graphs and the Quantum Max 3-Cut Problem

We prove that, to each synchronous non-local game G=(I,O,λ) with |I|=n and |O|=m≥3, there is an associated graph Gλ for which approximate winning strategies for the game G and the 3-coloring game for Gλ are preserved. That is, using a similar graph to previous work of the author (Ann Henri Poincaré, 2024), any synchronous strategy for Hom(Gλ,K3) that wins the game with probability 1-ε with respect to the uniform probability distribution on the edges, yields a strategy in the same model that wins the game G with respect to the uniform distribution with probability at least 1-h(n,m)ε12, where h is a polynomial in n and 2m. 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 G has quantum value 1 or quantum value less than 1-ε, 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.