Approximation algorithms for noncommutative CSPs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909328116547584 |
|---|---|
| author | Culf, Eric Mousavi, Hamoon Spirig, Taro |
| author_facet | Culf, Eric Mousavi, Hamoon Spirig, Taro |
| contents | Noncommutative constraint satisfaction problems (NC-CSPs) are higher-dimensional operator extensions of classical CSPs. Despite their significance in quantum information, their approximability remains largely unexplored. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-$3$-Cut. We present a $0.864$-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and $\ast$-anticommutation, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_16765 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Approximation algorithms for noncommutative CSPs Culf, Eric Mousavi, Hamoon Spirig, Taro Quantum Physics Computational Complexity Noncommutative constraint satisfaction problems (NC-CSPs) are higher-dimensional operator extensions of classical CSPs. Despite their significance in quantum information, their approximability remains largely unexplored. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-$3$-Cut. We present a $0.864$-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and $\ast$-anticommutation, which may be of independent interest. |
| title | Approximation algorithms for noncommutative CSPs |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2312.16765 |