Adiabatic condition for quantum annealing revisited

Quantum annealing (QA) is a promising method for solving optimization problems. If the adiabatic condition is satisfied in the QA, the ground state of the problem Hamiltonian can be obtained. The adiabatic condition consists of a transition matrix of time derivative of Hamiltonian and an energy gap (EG) between the ground and excited states. It is supposed that scaling of the EG provides criteria for whether the optimization problem is hard or not. In this presentation, we propose a general framework that gives counter-examples to this criteria: QA with a constant annealing time fails although the EG is constant, i.e., O(L0) during QA, where L is the problem size. The key idea of our analysis is to add a penalty term in the Hamiltonian, which does not change the eigenstate of Hamiltonian but change the eigenvalue. We show a prescription to construct the case where the transition matrix becomes exponentially large with the penalty term. By adding such a penalty term in the adiabatic Grover search, we provide a concrete example, and we analytically show that the transition matrix becomes exponentially large and the magnetization has a discontinuity, i.e., first phase transition occurs despite an EG that scales as O(L0). Moreover, we show that, in this example, the success probability of QA becomes exponentially small as we increase the problem size L. This paper was based on results obtained from a project, JPNP16007, commissioned by the New Energy and Industrial Technology Development Organization (NEDO), Japan.