Kavli Affiliate: Frank Wilczek

| First 5 Authors: Hongye Yu, Frank Wilczek, Biao Wu, ,

| Summary:

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 graphs, our quantum algorithm on average

can find an independent set of size very close to $alpha(G)$, which is the

size of the maximum independent set of a given graph $G$. Numerical results

indicate that an $O(n^2)$ time complexity quantum algorithm is sufficient for

finding an independent set of size $(1-epsilon)alpha(G)$. The best classical

approximation algorithm can produce in polynomial time an independent set of

size about half of $alpha(G)$.

| Search Query: ArXiv Query: search_query=au:”Frank Wilczek”&id_list=&start=0&max_results=10