  We analyze the performance of quantum annealing as formulated by Lechner,
Hauke, and Zoller (LHZ), by which a Hamiltonian with all-to-all two-body
interactions is reduced to a corresponding Hamiltonian with local many-body
interactions. Mean-field analyses show that problematic first-order quantum
phase transitions that exist in the original LHZ formulation can be avoided,
and thus an exponential speedup is achieved, if we drive the coefficient of the
many-body term, which represents the constraint, non-linearly as a function of
time. This result applies not only to a simple ferromagnetic model but also to
the spin glass problem if a parameter in the spin glass model is chosen
appropriately.
