Efficient solution of the maximum independent set problem by quantum annealing with non-abelian mixing

Quantum annealing, as a prominent algorithm in the field of quantum computing, demonstrates unique advantages in solving combinatorial optimization problems. It operates by encoding the problem into the ground state of a quantum Hamiltonian and driving the system through engineered quantum dynamics to explore the Hilbert space via quantum fluctuations. Owing to the quantum tunneling effect, quantum annealing enables efficient escape from shallow local minima in the Hilbert space, thereby facilitating quantum performance advantages. When implemented in a physical quantum system, quantum annealing naturally avoids the exponential growth in runtime and memory requirements with increasing problem size that plagues classical computation, making it one of the few practical approaches for solving large-scale combinatorial optimization problems. At present, its key implementation bottleneck lies in the design of time-dependent driving dynamics: the choice of a delicate adiabatic path directly determines the success probability of reaching the optimal solution.

In 2020, Biao Wu’s team at Peking University proposed a non-Abelian annealing algorithm for solving the maximum independent set problem [Phys. Rev. A 101, 012318 (2020); Chinese Physics Letters 38, 030304 (2021)]. This algorithm ingeniously designs a slowly rotating quantum adiabatic path and employs non-Abelian mixing in the solution space to search for the maximum independent set, achieving a significantly higher success rate than conventional quantum annealing. In 2022, Lukin’s team at Harvard University experimentally realized a variational quantum annealing algorithm for the maximum independent set problem using a Rydberg atom platform [Science 376, 1209–1215 (2022)].

Recently, the research group led by Biao Wu at the School of Physics, Peking University, in collaboration with Li You’s group at the Department of Physics, Tsinghua University, made an important progress: by comparing the heuristic adiabatic algorithm experimentally employed by Lukin’s group with the non-Abelian annealing algorithm previously proposed by Wu’s team-formulated based on insights into the structure of the system’s Hilbert space, they demonstrated the equivalence of the two approaches under the interaction picture transformation. Furthermore, both numerical simulations and analytical analysis revealed the advantages of the non-Abelian adiabatic paths. The findings were published in the 9th issue of National Science Review (NSR) in 2025 under the title “Quantum Hamiltonian Algorithms for Maximum Independent Sets”. The first author of the paper is Xianjue Zhao, Ph.D. student in the Department of Physics at Peking University, and the corresponding author is Biao Wu, professor in the Department of Physics at Peking University.  Other co-authors include Professor Frank Wilczek of MIT and Nobel Laureate, Professor Li You of Tsinghua University, Peiyun Ge, Ph.D. student at Tsinghua University, and Hongye Yu, Ph.D. student at Stony Brook University.

This work demonstrates that the non-Abelian annealing algorithm for solving the maximum independent set problem can be faithfully implemented using a Rydberg atom Hamiltonian with time-dependent driving terms. Through the interaction picture transformation, the authors derive analytic expressions for the corresponding adiabatic paths. Numerical simulations show that the success probability of the non-Abelian annealing is significantly higher than that of the conventional heuristic adiabatic paths used in experiments, with an average improvement exceeding 50%. Even when variational optimization is applied, the performance gap only narrows to approximately 25%, while requiring an additional 10⁶ measurements due to the variational process. This is because the variational optimization at each small time step tends to achieve only local optima, rather than the global optimum. The genuine quantum advantage emerges from a globally designed and controlled evolution throughout the entire process. On the analytical side, the study considers the impact of random qubit-flip errors introduced during measurement, and shows that the non-Abelian annealing exhibit greater robustness to such perturbations compared to variational methods. Furthermore, by applying a rigorous adiabatic theorem to the effective Hamiltonians induced by the two types of adiabatic paths in the solution subspace, the authors identify that the advantage of the non-Abelian approach originates from the special form of its adiabatic path, which yields a significantly smaller upper bound in the adiabatic condition, thereby enhancing the algorithm's success rate.

---

---