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 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)$.

References in corpus (1)

• Quantum algorithm of a set of quantum 2-sat problem

Cited by in corpus (7)

• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Escaping Local Minima with Quantum Coherent Cooling
• Lorentz Quantum Computer
• Quantum Hamiltonian Algorithms for Maximum Independent Sets
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Q-CHOP: Quantum constrained Hamiltonian optimization