Quantum Algorithm for Approximating Maximum Independent Sets

Hongye Yu, Frank Wilczek, Biao Wu

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Article number030304
JournalChinese Physics Letters
Issue number3
StatePublished - Mar 2021

ASJC Scopus subject areas

  • General Physics and Astronomy


Dive into the research topics of 'Quantum Algorithm for Approximating Maximum Independent Sets'. Together they form a unique fingerprint.

Cite this