Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA

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.