Quantum Algorithms, Quantum Computing News

Light-cone algorithm boosts MaxCut results on quantum computers

Avatar of Ivy Delaney
August 28, 2026 by Ivy Delaney

Researchers Xiaoyang Wang, Yuexin Su, and Tongyang Li detailed a new “light-cone” algorithm designed to improve performance on the MaxCut problem, a challenging optimization task for quantum computers. The work addresses a core limitation of current Variational Quantum Algorithms (VQAs) like QAOA, which currently offer lower performance guarantees than the best classical approaches and struggle during optimization.

The team proves the light-cone VQA achieves an approximation ratio of 0.7926 for the MaxCut problem on 3-regular graphs with a single round, exceeding the performance of a three-round QAOA; multi-angle relaxation further improves this to 0.8333. Experiments on IBM’s quantum devices demonstrate the single-round light-cone VQA surpasses known classical hardness thresholds in both 72- and 148-qubit demonstrations, while QAOA fails on the 148-qubit system.

Light-cone VQA Achieves 0.7926 Approximation Ratio for MaxCut on 3-Regular Graphs

A newly detailed light-cone variational quantum algorithm (VQA) achieves an approximation ratio of 0.7926 for the MaxCut problem on 3-regular graphs. The researchers specifically targeted the barren plateau problem, a known obstacle causing optimization difficulties in VQAs, by strategically selecting an optimal gate sequence. This light-cone VQA improves solution accuracy and circumvents the barren plateau problem, a significant step toward practical quantum advantage; multi-angle relaxation further improves the approximation ratio to 0.8333.

Numerical simulations confirm the algorithm’s superiority over established classical methods like the Goemans-Williamson algorithm and the CPLEX solver, demonstrating enhanced performance in computational tests. The work, originating from RIKEN Center for Interdisciplinary Theoretical and Mathematical Sciences and Peking University, highlights that the findings represent “a promising route towards solving classically hard problems on practical quantum devices.” These results suggest a viable path for leveraging quantum computing to tackle complex optimization challenges currently intractable for even the most powerful conventional computers, potentially unlocking new capabilities in fields reliant on efficient MaxCut solutions.

More like this
Quantum Research NewsQAOA Efficiency Boosted by Cambridge Study
Machine LearningQuantum Computing Optimizes Combinatorial Problems
Quantum Research NewsLinear Ansatz Scales QAO to 100 Qubits
Analog ComputingQuantum Annealing Beats Classical Algorithms
Stay current

See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.

Tags:
QAOA Quantum Computing Riken Variational Quantum Algorithms
Avatar of Ivy Delaney

Ivy Delaney

Ivy Delaney has been working with neural networks and machine learning since the mid-nineties, back when a couple of hidden layers and a long afternoon of training counted as ambitious. She has watched the field go from academic curiosity to the thing quietly running underneath everything, and she brings that long view to quantum computing. For Quantum Zeitgeist she covers the ground where the two fields meet. That means quantum machine learning and the variational algorithms it leans on, and it also means the less glamorous but more interesting story of classical machine learning already doing real work inside quantum machines, decoding error-correcting codes, calibrating noisy hardware and learning the error models that simulators depend on. She writes about the hardware those algorithms have to run on too, and about the post-quantum cryptography scramble that the same hardware has set off. Her stories typically start with the paper, whether that is peer-reviewed work, conference proceedings or an arXiv preprint, with the source linked so you can hold a claim up against the research it came from. She is unimpressed by benchmarks that will not say what they beat, and by demonstrations that only work in the press release.

Latest Posts by Ivy Delaney: