(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem

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 [Has20]. 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 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 δ ) using at most exp(n δ ) queries for δ = 1 5 -o(1). Our construction of the graph is somewhat similar to the "welded-trees" construction of Childs et al. [CCD + 03], but uses additional ideas of Hastings [Has20] for achieving a spectral gap and a short adiabatic path.