  One of the distinct features of quantum mechanics is that the probability
amplitude can have both positive and negative signs, which has no classical
counterpart as the classical probability must be positive. Consequently, one
possible way to achieve quantum speedup is to explicitly harness this feature.
Unlike a stoquastic Hamiltonian whose ground state has only positive amplitudes
(with respect to the computational basis), a non-stoquastic Hamiltonian can be
eventually stoquastic or properly non-stoquastic when its ground state has both
positive and negative amplitudes. In this paper, we describe that, for some
hard instances which are characterized by the presence of an anti-crossing (AC)
in a transverse-field quantum annealing (QA) algorithm, how to design an
appropriate XX-driver graph (without knowing the prior problem structure) with
an appropriate XX-coupler strength such that the resulting non-stoquastic QA
algorithm is proper-non-stoquastic with two bridged anti-crossings (a
double-AC) where the spectral gap between the first and second level is large
enough such that the system can be operated diabatically in polynomial time.
The speedup is exponential in the original AC-distance, which can be
sub-exponential or exponential in the system size, over the stoquastic QA
algorithm, and possibly the same order of speedup over the state-of-the-art
classical algorithms in optimization. This work is developed based on the novel
characterizations of a modified and generalized parametrization definition of
an anti-crossing in the context of quantum optimization annealing introduced in
[4].
