Quantum Algorithm for Approximating Maximum Independent Sets
Hongye Yu1, Frank Wilczek2,3,4,5,6, and Biao Wu7,4,8*
1Department of Physics and Astronomy, Stony Brook University, Stony Brook, NY 11794, USA 2Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA 3D. Lee Institute, Shanghai Jiao Tong University, Shanghai 200240, China 4Wilczek Quantum Center, School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240, China 5Department of Physics, Stockholm University, Stockholm SE-106 91, Sweden 6Department of Physics and Origins Project, Arizona State University, Tempe AZ 25287, USA 7International Center for Quantum Materials, School of Physics, Peking University, Beijing 100871, China 8Collaborative Innovation Center of Quantum Matter, Beijing 100871, China
Abstract：We present a quantum algorithm for approximating maximum independent sets of a graph based on quantum non-Abelian adiabatic mixing in the sub-Hilbert space of degenerate ground states, which generates quantum annealing in a secondary Hamiltonian. For both sparse and dense random graphs $G$, numerical simulation suggests that our algorithm on average finds an independent set of size close to the maximum size $\alpha(G)$ in low polynomial time. The best classical algorithms, by contrast, produce independent sets of size about half of $\alpha(G)$ in polynomial time.
2021, Vol. 38 
