Algorithms for Gibbs states of quantum many-body systems

Abstract

We consider the many-body problem in quantum mechanics from a computational perspective. While physical problems like the time-evolution of a quantum system or its ground and thermal states have simple closed-form expressions, these formulas become intractable for multipartite systems. Even for a moderate number of constituents the exponential dimension of the underlying state space does not allow for direct computations. However, the physically interesting problems do not cover the entirety of this exponentially large space. In this thesis, we present a number of new algorithmic approaches for various problems arising in the setting of quantum spin lattices, a mathematical model that closely captures the physics of many condensed matter systems. For these algorithms, we provide convergence guarantees in various restricted settings. Such restrictions are necessary due to hardness results from Hamiltonian complexity. However, in part of this work, we take a step further, presenting algorithms without a priori convergence guarantees, but instead equipped with a posteriori guarantees. This means that, while hardness results can prove that an algorithm has to fail for some instances of a problem, these instances are often highly contrived and useful certified bounds are still possible for many relevant instances of a computationally hard problem. The free energy and local observable problem The first problem we address is the estimation of the free energy given the local interactions in the form of the Hamiltonian terms. The free energy has immediate physical relevance for thermodynamic problems, but also serves as a proxy for the computation of expectation values of local observables in thermal equilibrium. Together with its close relation to ground-state energy problems and thereby combinatorial optimization it has established itself as a benchmark problem in theoretical computer science. We start by addressing the setting of one-dimensional systems. While the ground-state problem is still provably hard, this restriction is sufficient to guarantee efficient algorithms at any constant temperature. We use mathematical tools from the study of the analyticity of the free energy to design novel algorithms that outperform previous asymptotic runtimes. Beyond 1D, using ideas from convex optimization, we design hierarchies of relaxations for observables in thermal states. While quantitative convergence guarantees only apply to restricted settings, we prove a qualitative convergence result in full generality with implications on the decidability of a local observable problem. In the next chapter, we turn our attention to a different, previously proposed hierarchy for the free energy called Markov Entropy Decomposition. We prove a convergence criterion for this hierarchy based on the so-called effective interaction, a quantity that is related to the parent Hamiltonian of marginals of the Gibbs state. The criterion is known to hold in 1D and in limited high temperature settings, but also provides a framework for more general results. In addition, we supplement this convex relaxation with a rounding procedure constructing globally consistent states. By implementing the procedure in terms of quantum gates this allows for efficient preparation of Gibbs states on quantum computers under the same conditions. Hierarchies of convex relaxations are a standard tool that has been extended from the classical setting, where they can be applied to combinatorial optimization problems, to quantum problems like the ground-state energy. In the last chapter of this part, we equip these relaxations with an information-theoretically inspired strengthening: Marginal relaxations need not be compatible with global states and can thereby violate entropy inequalities like the strong subadditivity. Adding these inequalities as a constraint to a hierarchy therefore strengthens it, but also keeps the convex structure of the problem. The technique is very flexible and can be applied to ground state problems, but also other hierarchies such as the ones presented in the preceding chapters. Learning from Hamiltonians In the last part of this thesis, we switch our attention to the problem of learning from measurements of a given quantum Gibbs state. Firstly, we investigate another convex relaxation hierarchy for the learning problem in arbitrary dimensions based on the same formulation as the previous hierarchy for the observable problem. Besides providing a similar a posteriori guarantee of certified bounds on the learned coefficients of the Hamiltonian terms, we also present convergence guarantees in the setting of commuting Hamiltonians. In the final section, we specifically aim at obtaining a tensor network description of Gibbs states in one dimension. This is facilitated by a result of independent interest, the decay of a form of conditional mutual information.