Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem

arXiv:2504.12896v4 Announce Type: replace 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.

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.

arXiv:2504.12896 [quant-ph]

(or arXiv:2504.12896v4 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2504.12896 Focus to learn more arXiv-issued DOI via DataCite

Quantum Sci. Technol. 11 045028 (2026)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem

Related coverage