Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.02585 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912201599614976 |
|---|---|
| author | Zhang, Zewen Paredes, Roger Sundar, Bhuvanesh Quiroga, David Kyrillidis, Anastasios Duenas-Osorio, Leonardo Pagano, Guido Hazzard, Kaden R. A. |
| author_facet | Zhang, Zewen Paredes, Roger Sundar, Bhuvanesh Quiroga, David Kyrillidis, Anastasios Duenas-Osorio, Leonardo Pagano, Guido Hazzard, Kaden R. A. |
| contents | The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT problems (All-SAT). G-QAOA is less resource-intensive and more adaptable for 3-SAT and Max-SAT than Grover's algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02585 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering Zhang, Zewen Paredes, Roger Sundar, Bhuvanesh Quiroga, David Kyrillidis, Anastasios Duenas-Osorio, Leonardo Pagano, Guido Hazzard, Kaden R. A. Quantum Physics Computational Physics The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT problems (All-SAT). G-QAOA is less resource-intensive and more adaptable for 3-SAT and Max-SAT than Grover's algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles. |
| title | Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering |
| topic | Quantum Physics Computational Physics |
| url | https://arxiv.org/abs/2402.02585 |