⚛️ quantum physics

Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

This paper demonstrates that a classical local algorithm, the Variational Iterative Rotation Algorithm (VIRAL), outperforms the Quantum Approximate Optimization Algorithm (QAOA) in establishing new lower bounds for the Max-Cut fraction on large-girth 3-regular graphs, thereby raising the asymptotic lower bound from 0.912 to 0.9127 and challenging the prospects of quantum advantage in this specific domain.

Original authors: Flaviano Morone, Shivang Rawat, Dries Sels

Published 2026-10-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Flaviano Morone, Shivang Rawat, Dries Sels

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

In the vast landscape of computer science, there exists a class of problems so complex that finding the perfect solution for a large system is effectively impossible, even with the most powerful supercomputers. One such challenge is the "maximum cut" problem. Imagine a network of points connected by lines, where every point is linked to exactly three others. The goal is to split these points into two groups so that the number of lines crossing between the groups is as high as possible. While finding the absolute best split is a mathematical nightmare, researchers are deeply interested in how well different methods can perform on these networks, especially when the network is designed to avoid small loops. This specific type of network, known as a large-girth graph, acts as a testing ground for the limits of computation. For decades, the question has been whether quantum computers, which harness the strange laws of physics to process information, can solve these problems significantly better than classical computers, which rely on standard logic and binary switches.

A team of researchers has now challenged the prevailing hope that quantum computers hold a decisive edge in this specific arena. By refining a classical method that uses simple, local rules to make decisions, they have demonstrated that a traditional algorithm can outperform the leading quantum approach on these loop-free networks at specific depths. The study focuses on a specific algorithm called the Variational Iterative Rotation Algorithm, or VIRAL. Unlike quantum methods that attempt to explore many possibilities simultaneously through complex probability waves, VIRAL assigns a direction to each point in the network and then rotates these directions based on the influence of their immediate neighbors. This process happens in layers, with each layer allowing the points to react to their neighbors' new positions. The researchers tested this method on a theoretical model of a network that has no small loops, a condition that forces the algorithm to rely strictly on local information without being confused by distant connections.

The results of this investigation are precise and surprising. The researchers ran their classical algorithm on a theoretical tree structure that represents the local view of any point in these large, loop-free networks. They pushed the algorithm to a depth of thirty-two layers, a significant increase from previous tests. At every even depth tested from p=4 up to p=32, the classical method produced a better result than the Quantum Approximate Optimization Algorithm, or QAOA, which has been the standard for quantum performance on these graphs. Specifically, the classical algorithm guaranteed that it could cut a larger fraction of the connecting lines than the quantum method could, with the gap widening as the complexity of the layers increased. At the deepest level tested, the classical method achieved a success rate of approximately 91.27 percent, a figure that surpasses the previous best guarantee for these types of networks. This finding suggests that for this particular class of problems, the quantum advantage—the idea that quantum computers can do things classical ones cannot—does not exist at these specific depths, at least not in the way it was previously thought to.

The significance of this work lies in what it rules out as much as what it proves. For some time, it was believed that quantum algorithms held a clear lead over classical ones for these specific networks once the complexity reached a certain threshold. The new study explicitly overturns this belief for the case of three-connected networks at even depths up to p=32. The researchers did not merely suggest that the classical method was competitive; they provided rigorous mathematical bounds showing that the classical method is strictly superior at every even depth tested from p=4 onwards. They calculated that the probability of their result being a statistical fluke is less than one in ten million. Furthermore, they showed that this classical approach is not just a theoretical curiosity but a constructive one, meaning it provides a clear, step-by-step recipe that a standard computer can follow to achieve these results in a time that grows linearly with the size of the network.

This discovery reshapes the understanding of where quantum computers might offer an advantage. The study indicates that the complex quantum fluctuations that give quantum computers their power are not always a necessary resource. In this specific scenario, the randomness provided by simple, classical seeds—essentially random starting points for the algorithm—was sufficient to drive the system to a better solution than the quantum method. The researchers found that the classical algorithm's performance continued to improve as they added more layers, closing the gap toward the theoretical maximum possible for these networks. While the exact limit of what a local algorithm can achieve remains unknown, the new data pushes the known lower bound higher than ever before, raising the floor for what is considered possible with classical computing. The work serves as a reminder that in the race for computational supremacy, the most sophisticated tools are not always the most effective, and that sometimes, a well-tuned classical strategy can outmaneuver the most advanced quantum machinery.

Technical Summary: Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

Problem Definition
The paper addresses the problem of determining the maximum fraction of edges, denoted $M_g$ , that can be guaranteed to be cut in any 3-regular graph with girth $g$ (the length of the shortest cycle). The quantity $M_g$ is defined as the infimum of the maximum cut fraction over all 3-regular graphs with girth at least $g$ . While the asymptotic limit $\lim_{g\to\infty} M_g$ is known to lie within a narrow window ( $0.912 \le \lim M_g \le 0.92386$ ), the precise lower bound remains unknown.

A central motivation for this work is the comparison between classical local algorithms and the Quantum Approximate Optimization Algorithm (QAOA). Previous research established that for 3-regular graphs with girth $g \ge 16$ , the depth- $p$ QAOA outperforms the best known classical local algorithms with provable guarantees. This suggested a potential "quantum advantage" for local algorithms at moderate girths. The authors investigate whether this advantage persists when a more powerful classical local algorithm is applied to the same theoretical setting.

Methodology
The authors evaluate the Variational Iterative Rotation Algorithm (VIRAL), a classical local algorithm, on the specific geometric structure relevant to large-girth graphs.

Algorithmic Framework: VIRAL assigns a classical unit vector (spin) to each vertex. Over $p$ layers, these spins are updated synchronously using rotations determined by local fields derived from neighbors' $z$ -components. The update rule is:
$s_i(n+1) = R_x(\beta_n) R_z(\gamma_n h_i(n)) s_i(n)$
where $h_i(n) = \sum_{j \in \partial i} s^z_j(n)$ . The process is initialized with random "seeds" $\epsilon_i \in \{-1, +1\}$ to break symmetry, which is crucial for generating a non-trivial cut on regular graphs. After $p$ layers, spins are thresholded to determine the cut partition.
Local Neighborhood Analysis: The authors leverage the property that on a graph with girth $g \ge 2p+2$ , the radius- $p$ neighborhood of any edge is a finite tree (specifically, two vertices connected by an edge, each rooted to a complete binary tree of depth $p$ ). Because the algorithm is local, the probability that an edge is cut depends only on the random seeds within this tree.
Deriving Bounds: Instead of running VIRAL on finite random graphs (which contain short cycles that invalidate strict lower bounds for $M_g$ ), the authors compute the expected cut fraction, $c_{\text{VIRAL}}(p)$ , directly on this depth- $p$ tree. By the definition of $M_g$ , if a local algorithm achieves an expected cut fraction $c$ on the tree, it guarantees a cut fraction of at least $c$ for any 3-regular graph with girth $g \ge 2p+2$ . Thus, $M_g \ge c_{\text{VIRAL}}(p)$ .
Computation and Statistics: The parameters for VIRAL were pre-trained on random 3-regular graphs (as described in Ref. [15]) and kept fixed. The authors estimated $c_{\text{VIRAL}}(p)$ by sampling $10^7$ independent seed configurations on the tree for every even depth $p$ up to 32. For $p=2$ , the value was computed exactly by enumerating all $2^{14}$ configurations. Statistical lower bounds ( $L$ ) were calculated at a 99.99999% confidence level.

Key Results
The study produces rigorous lower bounds for $M_g$ that surpass previous records:

Superiority over QAOA: For every even depth $p \ge 4$ , the VIRAL tree value $c_{\text{VIRAL}}(p)$ exceeds the corresponding QAOA bounds reported in Ref. [4]. The improvement ranges from 0.005 to 0.011.
Superiority over Classical Vector Algorithms: VIRAL also outperforms the explicit vector algorithm of Thompson, Parekh, and Marwaha (TPM) [8] at all depths $p \ge 4$ .
Extension of Girth Range: The results extend the range of girths for which improved lower bounds are known from $g=36$ (the limit of previous QAOA results) to $g=66$ .
New Asymptotic Lower Bound: At $g=66$ (corresponding to $p=32$ ), the authors obtain a rigorous lower bound of $M_{66} \ge 0.91271$ at a 99.99999% confidence level. This raises the known asymptotic lower bound for $\lim_{g\to\infty} M_g$ from 0.912 to 0.9127.
Convergence Behavior: The increments in performance ( $c_{\text{VIRAL}}(p) - c_{\text{VIRAL}}(p-2)$ ) are still decreasing at $p=32$ , indicating that the limit $p \to \infty$ has not yet been reached, but the algorithm is converging toward the theoretical upper bound of 0.92386.

Significance and Claims
The paper claims that the apparent quantum advantage of the QAOA over classical local algorithms for Max-Cut on 3-regular graphs at moderate girths is an artifact of the specific classical algorithm previously used for comparison. By employing VIRAL, a classical algorithm that utilizes random seeds to mimic the noise inherent in semiclassical approximations of quantum dynamics, the authors demonstrate that classical methods can outperform QAOA at every depth $p \ge 4$ on the relevant tree structures.

The authors conclude that for the specific case of Max-Cut on 3-regular graphs, quantum fluctuations (as utilized by QAOA) do not provide a resource advantage over the classical dynamics driven by random seeds. The "quantum advantage" observed in previous studies disappears when the classical baseline is optimized. The work establishes that the advantage does not exist in this specific regime, though the authors note that whether this holds for higher degrees or $k \ge 3$ (Max- $k$ -Cut) remains an open question. The results are constructive, providing an algorithm that runs in linear time relative to the number of edges to achieve these bounds.

Technical Summary: Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs

More like this