  Non-stoquastic Hamiltonians have both positive and negative signs in
off-diagonal elements in their matrix representation in the standard
computational basis and thus cannot be simulated efficiently by the standard
quantum Monte Carlo method due to the sign problem. We describe our analytical
studies of this type of Hamiltonians with infinite-range non-random as well as
random interactions from the perspective of possible enhancement of the
efficiency of quantum annealing or adiabatic quantum computing. It is shown
that multi-body transverse interactions like $XX$ and $XXXXX$ with positive
coefficients appended to a stoquastic transverse-field Ising model render the
Hamiltonian non-stoquastic and reduce a first-order quantum phase transition in
the simple transverse-field case to a second-order transition. This implies
that the efficiency of quantum annealing is exponentially enhanced, because a
first-order transition has an exponentially small energy gap (and therefore
exponentially long computation time) whereas a second-order transition has a
polynomially decaying gap (polynomial computation time). The examples presented
here represent rare instances where strong quantum effects, in the sense that
they cannot be efficiently simulated in the standard quantum Monte Carlo, have
analytically been shown to exponentially enhance the efficiency of quantum
annealing for combinatorial optimization problems.
