Umesh Vazirani

Statistical mechanics assumes that a quantum many-body system at low temperature can be described by its Gibbs state. However, many complex quantum systems only exist as metastable states of dissipative open system dynamics, which substantially deviate from true thermal equilibrium. Why, then, should the predictions of thermal equilibrium--such as the area law--be so unreasonably effective in explaining low-temperature phenomena? In this work, we model metastable states as approximate stationary states of a quasi-local, (KMS)-detailed-balanced master equation representing Markovian system-bath interaction. We show that all metastable states exhibit universal structures that parallel true quantum Gibbs states: an area law of mutual information and a local Markov property. The more metastable the states are, the larger the regions to which these structural results apply. Behind our structural results lies a systematic framework encompassing sharp equivalences between local minima of free energy, a non-commutative Fisher information, as well as approximate detailed-balance and Kubo-Martin-Schwinger conditions, ultimately building towards a quantitative theory of thermal metastability.

Abstract We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped sparse Hamiltonian with no sign problem. This is in sharp contrast with frustration-free stoquastic Hamiltonians, where no such speedup is possible as shown by Bravyi and Terhal (2008). 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. (2003), but uses additional ideas for simultaneously achieving a spectral gap and a short adiabatic path.