Quantum Annealing on Glued Trees: Tunneling and Noise

We analyze the quantum annealing algorithm for the glued-trees problem [PRL, 109, 050501]. This is an oracle problem which has a provable exponential speedup over the best possible classical algorithm. We show that the quantum dynamics of the quantum anneal admit a tunneling description. We further analyze the effect of an additive random matrix noise model [PRA 71, 032330] on the annealing dynamics. We answer the question: How should the strength of the noise and the anneal-time scale with problem size in order to obtain a sufficiently high probability of success?