  Ising machines are next-generation computers expected to efficiently sample
near-optimal solutions of combinatorial optimization problems. Combinatorial
optimization problems are modeled as quadratic unconstrained binary
optimization (QUBO) problems to apply an Ising machine. However, current
state-of-the-art Ising machines still often fail to output near-optimal
solutions due to the complicated energy landscape of QUBO problems.
Furthermore, the physical implementation of Ising machines severely restricts
the size of QUBO problems to be input as a result of limited hardware graph
structures. In this study, we take a new approach to these challenges by
injecting auxiliary penalties preserving the optimum, which reduces quadratic
terms in QUBO objective functions. The process simultaneously simplifies the
energy landscape of QUBO problems, allowing the search for near-optimal
solutions, and makes QUBO problems sparser, facilitating encoding into Ising
machines with restriction on the hardware graph structure. We propose
linearization of QUBO problems using variable posets as an outcome of the
approach. By applying the proposed method to synthetic QUBO instances and to
multi-dimensional knapsack problems, we empirically validate the effects on
enhancing minor-embedding of QUBO problems and the performance of Ising
machines.
