Quantum Local Search with the Quantum Alternating Operator Ansatz

Abstract

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ős-Rényi graphs with up to 100 nodes.

13 pages, 8 figures

References in corpus (6)

• A Quantum Approximate Optimization Algorithm
• Warm-starting quantum optimization
• Asymptotic Improvements to Quantum Circuits via Qutrits
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• $N$-body interactions between trapped ion qubits via spin-dependent squeezing
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples

Cited by in corpus (5)

• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Approaches to Constrained Quantum Approximate Optimization
• Incentivising Demand Side Response through Discount Scheduling using Hybrid Quantum Optimization
• Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms