Thuy-Duong Vuong

Despite extensive study, our understanding of quantum Markov chains remains far less complete than that of their classical counterparts. [Temme'13] observed that the Davies Lindbladian, a well-studied model of quantum Markov dynamics, contains an embedded classical Markov generator, raising the natural question of how the convergence properties of the quantum and classical dynamics compare. While [Temme'13] showed that the spectral gap of the Davies Lindbladian can be exponentially smaller than that of the embedded classical generator for certain highly structured Hamiltonians, we show that if the spectrum of the Hamiltonian does not contain long arithmetic progressions, then the two spectral gaps must be comparable. As a consequence, we prove that for a large class of Hamiltonians, including those obtained by perturbing a fixed Hamiltonian with a generic external field, the quantum spectral gap remains within a constant factor of the classical spectral gap. Our result aligns with physical intuition and enables the application of classical Markov chain techniques to the quantum setting. The proof is based on showing that any ``off-diagonal'' eigenvector of the Davies generator can be used to construct an observable which commutes with the Hamiltonian and has a Lindbladian Rayleigh quotient which is comparably small. Thus, a spectral gap for such observables implies a spectral gap for the full Davies generator.

We study the problem of approximating the partition function of the transverse-field Ising model (TFIM), a widely studied quantum many-body model with important applications in quantum simulation and quantum annealing. Despite its fundamental importance, the algorithmic landscape for computing the TFIM partition function has remained poorly understood beyond restricted parameter regimes. We provide a precise characterization of the temperature regimes in which efficient approximation is possible, establishing a sharp computational phase transition. Let $J$ denote the symmetric interaction matrix and $\Delta(J) = \lambda_{\max}(J)-\lambda_{\min}(J)$ be its spectral width. We show that for all inverse temperatures $\beta \in [0,1/\Delta(J)]$, there exists an efficient classical randomized algorithm that approximates the partition function $\tr(e^{-\beta H})$ to within an arbitrarily small multiplicative factor. We apply the standard Trotter decomposition to map the quantum model to a classical spin system, then leverage new techniques in Markov chain analysis to show an efficient algorithm that samples from and computes the partition function of the resulting distribution. This temperature threshold is tight: for $\beta > 1/\Delta(J)$, we show that approximating the partition function is NP-hard and thus is unlikely to admit an efficient classical or quantum algorithm.