  We propose a novel type of minor-embedding (ME) in simulated-annealing-based
Ising machines. The Ising machines can solve combinatorial optimization
problems. Many combinatorial optimization problems are mapped to find the
ground (lowest-energy) state of the logical Ising model. When connectivity is
restricted on Ising machines, ME is required for mapping from the logical Ising
model to a physical Ising model, which corresponds to a specific Ising machine.
Herein we discuss the guiding principle of ME design to achieve a high
performance in Ising machines. We derive the proposed ME based on a theoretical
argument of statistical mechanics. The performance of the proposed ME is
compared with two existing types of MEs for different benchmarking problems.
Simulated annealing shows that the proposed ME outperforms existing MEs for all
benchmarking problems, especially when the distribution of the degree in a
logical Ising model has a large standard deviation. This study validates the
guiding principle of using statistical mechanics for ME to realize fast and
high-precision solvers for combinatorial optimization problems.
