Quantum annealing promises to solve combinatorial optimization problems by preparing the ground state of a target Hamiltonian. Standard annealing protocols are, however, stoquastic and can thus be simulated by sign-problem-free quantum Monte-Carlo methods. To obtain a true quantum advantage, it has been proposed to use non-stoquastic catalyst Hamiltonians. Active only at intermediate stages of the protocol, these can, for certain problems, convert first-order into second-order quantum phase transitions and thus permit an exponential speedup over the stoquastic protocol. At the same time, the non-stoquastic catalyst renders quantum Monte-Carlo methods inefficient. It remains, however, an open question how other classical computation methods are affected by the non-stoquastic terms. We address this question by computing quantum resources -- entanglement entropy and stabilizer Rényi entropy -- whose presence makes classical computations based on tensor networks and stabilizer-tableau methods exponentially hard. We compare these with the spectral gap along the annealing path for two paradigmatic benchmark models, the fully connected
p-spin model and a geometrically local Ising model. While the exact behavior shows a subtle dependency on the underlying model and the annealing path, our numerics suggest consistently that the scaling of entanglement and non-stabilizerness is at least maintained in the deeply non-stoquastic regime and in some cases even significantly enhanced. Our results thus suggest that improvements of quantum performance in non-stoquastic annealing coincide with significant presence of quantum computational resources.
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].