Obstacles to Variational Quantum Optimization from Symmetry Protection

The quantum approximate optimization algorithm (QAOA) employs variational states generated by a parameterized quantum circuit to maximize the expected value of a Hamiltonian encoding a classical cost function. Whether or not the QAOA can outperform classical algorithms in some tasks is an actively debated question. Our work exposes fundamental limitations of the QAOA resulting from the symmetry and the locality of variational states. A surprising consequence of our results is that the classical Goemans-Williamson algorithm outperforms the QAOA for certain instances of MaxCut, at any constant level. To overcome these limitations, we propose a nonlocal version of the QAOA and give numerical evidence that it significantly outperforms the standard QAOA for frustrated Ising models.

Figure 1

(a) Approximation ratios achieved by the level-1 RQAOA (blue) and the Goemans-Williamson (GW) algorithm [9] (red) for 15 instances of the Ising cost function with random $\pm 1$ couplings defined on the 2D toric grid of size $16\times 16$. In case (b), the Ising Hamiltonian also includes random $\pm 1$ external fields. The RQAOA threshold value is $n_c=20$. We found that the standard level-1 QAOA achieves approximation ratios below $1/2$ for all considered instances (not shown). The GW algorithm was implemented with $n=256$ rounding attempts, and the best found solution was selected. The exact maximum energy was computed using integer linear programming.