Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910764843925504 |
|---|---|
| author | Harris, Samuel J. |
| author_facet | Harris, Samuel J. |
| contents | 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 $\text{Hom}(G_λ,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. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19405 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem Harris, Samuel J. Quantum Physics Operator Algebras 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 $\text{Hom}(G_λ,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. 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. |
| title | Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem |
| topic | Quantum Physics Operator Algebras |
| url | https://arxiv.org/abs/2412.19405 |