Quantum Local Search with the Quantum Alternating Operator Ansatz

Understand

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.
• This hybrid algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution.
• We study the performance of this algorithm on 3-regular, Community, and Erd\H{o}s-R\'{e}nyi graphs with up to 100 nodes.