Quantum Algorithm for Approximating Maximum Independent Sets

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 α(G) in low polynomial time. The best classical algorithms, by contrast, produce independent sets of size about half of α(G) in polynomial time.