Computational Overhead of Locality Reduction in Binary Optimization Problems

Understand

Recently, there has been considerable interest in solving optimization problems by mapping these onto a binary representation, sparked mostly by the use of quantum annealing machines.

• Such binary representation is reminiscent of a discrete physical two-state system, such as the Ising model.
• As such, physics-inspired techniques -- commonly used in fundamental physics studies -- are ideally suited to solve optimization problems in a binary format.
• While binary representations can be often found for paradigmatic optimization problems, these typically result in k-local higher-order unconstrained binary optimization cost functions.