Approximate Solutions of Combinatorial Problems via Quantum Relaxations

Understand

Combinatorial problems are formulated to find optimal designs within a fixed set of constraints.

• They are commonly found across diverse engineering and scientific domains.
• Understanding how to best use quantum computers for combinatorial optimization is to date an open problem.
• Here we propose new methods for producing approximate solutions for the maximum cut problem and its weighted version, which are based on relaxations to local quantum Hamiltonians.