  Quantum annealing is a generic solver for optimization problems that uses
fictitious quantum fluctuation. The most groundbreaking progress in the
research field of quantum annealing is its hardware implementation, i.e., the
so-called quantum annealer, using artificial spins. However, the connectivity
between the artificial spins is sparse and limited on a special network known
as the chimera graph. Several embedding techniques have been proposed, but the
number of logical spins, which represents the optimization problems to be
solved, is drastically reduced. In particular, an optimization problem
including fully or even partly connected spins suffers from low embeddable size
on the chimera graph. In the present study, we propose an alternative approach
to solve a large-scale optimization problem on the chimera graph via a
well-known method in statistical mechanics called the Hubbard-Stratonovich
transformation or its variants. The proposed method can be used to deal with a
fully connected Ising model without embedding on the chimera graph and leads to
nontrivial results of the optimization problem. We tested the proposed method
with a number of partition problems involving solving linear equations and the
traffic flow optimization problem in Sendai and Kyoto cities in Japan.
