  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. This strengthens the superpolynomial separation recently
proved by Hastings. The Hamiltonian that exhibits this speed-up comes from the
adjacency matrix of an undirected graph, and we can view the adiabatic
evolution as an efficient $\mathcal{O}(\mathrm{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= \frac15 - 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.
