TY - JOUR
T1 - Quantum Algorithm for Approximating Maximum Independent Sets
AU - Yu, Hongye
AU - Wilczek, Frank
AU - Wu, Biao
N1 - Publisher Copyright:
© 2021 Chinese Physical Society and IOP Publishing Ltd.
PY - 2021/3
Y1 - 2021/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85103664634&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103664634&partnerID=8YFLogxK
U2 - 10.1088/0256-307X/38/3/030304
DO - 10.1088/0256-307X/38/3/030304
M3 - Article
AN - SCOPUS:85103664634
SN - 0256-307X
VL - 38
JO - Chinese Physics Letters
JF - Chinese Physics Letters
IS - 3
M1 - 030304
ER -