Quantum Dynamics in Rugged Energy Landscapes

We study the ability of quantum dynamics to navigate rugged energy landscapes, for example as exist in many optimization problems in computer science. In particular, we consider the performance of tunneling in "energy-matching" problems, where one solution to an optimization problem is already given and used as a starting point to find others. Clustering in the solution space and the existence of energy barriers make this problem difficult for classical algorithms. Focusing on a specific family of toy models in the presence of a transverse magnetic field, we identify three sharp phases of the quantum dynamics. At small fields, the system cannot tunnel between solutions (and energy matching fails). At intermediate fields, the system does tunnel between solutions (energy matching succeeds). At high fields, the system is excited into states that are not solutions (energy matching fails). We discuss the relation to certain simple classical algorithms.