Catastrophic failure of quantum annealing owing to non-stoquastic Hamiltonian and its avoidance by decoherence

Abstract Quantum annealing (QA) is a promising method for solving combinatorial optimization problems whose solutions are embedded into a ground state of the Ising Hamiltonian. This method employs two types of Hamiltonians, namely a driver Hamiltonian and a problem Hamiltonian. After a sufficiently slow change from the driver Hamiltonian to the problem Hamiltonian, the target ground state that corresponds to the solution can be obtained. The inclusion of non-stoquastic terms in the driver Hamiltonian is believed to enhance the efficiency of the QA. Meanwhile, decoherence is regarded as one of the main obstacles for QA. This paper presents examples to show that non- stoquastic Hamiltonians can lead to catastrophic failure of QA, whereas a certain decoherence process can be adopted to avoid such failure. More specifically, when anti-ferromagnetic interactions (i.e., typical non-stoquastic terms) are included in the Hamiltonian, the target ground state cannot be prepared even with an infinitely long annealing time for some specific cases. In the example presented herein, owing to a symmetry, the Hamiltonian is block-diagonalized, and a crossing occurs during the QA, which leads to a complete failure of the ground-state search. Moreover, it is shown that adding a certain type of decoherence can yield the ground state after QA for these cases. This is because, even when a symmetry exists in isolated quantum systems, the environment breaks the symmetry. In summary, the counter-intuitive results presented herein provide an insight into the fundamental mechanism of QA.