  The quantum approximate optimization algorithm (QAOA) is a variational method
for noisy, intermediate-scale quantum computers to solve combinatorial
optimization problems. Quantifying performance bounds with respect to specific
problem instances provides insight into when QAOA may be viable for solving
real-world applications. Here, we solve every instance of MaxCut on
non-isomorphic unweighted graphs with nine or fewer vertices by numerically
simulating the pure-state dynamics of QAOA. Testing up to three layers of QAOA
depth, we find that distributions of the approximation ratio narrow with
increasing depth while the probability of recovering the maximum cut generally
broadens. We find QAOA exceeds the Goemans-Williamson approximation ratio bound
for most graphs. We also identify consistent patterns within the ensemble of
optimized variational circuit parameters that offer highly efficient heuristics
for solving MaxCut with QAOA. The resulting data set is presented as a
benchmark for establishing empirical bounds on QAOA performance that may be
used to test on-going experimental realizations.

Quantum Physics;Computational Physics