Quantum Optimization Heuristics with an Application to Knapsack Problems

Understand

This paper introduces two techniques that make the standard Quantum Approximate Optimization Algorithm (QAOA) more suitable for constrained optimization problems.

• The first technique describes how to use the outcome of a prior greedy classical algorithm to define an initial quantum state and mixing operation to adjust the quantum optimization algorithm to explore the possible answers around this initial greedy solution.
• The second technique is used to nudge the quantum exploration to avoid the local minima around the greedy solutions.
• To analyze the benefits of these two techniques we run the quantum algorithm on known hard instances of the Knapsack Problem using unit depth quantum circuits.