Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912243345522688 |
|---|---|
| author | Montanaro, Ashley Zhou, Leo |
| author_facet | Montanaro, Ashley Zhou, Leo |
| contents | We present new advances towards achieving exponential quantum speedups for solving optimization problems by low-depth quantum algorithms. Specifically, we focus on families of combinatorial optimization problems that exhibit symmetry and contain planted solutions. We rigorously prove that the 1-step Quantum Approximate Optimization Algorithm (QAOA) can achieve a success probability of $Ω(1/\sqrt{n})$, and sometimes $Ω(1)$, for finding the exact solution in many cases. This allows us to prove a separation of $O(1)$ quantum queries and $Ω(n/\log n)$ classical queries required to find the planted solution in the latter setting. Furthermore, we construct near-symmetric optimization problems by randomly sampling the individual clauses of symmetric problems, and prove that the QAOA maintains a strong success probability in this setting even when the symmetry is broken. Finally, we construct various families of near-symmetric Max-SAT problems and benchmark state-of-the-art classical solvers, discovering instances where all known general-purpose classical algorithms require exponential time. Therefore, our results indicate that low-depth QAOA may achieve an exponential quantum speedup for optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04979 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA Montanaro, Ashley Zhou, Leo Quantum Physics Data Structures and Algorithms We present new advances towards achieving exponential quantum speedups for solving optimization problems by low-depth quantum algorithms. Specifically, we focus on families of combinatorial optimization problems that exhibit symmetry and contain planted solutions. We rigorously prove that the 1-step Quantum Approximate Optimization Algorithm (QAOA) can achieve a success probability of $Ω(1/\sqrt{n})$, and sometimes $Ω(1)$, for finding the exact solution in many cases. This allows us to prove a separation of $O(1)$ quantum queries and $Ω(n/\log n)$ classical queries required to find the planted solution in the latter setting. Furthermore, we construct near-symmetric optimization problems by randomly sampling the individual clauses of symmetric problems, and prove that the QAOA maintains a strong success probability in this setting even when the symmetry is broken. Finally, we construct various families of near-symmetric Max-SAT problems and benchmark state-of-the-art classical solvers, discovering instances where all known general-purpose classical algorithms require exponential time. Therefore, our results indicate that low-depth QAOA may achieve an exponential quantum speedup for optimization problems. |
| title | Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.04979 |