Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
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_ | 1866929521663410176 |
|---|---|
| author | He, Entong |
| author_facet | He, Entong |
| contents | We review the correspondence between synchronous games and their associated $*$-algebra. Building upon the work of (Helton et al., New York J. Math. 2017), we propose results on algebraic and locally commuting graph identities. Based on the noncommutative Nullstellensätze (Watts, Helton and Klep, Annales Henri Poincaré 2023), we build computational tools that check the non-existence of perfect $C^*$ and algebraic strategies of synchronous games using Gröbner basis methods and semidefinite programming. We prove the equivalence between the hereditary and $C^*$ models questioned in (Helton et al., New York J. Math. 2017). We also extend the quantum-version NP-hardness reduction $\texttt{3-SAT}^* \leq_p \texttt{3-Coloring}^*$ due to (Ji, arXiv 2013) by exhibiting another instance of such reduction $\texttt{3-SAT}^* \leq_p \texttt{Clique}^*$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10114 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions He, Entong Quantum Physics Computational Complexity Operator Algebras We review the correspondence between synchronous games and their associated $*$-algebra. Building upon the work of (Helton et al., New York J. Math. 2017), we propose results on algebraic and locally commuting graph identities. Based on the noncommutative Nullstellensätze (Watts, Helton and Klep, Annales Henri Poincaré 2023), we build computational tools that check the non-existence of perfect $C^*$ and algebraic strategies of synchronous games using Gröbner basis methods and semidefinite programming. We prove the equivalence between the hereditary and $C^*$ models questioned in (Helton et al., New York J. Math. 2017). We also extend the quantum-version NP-hardness reduction $\texttt{3-SAT}^* \leq_p \texttt{3-Coloring}^*$ due to (Ji, arXiv 2013) by exhibiting another instance of such reduction $\texttt{3-SAT}^* \leq_p \texttt{Clique}^*$. |
| title | Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions |
| topic | Quantum Physics Computational Complexity Operator Algebras |
| url | https://arxiv.org/abs/2408.10114 |