  Quantum computation provides exponential speedup for solving certain
mathematical problems against classical computers. Motivated by current rapid
experimental progress on quantum computing devices, various models of quantum
computation have been investigated to show quantum computational supremacy. At
a commercial side, quantum annealing machine realizes the quantum Ising model
with a transverse field and heuristically solves combinatorial optimization
problems. The computational power of this machine is closely related to
adiabatic quantum computation (AQC) with a restricted type of Hamiltonians,
namely stoquastic Hamiltonians, and has been thought to be relatively less
powerful compared to universal quantum computers. Little is known about
computational quantum speedup nor advantage in AQC with stoquastic
Hamiltonians. Here we characterize computational capability of AQC with
stoquastic Hamiltonians, which we call stoqAQC. We construct a concrete stoqAQC
model, whose lowest energy gap is lower bounded polynomially, and hence the
final state can be obtained in polynomial time. Then we show that it can
simulate universal quantum computation if adaptive single-qubit measurements in
non-standard bases are allowed on the final state. Even if the measurements are
restricted to non-adaptive measurements to respect the robustness of AQC, the
proposed model exhibits quantum computational supremacy; classical simulation
is impossible under complexity theoretical conjectures. Moreover, it is found
that such a stoqAQC model can simulate Shor's algorithm and solve the factoring
problem in polynomial time. We also propose how to overcome the measurement
imperfections via quantum error correction within the stoqAQC model and also an
experimentally feasible verification scheme to test whether or not stoqAQC is
done faithfully.
