⚛️ quantum physics

The QAOA on the ring of disagrees

This paper proves that the Quantum Approximate Optimization Algorithm (QAOA) achieves the conjectured performance limit of finding a $(2p+1)/(2p+2)$ fraction of edges in the MaxCut problem on a cycle graph by demonstrating its equivalence to optimizing a pair of Laurent polynomials via quantum signal processing, without requiring the explicit determination of optimal parameters.

Original authors: Kunal Marwaha

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kunal Marwaha

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a puzzle on a giant, circular necklace made of beads. Some beads are "friends" (they want to be the same color), and some are "rivals" (they want to be different colors). This specific puzzle is called the "Ring of Disagrees."

Your goal is to cut the necklace in as many places as possible where two rivals are next to each other. This is known in math as finding a "Max Cut."

The Problem: The Tunnel Vision

The paper studies a specific type of problem-solver called QAOA (Quantum Approximate Optimization Algorithm). Think of QAOA as a very smart, but slightly short-sighted robot.

The Robot's Limitation: The robot can only look at a small neighborhood around each cut. It cannot see the whole necklace at once. If the necklace is huge, the robot only sees a tiny segment, like looking through a straw.
The "Depth" (p): The number of steps the robot takes to look around is called its "depth" ( $p$ ). The deeper it looks, the more of the neighborhood it sees.
The Old Mystery: For 12 years, scientists guessed that no matter how smart this robot is, if it can't see the whole necklace, it will always miss a tiny fraction of the perfect cuts. They had a formula for this limit: it can only cut about $\frac{2p+1}{2p+2}$ of the rival pairs. But nobody could prove it was the absolute best possible.

The Breakthrough: A New Language

The author, Kunal Marwaha, finally proved this 12-year-old guess is correct. But he didn't do it by brute-forcing the robot's settings. Instead, he translated the robot's behavior into a completely different language: Quantum Signal Processing.

Here is the creative analogy for how he did it:

Breaking the Necklace: Instead of looking at the giant ring, the author realized the robot's behavior on the ring is mathematically identical to running the same robot on many tiny, independent single-qubit systems (think of these as tiny, one-bead puzzles).
The Polynomial Translator: The author showed that choosing the robot's settings (angles) is exactly the same as choosing a pair of special mathematical curves called Laurent polynomials.
- Analogy: Imagine you are trying to tune a radio to get the clearest signal. Instead of twisting the dial randomly, you realize that every possible dial setting corresponds to a specific shape of a wave. The author proved that finding the best dial setting is just finding the best wave shape.
The "Invisible" Limit: When the robot is too short-sighted (depth $p$ is small compared to the ring size), the math shows that the "wave" it creates has a fundamental limit. It's like trying to fill a bucket with a leaky cup; no matter how fast you pour, you can never fill it completely. The math proves the "leak" is exactly $\frac{1}{2p+2}$ of the total capacity.

The Results: Two Scenarios

The paper proves two main things depending on how big the ring is compared to the robot's vision:

Scenario A: The Ring is Huge (The Robot is Short-Sighted)

Condition: The ring is so big that the robot's view ( $p$ ) doesn't reach all the way around.
Result: The robot achieves exactly the limit everyone guessed: it cuts $\frac{2p+1}{2p+2}$ of the rival pairs.
The Catch: The author proved this is the best possible performance for any symmetric, local algorithm. However, the paper admits that while we know what the perfect settings are (in terms of those wave shapes), we don't have a simple recipe to write down the exact dial settings (angles) to achieve it. It's like knowing the perfect song exists, but not having the sheet music written out in simple notes.

Scenario B: The Ring is Small (The Robot Sees Everything)

Condition: The ring is small enough that the robot's view covers the whole thing.
Result: The robot finds the perfect cut every time.
- If the ring has an even number of beads, it cuts 100% of the rivals.
- If the ring has an odd number of beads, it cuts all but one (which is the mathematical maximum for an odd ring).
The Good News: In this case, the author did find a simple recipe for the dial settings to get this perfect result.

Why This Matters (According to the Paper)

It's a Proof, Not a New Tool: The paper doesn't invent a new algorithm; it proves that the existing QAOA algorithm is as good as it can possibly be for this specific type of problem.
No Classical Match: Surprisingly, the paper notes that no known classical (non-quantum) algorithm in this same "short-sighted" family can match the QAOA's performance. The quantum robot is beating the classical robots at their own game.
The "Black Box" of Angles: Even though the author proved the optimal settings exist, he couldn't write them down in a simple formula. They are hidden inside the roots of complex mathematical curves (Chebyshev polynomials).

A Note on the Author's Process

The author openly states that he used Artificial Intelligence (specifically ChatGPT 5.5 Pro) extensively to help discover the connection to Quantum Signal Processing, find the optimal polynomial shapes, and even draft parts of the proofs. He acted as the editor and verifier, polishing the AI's output and writing the final paper himself. He also mentions that another group independently proved the same result using computer code verification.

In summary: The paper solves a 12-year-old mystery by translating a quantum algorithm into the language of wave shapes. It proves that when the algorithm is too short-sighted to see the whole picture, it hits a hard ceiling on how well it can perform, and it hits that ceiling exactly as predicted.

Technical Summary: The QAOA on the Ring of Disagrees

Problem Statement
This paper investigates the performance of the Quantum Approximate Optimization Algorithm (QAOA) applied to the "ring of disagrees" problem, which corresponds to finding large cuts on a cycle graph $C_n$ with $n \ge 3$ vertices. The study focuses on symmetric local algorithms, defined as circuits that commute with global bit-flipping and make decisions based solely on local neighborhoods of depth $p$ .

A long-standing conjecture by Farhi et al. [1] posited that when the QAOA depth $p$ is insufficient to "see" the entire graph (specifically when $n \ge 2p + 2$ ), the algorithm achieves an expected cut size of $n \cdot \frac{2p+1}{2p+2}$ . Conversely, when the graph is small enough to be fully observed ( $n < 2p + 2$ ), the algorithm should find the maximum possible cut (size $n$ for even $n$ , $n-1$ for odd $n$ ). While supported by numerical evidence for over a decade, this conjecture remained unproven.

Methodology
The authors prove the conjecture by recasting the QAOA on the cycle graph into the language of Quantum Signal Processing (QSP). The proof proceeds through three main stages:

Reduction to Single-Qubit Systems:
Leveraging a free fermionic picture established in prior work [4], the authors demonstrate that running the QAOA on a cycle $C_{2k}$ is equivalent to simultaneously running the QAOA on $k$ independent single-qubit systems. Each system $j$ operates with a cost Hamiltonian $h_c(\theta_j) = X \cos \theta_j + Z \sin \theta_j$ , where $\theta_j = \pi \frac{2j-1}{2k}$ . The angles for the single-qubit systems are related to the global QAOA angles by a factor of two and sign changes.
Expressibility via Laurent Polynomials:
The authors analyze the single-qubit QAOA using QSP techniques. They establish an Expressibility Theorem (Theorem 6), showing that the performance of a depth- $p$ QAOA on a single qubit is fully characterized by a pair of real Laurent polynomials $(A, B)$ of degree at most $2p-1$ . These polynomials must satisfy specific normalization and parity constraints (belonging to the set $S_{2p-1}$ ).
Crucially, this reformulation allows the optimization problem to shift from searching over continuous angle parameters $(\vec{\gamma}, \vec{\beta})$ to searching for optimal polynomial pairs. The performance metric is expressed as a function of these polynomials evaluated at specific points $z_j = e^{i\theta_j/2}$ .
Optimization and Bounds:
- Case 1: $n \ge 2p + 2$ (Cannot see the whole graph): The performance ratio simplifies to $1 - \sum |c_m|^2$ , where $c_m$ are coefficients of the amplitude polynomial $F(z)$ . Using the Cauchy-Schwarz inequality, the authors derive an upper bound of $\frac{2p+1}{2p+2}$ . They then construct a specific polynomial pair (related to Chebyshev polynomials of the second kind) that saturates this bound, proving the QAOA achieves this value.
- Case 2: $n < 2p + 2$ (Can see the whole graph):
  - For even $n$ , the authors construct a polynomial pair where the error term vanishes exactly at the required points, proving the QAOA finds the perfect cut. They provide an explicit closed-form solution for the optimal angles in this regime.
  - For odd $n$ , a similar reduction to single-qubit systems exists with slightly different angles. The authors prove the existence of a polynomial pair that optimizes all subsystems simultaneously, achieving the maximum cut size $n-1$ , though they do not find a simple closed form for the angles.

Key Results
The paper establishes two primary theorems:

Theorem 1: When $n \ge 2p + 2$ , the maximum expected cut fraction achieved by the depth- $p$ QAOA is exactly $\frac{2p+1}{2p+2}$ . This confirms the conjecture that symmetric local algorithms cannot exceed this limit.
Theorem 2: When $n < 2p + 2$ , the QAOA achieves the maximum possible cut size: $1$ (fraction of edges) if $n$ is even, and $\frac{n-1}{n}$ if $n$ is odd.

Significance and Claims
The authors claim to finally resolve a 12-year-old conjecture regarding the performance limits of QAOA on cycle graphs. The significance of the work lies in:

Proof of Optimality: Demonstrating that QAOA achieves the theoretical maximum for symmetric local algorithms on this specific problem class.
Methodological Shift: Introducing the language of Quantum Signal Processing and Laurent polynomials to analyze QAOA, a technique not previously applied to this problem. This allows for the derivation of exact performance bounds without needing to explicitly solve for optimal angles in the general case.
Surprising Gap: The authors note a curious finding: while they prove the existence of optimal parameters for QAOA, no known classical symmetric local algorithm matches this performance.
Independence: The authors acknowledge that a separate group independently proved Theorem 1 using the Lean proof assistant, highlighting the robustness of the result.

The paper concludes modestly, noting that while the existence of optimal angles is proven, explicit closed-form expressions for these angles (beyond the even $n$ case) remain elusive and are likely related to the roots of Chebyshev polynomials. The work was completed with significant assistance from contemporary AI systems for concept exploration and proof discovery, though the final text and verification were performed by the human author.