Quantum algorithm for energy matching in hard optimization problems

We consider the ability of local quantum dynamics to solve the energy matching problem: given an instance of a classical optimization problem and a low energy state, find another macroscopically distinct low energy state. Energy matching is difficult in rugged optimization landscapes, as the given state provides little information about the distant topography. Here we show that the introduction of quantum dynamics can provide a speed-up over local classical algorithms in a large class of hard optimization problems. The essential intuition is that tunneling allows the system to explore the optimization landscape while approximately conserving the classical energy, even in the presence of large barriers. In particular, we study energy matching in the random p-spin model of spin glass theory. Using perturbation theory and numerical exact diagonalization, we show that introducing a transverse field leads to three sharp dynamical phases, only one of which solves the matching problem: (1) a small-field trapped phase, in which tunneling is too weak for the system to escape the vicinity of the initial state; (2) a large-field excited phase, in which the field excites the system into high energy states, effectively forgetting the initial low energy; and (3) the intermediate tunneling phase, in which the system succeeds at energy matching. We find that in the tunneling phase, the time required to find distant states scales exponentially with system size but is nevertheless exponentially faster than simple classical Monte Carlo.