Classical Simulation of Quantum CSP Strategies
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909557798731776 |
|---|---|
| author | Banakh, Demian Ciardo, Lorenzo Kozik, Marcin Tułowiecki, Jan |
| author_facet | Banakh, Demian Ciardo, Lorenzo Kozik, Marcin Tułowiecki, Jan |
| contents | We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on $(i)$ the size of the shared quantum system used in the quantum strategy, and $(ii)$ structural parameters of the CSP template. The result is obtained via a combinatorial characterisation of perfect classical strategies with extra communication channels and a geometric rounding procedure for the projection-valued measurements involved in quantum strategies. A key intermediate step of our proof is to establish that the gap between the classical chromatic number of graphs and its quantum variant is bounded when the quantum strategy involves shared quantum information of bounded size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23206 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Classical Simulation of Quantum CSP Strategies Banakh, Demian Ciardo, Lorenzo Kozik, Marcin Tułowiecki, Jan Quantum Physics Computational Complexity Logic in Computer Science Combinatorics 81P45, 05C15 We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on $(i)$ the size of the shared quantum system used in the quantum strategy, and $(ii)$ structural parameters of the CSP template. The result is obtained via a combinatorial characterisation of perfect classical strategies with extra communication channels and a geometric rounding procedure for the projection-valued measurements involved in quantum strategies. A key intermediate step of our proof is to establish that the gap between the classical chromatic number of graphs and its quantum variant is bounded when the quantum strategy involves shared quantum information of bounded size. |
| title | Classical Simulation of Quantum CSP Strategies |
| topic | Quantum Physics Computational Complexity Logic in Computer Science Combinatorics 81P45, 05C15 |
| url | https://arxiv.org/abs/2503.23206 |