  Combinatorial optimization is an important application targeted by quantum
computing. However, near-term hardware constraints make quantum algorithms
unlikely to be competitive when compared to high-performing classical
heuristics on large practical problems. One option to achieve advantages with
near-term devices is to use them in combination with classical heuristics. In
particular, we propose using quantum methods to sample from classically
intractable distributions -- which is the most probable approach to attain a
true provable quantum separation in the near-term -- which are used to solve
optimization problems faster. We numerically study this enhancement by an
adaptation of Tabu Search using the Quantum Approximate Optimization Algorithm
(QAOA) as a neighborhood sampler. We show that QAOA provides a flexible tool
for exploration-exploitation in such hybrid settings and can provide evidence
that it can help in solving problems faster by saving many tabu iterations and
achieving better solutions.
