The QAOA on the ring of disagrees
Kunal Marwaha · 2026
Read The QAOA on the ring of disagrees by Kunal Marwaha (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29562.txt.
Description
Marwaha studies the Quantum Approximate Optimization Algorithm, or QAOA, on the ring of disagrees, a cycle graph where good cuts separate neighbouring vertices. A cut splits the graph's vertices into two groups, and the goal is to cross as many edges as possible. Local algorithms that cannot see the whole graph have a known ceiling on the fraction of edges they can cut in expectation.
Marwaha proves the QAOA reaches exactly that ceiling, settling a long-standing conjecture. Curiously, the proof never finds the optimal algorithm parameters. Instead, the problem becomes equivalent to finding an optimal pair of Laurent polynomials of bounded degree. That recasting is possible because the QAOA on one qubit can be expressed in the language of quantum signal processing. The result gives an exact performance guarantee for a flagship quantum algorithm on a clean test case, using classical polynomial machinery rather than direct parameter search.
Catalog record
| CREATOR | Kunal Marwaha |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.29562