  Quantum fluctuations driven by non-stoquastic Hamiltonians have been
conjectured to be an important and perhaps essential missing ingredient for
achieving a quantum advantage with adiabatic optimization. We introduce a
transformation that maps every non-stoquastic adiabatic path ending in a
classical Hamiltonian to a corresponding stoquastic adiabatic path by
appropriately adjusting the phase of each matrix entry in the computational
basis. We compare the spectral gaps of these adiabatic paths and find both
theoretically and numerically that the paths based on non-stoquastic
Hamiltonians have generically smaller spectral gaps between the ground and
first excited states, suggesting they are less useful than stoquastic
Hamiltonians for quantum adiabatic optimization. These results apply to any
adiabatic algorithm which interpolates to a final Hamiltonian that is diagonal
in the computational basis.

Quantum Physics