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

Abstract Variational quantum algorithms (VQAs) are promising to demonstrate the advantage of 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 (BP) 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 BP 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 a multi-angle relaxation. We conduct systematic experiments to verify our theory. On the one hand, numerical simulations demonstrate that the light-cone VQA achieves better performance over the classical Goemans–Williamson algorithm and the CPLEX solver. On the other hand, we demonstrate on IBM’s quantum devices that the single-round light-cone VQA exceeds the known classical hardness threshold in both 72- and 148-qubit demonstrations, whereas QAOA fails in the 148-qubit one. This work highlights a promising route towards solving classically hard problems on practical quantum devices.