Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians

Hidetoshi Nishimori

Published 2016-09-13Version 1

Non-stoquastic Hamiltonians have both positive and negative signs in off-diagonal elements in their matrix representation in the standard basis and thus cannot be simulated efficiently by the standard quantum Monte Carlo method due to the sign problem. We review our analytical studies of this type of Hamiltonians with infinite-range non-random and random interactions from the perspective of possible enhancement of the efficiency of quantum annealing or adiabatic quantum computing. It is shown that non-stoquastic terms, of the type of multi-body transverse interactions like XX and XXX with positive coefficients, appended to the stoquastic Hamiltonian reduce a first-order quantum phase transition in the simple transverse-field Ising model 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 are the first 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.