Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Understand

To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization.

• However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming.
• State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution.
• If the potential of quantum computing realizes, it can be expected that in particular finding high-quality solutions for hard problems can be done fast.