Computational Complexity and Quantum Gibbs Sampling for Local Hamiltonians

One of the primary motivations for building quantum computers is to simulate quantum many-body systems. While significant progress has been made in simulating quantum dynamics, much less is known about simulating ground states and Gibbs states, an essential task for understanding the static properties of quantum many-body systems. From a computer science perspective, problems on ground states and Gibbs states are quantum analogues of the Boolean satisfiability problem (SAT) and classical Gibbs sampling, which have wide applications in optimization, machine learning, and computational complexity. This thesis leverages tools from computer science to explore the potential quantum advantage in simulating ground states and Gibbs states, through two complementary approaches: designing new quantum algorithms and evaluating the extent to which classical algorithms remain effective. In particular, Quantum Gibbs sampling. In the first part, we describe our progress in developing quantum algorithms for preparing quantum Gibbs states. For general Hamiltonians, we develop a quantum analogue of the Metropolis-Hastings algorithm that is both conceptually simple and provably correct, with the Gibbs state as its approximate unique fixed point. Note that generalizing the Metropolis-Hasting algorithm to the quantum setting is non-trivial due to the unclonability of quantum states. Additionally, for a broad class of commuting Hamiltonians, we propose a different approach which constructs efficient quantum Gibbs samplers by leveraging reductions to existing classical sampling algorithms. Sharpening the understanding of classical algorithms. In the second part, we present new complexity results to deepen our understanding of the capabilities of classical algorithms for ground energy estimation. The potential quantum advantage in solving many-body systems stems from the sign problem in general Hamiltonians, which classical algorithms struggle to handle. We give rigorous evidence to show that under certain conditions, widely used classical methods, such as fixed-node Monte Carlo and tensor network contraction, may overcome this barrier and effectively resolve the sign problem.