Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem

We prove that, to each synchronous non-local game mathcal{G}=(I,O,λ) with |I|=n and |O|=m geq 3, there is an associated graph G_λ for which approximate winning strategies for the game mathcal{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_λ,K₃\) 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. Moreover, we prove that there exists an αin (0,1) for which determining whether the non-commutative Max-3-Cut of a graph is |E| or less than α|E| is RE-hard, thus giving a positive answer to a problem posed by Culf, Mousavi and Spirig (arXiv:2312.16765), along with evidence for a sharp computability gap in the non-commutative Max-3-Cut problem. We also prove that there is some αin (0,1) such that determining the non-commutative (respectively, commuting operator framework) versions of the Max-3-Cut of a graph within a factor of α is uncomputable. All of these results avoid use of the unique games conjecture.