QISS classically samples a pairwise model built from O(N) low-weight QAOA correlators and outperforms standard QAOA at larger depths on MaxCut and MIS benchmarks.
Extending relax-and-round combinatorial optimization solvers with quantum correlations
1 Pith paper cite this work, alongside 4 external citations. Polarity classification is still indexing.
1
Pith paper citing it
4
external citations · Pith
abstract
We introduce a relax-and-round approach embedding the quantum approximate optimization algorithm (QAOA) with $p\geq 1$ layers. We show for many problems, including Sherrington-Kirkpatrick spin glasses, that at $p=1$, it is as accurate as its classical counterpart, and maintains the infinite-depth optimal performance guarantee of the QAOA. Employing a different rounding scheme, we prove the method shares the performance of the Goemans-Williamson algorithm for the maximum cut problem on certain graphs. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms.
fields
quant-ph 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Quantum-informed surrogate sampling for combinatorial optimization
QISS classically samples a pairwise model built from O(N) low-weight QAOA correlators and outperforms standard QAOA at larger depths on MaxCut and MIS benchmarks.