The Better Solution Probability Metric: Optimizing QAOA to Outperform its Warm-Start Solution
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_ | 1866913499341389824 |
|---|---|
| author | Feeney, Sean Tate, Reuben Eidenbenz, Stephan |
| author_facet | Feeney, Sean Tate, Reuben Eidenbenz, Stephan |
| contents | This paper presents a numerical simulation investigation of the Warm-Start Quantum Approximate Optimization Algorithm (QAOA) as proposed by Tate et al. [1], focusing on its application to 3-regular Max-Cut problems. Our study demonstrates that Warm-Start QAOA consistently outperforms theoretical lower bounds on approximation ratios across various tilt angles, highlighting its potential in practical scenarios beyond worst-case predictions. Despite these improvements, Warm-Start QAOA with traditional parameters optimized for expectation value does not exceed the performance of the initial classical solution. To address this, we introduce an alternative parameter optimization objective, the Better Solution Probability (BSP) metric. Our results show that BSP-optimized Warm-Start QAOA identifies solutions at non-trivial tilt angles that are better than even the best classically found warm-start solutions with non-vanishing probabilities. These findings underscore the importance of both theoretical and empirical analyses in refining QAOA and exploring its potential for quantum advantage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_09012 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Better Solution Probability Metric: Optimizing QAOA to Outperform its Warm-Start Solution Feeney, Sean Tate, Reuben Eidenbenz, Stephan Quantum Physics Data Structures and Algorithms Emerging Technologies Numerical Analysis This paper presents a numerical simulation investigation of the Warm-Start Quantum Approximate Optimization Algorithm (QAOA) as proposed by Tate et al. [1], focusing on its application to 3-regular Max-Cut problems. Our study demonstrates that Warm-Start QAOA consistently outperforms theoretical lower bounds on approximation ratios across various tilt angles, highlighting its potential in practical scenarios beyond worst-case predictions. Despite these improvements, Warm-Start QAOA with traditional parameters optimized for expectation value does not exceed the performance of the initial classical solution. To address this, we introduce an alternative parameter optimization objective, the Better Solution Probability (BSP) metric. Our results show that BSP-optimized Warm-Start QAOA identifies solutions at non-trivial tilt angles that are better than even the best classically found warm-start solutions with non-vanishing probabilities. These findings underscore the importance of both theoretical and empirical analyses in refining QAOA and exploring its potential for quantum advantage. |
| title | The Better Solution Probability Metric: Optimizing QAOA to Outperform its Warm-Start Solution |
| topic | Quantum Physics Data Structures and Algorithms Emerging Technologies Numerical Analysis |
| url | https://arxiv.org/abs/2409.09012 |