We introduce a sum-of-squares SDP hierarchy approximating the ground-state energy from below for quantum many-body problems, with a natural quantum embedding interpretation. We establish the connections between our approach and other variational methods for lower bounds, including the variational embedding, the RDM method in quantum chemistry, and the Anderson bounds. Additionally, inspired by the quantum information theory, we propose efficient strategies for optimizing cluster selection to tighten SDP relaxations while staying within a computational budget. Numerical experiments are presented to demonstrate the effectiveness of our strategy. As a byproduct of our investigation, we find that quantum entanglement has the potential to capture the underlying graph of the many-body Hamiltonian.
Variational methods play an important role in the study of quantum many-body problems, both in the flavor of classical variational principles based on tensor networks as well as of quantum variational principles in near-term quantum computing. This work stresses that for translationally invariant lattice Hamiltonians with periodic boundary conditions, one can easily derive efficiently computable lower bounds to ground state energies that can and should be compared with variational principles providing upper bounds. As small technical results, it is shown that (i) the Anderson bound and a (ii) common hierarchy of semidefinite relaxations both provide approximations with performance guarantees that scale as a constant in the energy density for cubic lattices. (iii) Also, the Anderson bound is systematically improved as a hierarchy of semidefinite relaxations inspired by the quantum marginal problem.
This dissertation concerns the quantum many-body problem, which is the problem of predicting the properties of systems of several quantum particles from the first principles of quantum mechanics. Included under this umbrella are various problems of fundamental importance in quantum chemistry, condensed matter physics, and materials science. Of particular interest is the electronic structure problem, the problem of determining the state of the electrons in a system with fixed atomic nuclei. Since direct numerical solution of the many-body Schrödinger equation is intractable even for systems of moderate size, a diverse array of approximate methods has been developed. The broad goals of this dissertation are to improve the mathematical understanding of certain widely-used approximations, as well as to propose new methods. Roughly speaking, we consider three (overlapping) categories of methods: Green's function methods, embedding methods, and variational methods.One can understand Green's function methods in terms of many-body perturbation theory, which computes series expansions of physical quantities about a non-interacting reference system. These expansions can be expressed graphically in terms of Feynman diagrams, which can in turn be reorganized, in some cases, into an expansion in terms of so-called bold diagrams. Green's function methods can be specified by choosing a subset of bold diagrams to approximate the sum. At the same time, such methods can be understood in terms of an object known as the Luttinger-Ward (LW) functional, which admits a representation in terms of the bold diagrams. Many aspects of these constructions are purely formal, and indeed the existence of the fermionic LW functional as a single-valued functional has recently been called into question. To contribute to the understanding of these issues, we provide rigorous proofs of the combinatorial construction and analytic interpretation of the bold diagrams in the simplified setting of a classical field theory. In this setting we also provide a rigorous non-perturbative construction of the LW functional via convex duality and prove several key properties, including continuity up to the boundary of its domain and asymptotics in the limit of large interaction.Quantum embedding methods, meanwhile, view a large system as being composed of smaller fragments that are treated with high accuracy and embedded in the larger system in a mutually consistent way. Inspired by a connection between the boundary analysis of the LW functional and embedding, we perform similar analysis for the 1-RDM theory for fermionic systems, which is also developed via convex duality, illustrating a relation to fermionic embedding methods such as the density matrix embedding theory (DMET).Another embedding method of note is the dynamical mean-field theory (DMFT), which is at the same time a Green's function method that can be understood in terms of the LW functional. DMFT relies on the solution of impurity problems, which specify the embedding of an interacting system into a non-interacting bath. Underlying DMFT is a result about the sparsity pattern of the self-energy matrix for impurity problems, which to our knowledge has not been proved in the literature. We provide a rigorous proof of this result in various classical and quantum settings. We go on to investigate the fermionic DMFT in depth, identifying the key mathematical structures that appear in the algorithmic loop for solving it and using these to prove the well-posedness of this loop, in a certain sense.Finally, we introduce a suite of new approaches to the quantum many-body problem that provide variational lower bounds to the ground-state energy. These methods, which combine the themes of convexity and embedding, are based on novel convex relaxations of the variational principles for the ground-state energies of many-body systems. To begin, we recover a second-quantized version of the formalism of strictly correlated electrons (SCE), which yields an exact expression for the exchange-correlation functional in Kohn-Sham density functional theory in the limit of infinite Coulomb repulsion in terms of the solution of a multi-marginal optimal transport problem. We introduce a semidefinite relaxation method for approximately solving this problem and obtaining a lower bound for the ground-state energy. The ideas underlying this relaxation are generalized considerably, outside the context of SCE, to yield much tighter lower bounds, which we validate numerically for both quantum spin systems and fermionic systems. We also describe how these relaxation methods can be interpreted as embedding methods via convex duality.
A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.
A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin- 1 / 2 Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way. Published by the American Physical Society 2024
Solving optimization problems is a key task for which quantum computers could possibly provide a speedup over the best known classical algorithms. Particular classes of optimization problems including semidefinite programming (SDP) and linear programming (LP) have wide applicability in many domains of computer science, engineering, mathematics, and physics. Here we focus on semidefinite and linear programs for which the dimensions of the variables involved are exponentially large, so that standard classical SDP and LP solvers are not helpful for such large-scale problems. We propose the QSlack and CSlack methods for estimating their optimal values, respectively, which work by (1) introducing slack variables to transform inequality constraints to equality constraints, (2) transforming a constrained optimization to an unconstrained one via the penalty method, and (3) replacing the optimizations over all possible nonnegative variables by optimizations over parameterized quantum states and parameterized probability distributions. Under the assumption that the SDP and LP inputs are efficiently measurable observables, it follows that all terms in the resulting objective functions are efficiently estimable by either a quantum computer in the SDP case or a quantum or probabilistic computer in the LP case. Furthermore, by making use of SDP and LP duality theory, we prove that these methods provide a theoretical guarantee that, if one could find global optima of the objective functions, then the resulting values sandwich the true optimal values from both above and below. Finally, we showcase the QSlack and CSlack methods on a variety of example optimization problems and discuss details of our implementation, as well as the resulting performance. We find that our implementations of both the primal and dual for these problems approach the ground truth, typically achieving errors of the order 10-2.