The method improved solutions to a graph-splitting problem while avoiding a training obstacle that affects some quantum algorithms.
The study introduces a light-cone variational quantum algorithm for maximum cut, a problem that asks how to divide the nodes of a network into two groups so that as many connections as possible cross between them. The researchers say the method uses a carefully chosen sequence of quantum gates and avoids barren plateaus, regions where optimization signals can become too weak to guide training.
For three-regular graphs, the researchers prove that one round of the method reaches an approximation ratio of 0.7926 in the worst case. A version with separate parameters for different parts of the circuit reaches 0.8333. Numerical simulations and experiments on IBM quantum devices supported the proposed method's performance, including demonstrations with 72 and 148 qubits.
What the quantum method achieved
The researchers prove that the one-round light-cone method has a worst-case approximation ratio of 0.7926 for maximum cut on three-regular graphs. This is higher than the guarantee for three rounds of the quantum approximate optimization algorithm. Allowing different parameters across the circuit raises the stated guarantee to 0.8333.
In numerical simulations, the light-cone method performed better than the classical Goemans-Williamson algorithm and the CPLEX solver. On IBM quantum devices, a single-round version exceeded the known classical hardness threshold in both the 72- and 148-qubit demonstrations. The quantum approximate optimization algorithm failed to exceed that threshold in the 148-qubit demonstration.
Why the result matters
The results address two difficulties that have limited variational quantum algorithms: weaker performance guarantees than leading classical methods and difficult parameter optimization caused by barren plateaus. Exceeding the stated classical hardness threshold in both hardware demonstrations provides evidence that this circuit design can produce strong results on current quantum devices for this problem.
The work does not show that quantum computers broadly outperform classical computers. Instead, it identifies a circuit design that the researchers say is a promising route for tackling classically hard optimization problems on practical quantum hardware.
Evidence and caveats
The study combines a mathematical guarantee, numerical simulations and demonstrations on IBM quantum devices. The formal guarantee is specifically for the worst case of three-regular graphs, rather than for all maximum cut instances. The abstract does not report the sizes or detailed results of the simulated graph sets, the raw hardware scores, or uncertainty estimates for the device demonstrations.
The hardware comparison is also specific to the tested light-cone method, devices and problem instances. The findings therefore support the method's performance in these experiments but do not establish a general quantum advantage over classical optimization.
// Source
Quantum Science and Technology · 2026 · DOI: 10.1088/2058-9565/ae9b3f
Authors: Xiaoyang Wang, Yang Su, Tongyang Li
Institutions: Peking University
