Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.05216 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm that can be used to approximately solve combinatorial optimization problems. However, a major limitation of QAOA is that it is a "local" algorithm for finite circuit depths, meaning it can only optimize over local properties of the graph. In this paper, we present Phantom-QAOA, a new QAOA ansatz that introduces only one additional parameter to the standard ansatz -- regardless of system size -- allowing QAOA to "see" more of the graph at a given depth $p$. We achieve this by modifying the target graph to include additional $α$-weighted edges, with $α$ serving as a tunable parameter. This modified graph is then used to construct the phase operator and allows QAOA to explore a wider range of the graph's features. We derive a general formula for our new ansatz at $p=1$ and analytically show an improvement in the approximation ratio for cycle graphs. We also provide numerical experiments that demonstrate significant improvements in the approximation ratio for the Max-Cut problem over the standard QAOA ansatz for $p=1$ and $p=2$ on random regular graphs up to 16 nodes.