We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. The quantum local search algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We compare the performance of this algorithm on 3-regular graphs with up to 100 nodes against the well known classical Boppana-Halld{o}rsson algorithm for the Maximum Independent Set problem.
Download