2025/09/28 by Tate, Reuben, Gupta, Swati
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2509.24108
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.