Abstract
We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph whose vertices are labeled by n-bit strings, and we can view the adiabatic evolution as an efficient O(poly(n))-time quantum algorithm for finding a specific "EXIT'' vertex in the graph given the "ENTRANCE'' vertex. On the other hand we show that if the graph is given via an adjacency-list oracle, there is no classical algorithm that finds the "EXIT'' with probability greater than $\exp(-n^\delta)$ using at most $\exp(n^\delta)$ queries for $\delta= 1/5 - o(1)$. Our construction of the graph is somewhat similar to the "welded-trees'' construction of Childs et al., but uses additional ideas of Hastings for achieving a spectral gap and a short adiabatic path.