  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. In this work, we discuss the effects of locality
reduction needed for solvers such as the D-Wave quantum annealer, the Fujitsu
Digital Annealer, or the Toshiba Simulated Bifurcation Machine that can only
accommodate 2-local (quadratic) cost functions. General locality reduction
approaches require the introduction of ancillary variables which cause an
overhead over the native problem. Using a parallel tempering Monte Carlo solver
on Azure Quantum, as well as k-local binary problems with planted solutions, we
show that post reduction to a corresponding 2-local representation the problems
become considerably harder to solve. We further quantify the increase in
computational hardness introduced by the reduction algorithm by measuring the
variation of number of variables, statistics of the coefficient values, and the
entropic family size. Our results demonstrate the importance of avoiding
locality reduction when solving optimization problems.
