Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor

We demonstrate the application of an intermediate scale superconducting qubit quantum processor to discrete optimization problems with the quantum approximate optimization algorithm (QAOA). We execute the QAOA across a variety of problem sizes and circuit depths for random instances of the Sherrington-Kirkpatrick model and 3-regular MaxCut, both high dimensional graph problems for which the QAOA requires significant compilation. We also study the Ising model restricted to the planar graph of our hardware. We experimentally measure and variationally optimize energy landscapes as a function of the QAOA parameters and observe clear features across even the largest instances studied (23 qubits). For Ising models on the hardware graph we obtain an approximation ratio that is independent of problem size and observe that performance increases with circuit depth until up to three or four layers of the algorithm. For the problems requiring compilation, we show that performance decreases with problem size but still provides an advantage over random guessing for problems on fewer than 18 qubits. Our experiment highlights the challenges of using quantum computers to optimize high dimensional graph problems and contributes to the developing tradition of using the QAOA as a holistic, device-level benchmark by providing a performance baseline on a popular quantum algorithm applied to well-studied optimization problems.