  The Quantum Approximate Optimization Algorithm (QAOA) constitutes one of the
often mentioned candidates expected to yield a quantum boost in the era of
near-term quantum computing. In practice, quantum optimization will have to
compete with cheaper classical heuristic methods, which have the advantage of
decades of empirical domain-specific enhancements. Consequently, to achieve
optimal performance we will face the issue of algorithm selection, well-studied
in practical computing. Here we introduce this problem to the quantum
optimization domain.
  Specifically, we study the problem of detecting those problem instances of
where QAOA is most likely to yield an advantage over a conventional algorithm.
As our case study, we compare QAOA against the well-understood approximation
algorithm of Goemans and Williamson (GW) on the Max-Cut problem. As exactly
predicting the performance of algorithms can be intractable, we utilize machine
learning to identify when to resort to the quantum algorithm. We achieve
cross-validated accuracy well over 96\%, which would yield a substantial
practical advantage. In the process, we highlight a number of features of
instances rendering them better suited for QAOA. While we work with simulated
idealised algorithms, the flexibility of ML methods we employed provides
confidence that our methods will be equally applicable to broader classes of
classical heuristics, and to QAOA running on real-world noisy devices.
