pith. sign in

arxiv: 2606.29562 · v1 · pith:VGCXXVAXnew · submitted 2026-06-28 · 🪐 quant-ph

The QAOA on the ring of disagrees

Kunal Marwaha This is my paper

Pith reviewed 2026-06-30 07:18 UTC · model grok-4.3

classification 🪐 quant-ph
keywords QAOAcycle graphmax-cutquantum signal processingLaurent polynomialsapproximation algorithmssymmetric local algorithms
0
0 comments X

The pith

QAOA achieves the maximum cut fraction of (2p+1)/(2p+2) on cycle graphs for symmetric local algorithms.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the Quantum Approximate Optimization Algorithm reaches the upper bound on edge cuts that any symmetric local algorithm of depth p can achieve on the cycle graph. This bound is (2p+1)/(2p+2) in expectation. A sympathetic reader would care because the result settles a conjecture posed by Farhi, Goldstone, and Gutmann more than a decade ago. The argument works by mapping the one-qubit QAOA evolution exactly onto the problem of choosing an optimal pair of Laurent polynomials of degree at most 2p-1.

Core claim

Symmetric local algorithms that cannot see the whole graph at depth p cut at most a (2p+1)/(2p+2) fraction of edges in expectation on the cycle graph. The QAOA achieves this value, a long-standing conjecture of Farhi, Goldstone, and Gutmann. This is shown without finding the optimal parameters, by recasting the QAOA on one qubit in the language of quantum signal processing, which yields an exact equivalence to finding an optimal pair of Laurent polynomials of degree at most 2p-1.

What carries the argument

Exact equivalence between one-qubit QAOA and selection of an optimal pair of Laurent polynomials of degree at most 2p-1, obtained by recasting the algorithm in the language of quantum signal processing.

If this is right

  • QAOA reaches the performance ceiling of every symmetric local algorithm on cycles at every depth p.
  • The performance guarantee holds without ever computing the optimal QAOA angles.
  • The same polynomial equivalence supplies the proof for arbitrary p rather than case-by-case verification.
  • Any future symmetric local algorithm on cycles is provably no better than QAOA at this depth.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The quantum-signal-processing reduction may let researchers bound QAOA performance on other regular graphs by similar polynomial problems.
  • If the Laurent-polynomial view extends to non-cycle instances, it could give parameter-free performance guarantees for QAOA on a wider class of graphs.
  • The approach suggests that analytic tools from signal processing could replace numerical optimization when analyzing QAOA on translation-invariant problems.

Load-bearing premise

The recasting of the QAOA on one qubit in the language of quantum signal processing yields an exact equivalence to finding an optimal pair of Laurent polynomials of degree at most 2p-1.

What would settle it

An explicit calculation of the QAOA expectation value for any small fixed p that yields a cut fraction strictly less than (2p+1)/(2p+2) would falsify the claim.

read the original abstract

We study the performance of symmetric local algorithms finding large cuts on the cycle graph. Such algorithms that cannot see the whole graph at depth p cut at most a (2p+1)/(2p+2) fraction of edges in expectation. We prove that the QAOA achieves this value, a long-standing conjecture of Farhi, Goldstone, and Gutmann. Curiously we do this without finding the optimal parameters. Instead we show it is equivalent to find an optimal pair of Laurent polynomials of degree at most 2p-1. This is made possible by recasting the QAOA on one qubit in the language of quantum signal processing.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proves that QAOA at depth p achieves an expected cut fraction of (2p+1)/(2p+2) on the cycle graph, matching the upper bound previously established for any symmetric local algorithm of depth p. The proof proceeds by recasting the one-qubit QAOA evolution in the language of quantum signal processing, thereby establishing an exact equivalence between the QAOA performance and the maximum of a certain functional over pairs of Laurent polynomials of degree at most 2p-1; the optimal QAOA angles are not computed explicitly.

Significance. If the claimed equivalence holds, the result resolves a long-standing conjecture of Farhi, Goldstone, and Gutmann and demonstrates that QAOA saturates the performance of the entire class of symmetric local algorithms on this family of instances. The QSP-based reduction is a technically interesting technique that may extend to other structured problems.

major comments (2)
  1. [QSP recasting / equivalence argument] The central claim of equivalence (abstract and the QSP recasting section) requires that the map from QAOA angle vectors to Laurent polynomial pairs be surjective onto the full admissible space of degree ≤2p-1. The manuscript shows that QAOA produces polynomials inside this class but does not explicitly verify that every admissible pair is attained by some choice of angles; without this, the QAOA maximum could lie strictly below the polynomial maximum even if the latter reaches (2p+1)/(2p+2).
  2. [Polynomial equivalence claim] The polynomial optimization problem is asserted to attain the value (2p+1)/(2p+2); the manuscript should state explicitly in which section or lemma this attainment is proved (or whether it is taken from prior work) because the QAOA claim rests on it.
minor comments (1)
  1. Notation for the two Laurent polynomials (e.g., their explicit definitions and the functional they optimize) should be introduced with equation numbers in the main text rather than only in the abstract.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying points that require clarification. We address each major comment below and will revise the manuscript accordingly to strengthen the presentation of the equivalence.

read point-by-point responses

  1. Referee: [QSP recasting / equivalence argument] The central claim of equivalence (abstract and the QSP recasting section) requires that the map from QAOA angle vectors to Laurent polynomial pairs be surjective onto the full admissible space of degree ≤2p-1. The manuscript shows that QAOA produces polynomials inside this class but does not explicitly verify that every admissible pair is attained by some choice of angles; without this, the QAOA maximum could lie strictly below the polynomial maximum even if the latter reaches (2p+1)/(2p+2).

    Authors: We agree that explicit verification of surjectivity strengthens the equivalence claim. The QSP recasting section already maps QAOA angles to valid Laurent polynomial pairs of degree at most 2p-1, and the converse direction follows from the standard controllability result in quantum signal processing: any pair of Laurent polynomials satisfying the unitarity condition |P|^2 + |Q|^2 = 1 on the unit circle (with the appropriate parity and degree bound) can be realized by a suitable choice of phase angles. We will add a short paragraph with a reference to this fact from the QSP literature (e.g., the original QSP papers) to make the bijection explicit. revision: yes

  2. Referee: [Polynomial equivalence claim] The polynomial optimization problem is asserted to attain the value (2p+1)/(2p+2); the manuscript should state explicitly in which section or lemma this attainment is proved (or whether it is taken from prior work) because the QAOA claim rests on it.

    Authors: The attainment of (2p+1)/(2p+2) by the Laurent polynomial optimization is proved directly in the manuscript in Lemma 4.1 (Section 4), which constructs an explicit sequence of polynomial pairs that achieve this value and thereby match the known upper bound for symmetric local algorithms. This is not taken from prior work but derived within the paper using the same functional whose maximum is being optimized. We will insert an explicit forward reference to Lemma 4.1 in the abstract, introduction, and the QSP recasting section to make the logical dependence clear. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation reduces to independent polynomial optimization via QSP equivalence

full rationale

The paper establishes a claimed exact equivalence between QAOA performance on the cycle and maximization over Laurent polynomial pairs of degree ≤2p-1 by recasting the one-qubit QAOA in quantum signal processing language. This is presented as a mathematical reduction that avoids explicit parameter optimization, with the performance bound following from the polynomial side. No load-bearing steps reduce by construction to fitted inputs, self-citations, or definitional tautologies; the equivalence is to an external, independently stated polynomial problem. The derivation is therefore self-contained against external benchmarks rather than circular.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on the domain assumption that single-qubit QAOA evolution admits an exact quantum-signal-processing representation that converts the variational problem into Laurent-polynomial optimization.

axioms (1)
  • domain assumption The QAOA on one qubit can be recast exactly in the language of quantum signal processing.
    This equivalence is the enabling step stated in the abstract.

pith-pipeline@v0.9.1-grok · 5621 in / 1100 out tokens · 46343 ms · 2026-06-30T07:18:33.629389+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 9 canonical work pages · 4 internal anchors

  1. [1]

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.A Quantum Approximate Optimization Algorithm. 2014. arXiv:1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  2. [2]

    Santoro.Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes

    Glen Bigan Mbeng, Rosario Fazio, and Giuseppe E. Santoro.Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes. 2019. arXiv: 1906. 08948

    2019

  3. [3]

    Obstacles to Variational Quantum Optimization from Symmetry Protection

    Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. “Obstacles to Variational Quantum Optimization from Symmetry Protection”. In:Physical Review Letters125.26 (2020), p. 260505.doi:10.1103/PhysRevLett.125.260505. arXiv:1910.08980

    work page doi:10.1103/physrevlett.125.260505 2020

  4. [4]

    Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View

    Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. “Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View”. In:Physical Review A97.2 (2018), p. 022304.doi:10.1103/PhysRevA.97.022304. arXiv:1706.02998

    work page doi:10.1103/physreva.97.022304 2018

  5. [5]

    Daniil Rabinovich, Andrey Kardashin, and Soumik Adhikary.On the role of overparametriza- tion in Quantum Approximate Optimization. 2025. arXiv:2508.10086

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  6. [6]

    Optimal Hamiltonian Simulation by Quantum Signal Processing

    Guang Hao Low and Isaac L. Chuang. “Optimal Hamiltonian Simulation by Quantum Signal Processing”. In:Physical Review Letters118.1 (2017), p. 010501.doi: 10.1103/PhysRevLett. 118.010501. arXiv:1606.02685

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett 2017

  7. [7]

    Product Decomposition of Periodic Functions in Quantum Signal Processing

    Jeongwan Haah. “Product Decomposition of Periodic Functions in Quantum Signal Processing”. In:Quantum3 (2019), p. 190.doi:10.22331/q-2019-10-07-190. arXiv:1806.10236

    work page doi:10.22331/q-2019-10-07-190 2019

  8. [8]

    Rui Chao, Dawei Ding, Andr´ as Gily´ en, Cupjin Huang, and Mario Szegedy.Finding Angles for Quantum Signal Processing with Machine Precision. 2020. arXiv:2003.02831

    work page arXiv 2020

  9. [9]

    Stable Factorization for Phase Factors of Quantum Signal Processing

    Lexing Ying. “Stable Factorization for Phase Factors of Quantum Signal Processing”. In: Quantum6 (2022), p. 842.doi:10.22331/q-2022-10-20-842. arXiv:2202.02671

    work page doi:10.22331/q-2022-10-20-842 2022

  10. [10]

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser.Invariant Quantum Algorithms for Insertion into an Ordered List. 1999. arXiv:quant-ph/9901059. 13 A Proof of reduction to one-qubit systems (Claim 3) For convenience, we rederive the result in [4] in detail. We focus on n = 2k. At the end we comment on how oddnchanges the picture. First, let...

    work page internal anchor Pith review Pith/arXiv arXiv 1999

  11. [11]

    14 Altogether, this means ˜HC =−(a 2k +a † 2k)(a1 −a † 1)PX + 2k−1X u=1 (au +a † u)(au+1 −a † u+1) whereP X =Q2k i=1 Xi

    =−(−iZ 1)Y2k 2k−1Y i=1 (−Xi) =−Z 1Z2k 2kY i=1 (−Xi). 14 Altogether, this means ˜HC =−(a 2k +a † 2k)(a1 −a † 1)PX + 2k−1X u=1 (au +a † u)(au+1 −a † u+1) whereP X =Q2k i=1 Xi. We then add a phase factor to unify the expression. Letb j :=a je−iπ·j/(2k). Then (eiπ·j/(2k) bj+e−iπ·j/(2k) b† j)(eiπ·(j+1)/(2k) bj+1−e−iπ·(j+1)/(2k) b† j+1) =e −iπ/2k eiπ(j+1)/k bjb...

  12. [12]

    = (b2k +b † 2k)(eiπ/2kb1 −e −iπ/2kb†

  13. [13]

    pseudospin

    =e −iπ/2k eiπ/kb2kb1 −b 2kb† 1 + h.c. Moreover, the QAOA stays within theP X = 1 subspace, as we start in|+⟩ ⊗2k, andP X commutes withH M andH C. So within this subspace, HM = 2kX j=1 (2b† jbj −1), ˜HC =e −iπ/2k 2kX j=1 eiπ(j+1)/k bjbj+1 −b jb† j+1 +e iπ/2k 2kX j=1 b† jbj+1 −e −iπ(j+1)/k b† jb† j+1 . We now apply a Fourier transform. Letc m = 1√ 2k P2k j=...