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,\lambda )$ with $\mathrm{\mid }I\mathrm{\mid }=n$ and $\mathrm{\mid }O\mathrm{\mid }=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-\epsilon$ 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){\epsilon }^{\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 $\alpha \in (0,1)$ for which determining whether the non-commutative Max-$3$-Cut of a graph is $\mathrm{\mid }E\mathrm{\mid }$ or less than $\alpha \mathrm{\mid }E\mathrm{\mid }$ 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 $\alpha \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 $\alpha$ is uncomputable. All of these results avoid use of the unique games conjecture.