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!
|
| _version_ | 1866909571935633408 |
|---|---|
| author | Langfitt, Quinn Tate, Reuben Eidenbenz, Stephan |
| author_facet | Langfitt, Quinn Tate, Reuben Eidenbenz, Stephan |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_05216 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA Langfitt, Quinn Tate, Reuben Eidenbenz, Stephan Quantum Physics Optimization and Control 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. |
| title | Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA |
| topic | Quantum Physics Optimization and Control |
| url | https://arxiv.org/abs/2411.05216 |