{"ID":2864482,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.24108","arxiv_id":"2509.24108","title":"Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families","abstract":"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|\u003c1000$) 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 \\to \\infty$), 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.","short_abstract":"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|\u003c1000$) on which the Goemans-Williamson a...","url_abs":"https://arxiv.org/abs/2509.24108","url_pdf":"https://arxiv.org/pdf/2509.24108v1","authors":"[\"Reuben Tate\",\"Swati Gupta\"]","published":"2025-09-28T23:00:28Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}