Abstract
Variational quantum algorithms (VQAs) are promising to demonstrate the advantage of near-term quantum computing over classical computing in practical applications, such as the maximum cut (MaxCut) problem. However, current VQAs such as the quantum approximate optimization algorithm (QAOA) have lower performance guarantees compared to the best-known classical algorithm, and suffer from hard optimization processes due to the barren plateau problem. We propose a light-cone VQA by choosing an optimal gate sequence of the standard VQAs, which enables a significant improvement in solution accuracy while avoiding the barren plateau problem. Specifically, we prove that the light-cone VQA with one round achieves an approximation ratio of 0.7926 for the MaxCut problem in the worst case of $3$-regular graphs, which is higher than that of the 3-round QAOA, and can be further improved to 0.8333 by an angle-relaxation procedure. Finally, our numerical results indicate an exponential speed-up in finding the exact solution using the light-cone VQA compared with the classical algorithm. Using IBM's quantum devices, we demonstrate that the single-round light-cone VQA exceeds the known classical hardness threshold in both 72- and 148-qubit demonstrations, whereas $p$-round $\text{QAOA}$ with $p=1,2,3$ does not in the latter one. Our work highlights a promising route towards solving classically hard problems on practical quantum devices.
Introduction
In the Noisy Intermediate-Scale Quantum (NISQ) era, identifying practical problems where quantum computers can outperform classical counterparts is a primary goal. The Maximum Cut (MaxCut) problem—dividing a graph's nodes into two sets to maximize the number of edges between them—is a central challenge in combinatorial optimization. While NP-hard, it is a prime candidate for quantum advantage.
Current approaches, most notably the Quantum Approximate Optimization Algorithm (QAOA), face two significant obstacles. First, the barren plateau (BP) problem: as circuits deepen, the optimization landscape flattens, causing gradients to vanish and making parameter tuning nearly impossible. Second, shallow-circuit QAOA often provides theoretical performance guarantees that are inferior to established classical approximation algorithms.
Methods: The Light-Cone VQA
The authors introduce a "light-cone" VQA based on a bipolar-ZY ansatz. This approach deviates from standard VQAs in several critical ways:
- Non-commuting ZY Gates: Unlike the $ZZ$ gates used in QAOA, this method employs $ZY$ gates ($e^{-i\theta Z_i Y_j/2}$). Because $ZY$ gates on adjacent edges do not commute, the circuit maintains a complex "light-cone" structure that cannot be simplified into a basic brick-wall pattern, increasing the difficulty for classical simulation.
- Bipolar Orientation: The gate sequence is organized according to a Directed Acyclic Graph (DAG). By utilizing a "bipolar orientation" (a DAG with exactly one source and one sink), the algorithm maximizes the theoretical lower bound of the solution's accuracy.
- Angle Relaxation: Rather than using a single global angle $\theta$ per round, the parameters are "relaxed." Different angles are assigned based on node degrees, significantly boosting the approximation ratio.
- Barren Plateau Mitigation: The authors prove that because the circuit maintains a finite "local depth" (the number of gates affecting any single qubit remains bounded as system size grows), it is mathematically guaranteed to avoid the barren plateau problem.
Key Results and Hardware Demonstration
The light-cone VQA demonstrates clear theoretical and experimental advantages over standard QAOA.
Theoretical Performance
On 3-regular graphs, a single-round light-cone VQA achieves an approximation ratio of 0.7926, surpassing the performance of a 3-round QAOA (0.7924). When angle relaxation is applied, this ratio increases to 0.8333. These results place the algorithm closer to the Goemans-Williamson classical benchmark (~0.878) than previous quantum methods.
Hardware Milestone
The algorithm was implemented on IBM's Heron R2 processors. On a 148-qubit instance, the light-cone VQA achieved an approximation ratio of 0.965. This is a critical milestone as it exceeds the 0.941 hardness threshold, beyond which the problem is considered exceptionally difficult for classical solvers. In contrast, standard $p$-round QAOA ($p=1,2,3$) failed to reach this threshold on the same hardware due to noise accumulation in deeper circuits.
Scaling Advantage
Numerical simulations suggest a potential exponential scaling advantage. The time-to-solution (TTS) for the light-cone VQA scales as $1.046^N$, outperforming the state-of-the-art classical solver CPLEX, which scales as $1.061^N$.
Conclusion
The light-cone VQA offers a robust path forward for NISQ-era quantum computing by effectively managing the trade-off between circuit depth and optimization feasibility. While it still trails the best-known classical algorithms in absolute guarantee, its ability to avoid barren plateaus and exceed classical hardness thresholds on real hardware marks a significant step toward practical quantum advantage.
Reference: Wang, X., Su, Y., & Li, T. (2025). Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem. arXiv:2504.12896v3 [quant-ph].
Summary updated