Elimination of perturbative crossings in adiabatic quantum optimization

摘要: It was recently shown that, for solving NP-complete problems, adiabatic paths always exist without finite-order perturbative crossings between local and global minima, which could lead to anticrossings with exponentially small energy gaps if present. However, it not whether such a path be found easily. Here, we give simple construction that deterministically eliminates all in polynomial time, space energy, any Ising models final gap. Thus, order quantum optimization require exponential time solve problem, some quality other than this type of anticrossing must unavoidable necessitate long runtimes.