Reachability Deficits Implicit in Google's Quantum Approximate Optimization of Graph Problems
V. Akshay, Hariphan Philathong, I. Zacharov, Jacob Biamonte · arXiv (Cornell University) · 2020
The quantum approximate optimisation algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the $density$ of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. We performed a detailed reanalysis of the data reproduced from Google's Sycamore superconducting qubit quantum processor executing QAOA applied to minimization problems on graphs. We found that Sycamore approaches a rapid fall-off in approximation quality experienced beyond intermediate-density instances. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.