There is a strong interest in finding challenging instances of NP-hard problems, from the perspective of showing quantum advantage. Due to the limits of near-term NISQ devices, it is moreover useful if these instances are small. In this work, we identify two graph families (|V|<1000) on which the Goemans-Williamson algorithm for approximating the Max-Cut achieves at most a 0. 912-approximation. We further show that, in comparison, a recent quantum algorithm, Quantum Approximate Optimization Algorithm (depth p=1), is a 0. 592-approximation on Karloff instances in the limit (n), and is at best a 0. 894-approximation on a family of strongly-regular graphs. We further explore construction of challenging instances computationally by perturbing edge weights, which may be of independent interest, and include these in the CI-QuBe github repository.
Tate et al. (Sun,) studied this question.