Quantum Algorithm for Approximating Maximum Independent Sets

• 作者: Hongye Yu Frank Wilczek Biao Wu
• 来源期刊: 中国物理快报（英文版）
• 年，卷（期）: 2021,（3）
• 所属期刊栏目: GENERAL
• 页码范围: 17-21,中插11-中插17
• 页数: 1页
• 语种: 英文
• DOI: 10.1088/0256-307X/38/3/030304

摘要

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.