Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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.