Extending relax-and-round combinatorial optimization solvers with quantum correlations
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_ | 1866910306730508288 |
|---|---|
| author | Dupont, Maxime Sundar, Bhuvanesh |
| author_facet | Dupont, Maxime Sundar, Bhuvanesh |
| contents | We introduce a relax-and-round approach embedding the quantum approximate optimization algorithm (QAOA) with $p\geq 1$ layers. We show for many problems, including Sherrington-Kirkpatrick spin glasses, that at $p=1$, it is as accurate as its classical counterpart, and maintains the infinite-depth optimal performance guarantee of the QAOA. Employing a different rounding scheme, we prove the method shares the performance of the Goemans-Williamson algorithm for the maximum cut problem on certain graphs. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_05821 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Extending relax-and-round combinatorial optimization solvers with quantum correlations Dupont, Maxime Sundar, Bhuvanesh Quantum Physics We introduce a relax-and-round approach embedding the quantum approximate optimization algorithm (QAOA) with $p\geq 1$ layers. We show for many problems, including Sherrington-Kirkpatrick spin glasses, that at $p=1$, it is as accurate as its classical counterpart, and maintains the infinite-depth optimal performance guarantee of the QAOA. Employing a different rounding scheme, we prove the method shares the performance of the Goemans-Williamson algorithm for the maximum cut problem on certain graphs. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms. |
| title | Extending relax-and-round combinatorial optimization solvers with quantum correlations |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2307.05821 |