Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2309.10957 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909114074923008 |
|---|---|
| author | Carlson, Charlie Jorquera, Zackary Kolla, Alexandra Kordonowy, Steven Wayland, Stuart |
| author_facet | Carlson, Charlie Jorquera, Zackary Kolla, Alexandra Kordonowy, Steven Wayland, Stuart |
| contents | We initiate the algorithmic study of the Quantum Max-$d$-Cut problem, a quantum generalization of the well-known Max-$d$-Cut problem. The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. Equivalently, this problem is physically motivated by the $SU(d)$-Heisenberg model, a spin glass model that generalized the well-known Heisenberg model over qudits. We develop a polynomial-time randomized approximation algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees. Moreover, we prove the tightness of our analysis by presenting an algorithmic gap instance for Quantum Max-d-Cut problem with $d \geq 3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_10957 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for Quantum Max-$d$-Cut Carlson, Charlie Jorquera, Zackary Kolla, Alexandra Kordonowy, Steven Wayland, Stuart Quantum Physics We initiate the algorithmic study of the Quantum Max-$d$-Cut problem, a quantum generalization of the well-known Max-$d$-Cut problem. The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. Equivalently, this problem is physically motivated by the $SU(d)$-Heisenberg model, a spin glass model that generalized the well-known Heisenberg model over qudits. We develop a polynomial-time randomized approximation algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees. Moreover, we prove the tightness of our analysis by presenting an algorithmic gap instance for Quantum Max-d-Cut problem with $d \geq 3$. |
| title | Approximation Algorithms for Quantum Max-$d$-Cut |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2309.10957 |