Qubit‐Efficient Quantum Local Search for Combinatorial Optimization
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size l$l$ of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit‐efficient variational quantum algorithm that implements a quantum version of local search with only ⌈log2l⌉$\lceil \log _2 l \rceil$ qubits and, therefore, can potentially work with classically intractable neighborhood sizes. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade‐off is crucial for present and near‐term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large‐scale combinatorial optimization problems on near‐term quantum devices.