We consider the optimization problem (ground energy search) for fermionic Hamiltonians with classical interactions. This QMA-hard problem is motivated by the Coulomb electron-electron interaction being diagonal in the position basis, a fundamental fact that underpins electronic-structure Hamiltonians in quantum chemistry and condensed matter. We prove that fermionic Gaussian states achieve an approximation ratio of at least 1/3 for such Hamiltonians, independent of sparsity. This shows that classical interactions are sufficient to prevent the vanishing Gaussian approximation ratio observed in SYK-type models. We also give efficient semi-definite programming algorithms for Gaussian approximations to several families of traceless and positive-semidefinite classically interacting Hamiltonians, with the ability to enforce a fixed particle number. The technical core of our results is the concept of a Gaussian blend, a construction for Gaussian states via mixtures of covariance matrices.
We consider the optimization problem (ground energy search) for fermionic Hamiltonians with classical interactions. This QMA-hard problem is motivated by the Coulomb electron-electron interaction being diagonal in the position basis, a fundamental fact that underpins electronic-structure Hamiltonians in quantum chemistry and condensed matter. We prove that fermionic Gaussian states achieve an approximation ratio of at least 1/3 for such Hamiltonians, independent of sparsity. This shows that classical interactions are sufficient to prevent the vanishing Gaussian approximation ratio observed in SYK-type models. We also give efficient semi-definite programming algorithms for Gaussian approximations to several families of traceless and positive-semidefinite classically interacting Hamiltonians, with the ability to enforce a fixed particle number. The technical core of our results is the concept of a Gaussian blend, a construction for Gaussian states via mixtures of covariance matrices.
We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q -local sparse fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q -local means that each term involves exactly q fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4 -local interactions (sparse SYK- 4 model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O(n−1/2) Gaussian approximation ratio for the normal (dense) SYK- 4 model extends to SYK- q for even q>4 , with an approximation ratio of O(n1/2–q/4) . Our results identify non-sparseness as the prime reason that the SYK- 4 model can fail to have a constant approximation ratio [1, 2].
We give a polynomial-time randomized classical algorithm that approximates the largest eigenvalue λmax of a traceless quartic fermionic Hamiltonian H on n modes. The algorithm achieves energy at least λmax/O(n) and outputs either a fermionic Gaussian state or a polynomially sparse state in the Fock basis. This is achieved through a new upper bound on λmax in terms of the maximum energy of a Gaussian state and 2−nTr(H2).
We discuss classical algorithms for approximating the largest eigenvalue of quantum spin and fermionic Hamiltonians based on semidefinite programming relaxation methods. First, we consider traceless 2-local Hamiltonians H describing a system of n qubits. We give an efficient algorithm that outputs a separable state whose energy is at least λmax/O(log n), where λmax is the maximum eigenvalue of H. We also give a simplified proof of a theorem due to Lieb that establishes the existence of a separable state with energy at least λmax/9. Second, we consider a system of n fermionic modes and traceless Hamiltonians composed of quadratic and quartic fermionic operators. We give an efficient algorithm that outputs a fermionic Gaussian state whose energy is at least λmax/O(n log n). Finally, we show that Gaussian states can vastly outperform Slater determinant states commonly used in the Hartree-Fock method. We give a simple family of Hamiltonians for which Gaussian states and Slater determinants approximate λmax within a fraction 1 − O(n−1) and O(n−1), respectively.
Identifying regimes in which interacting fermionic systems admit efficient classical simulation is a crucial task in quantum many-body physics. In this work, we rigorously establish the Gaussianity and classical simulability of sufficiently weakly interacting fermions. For the Gibbs state of a local interacting fermionic Hamiltonian H=H0+V at any finite temperature and in any spatial dimension, where H0 is quadratic and V is the interaction term, we show that there exists a positive interaction strength below which the Gibbs state is a convex mixture of fermionic Gaussian states. Moreover, based on this structure, we construct a polynomial-time classical sampler for the Gibbs state via Metropolis updates on a tree whose leaves are Gaussian states.
The fundamental problem in much of physics and quantum chemistry is to optimize a low-degree polynomial in certain anticommuting variables. Being a quantum mechanical problem, in many cases we do not know an efficient classical witness to the optimum, or even to an approximation of the optimum. One prominent exception is when the optimum is described by a so-called “Gaussian state”, also called a free fermion state. In this work we are interested in the complexity of this optimization problem when no good Gaussian state exists. Our primary testbed is the Sachdev–Ye–Kitaev (SYK) model of random degree-q polynomials, a model of great current interest in condensed matter physics and string theory, and one which has remarkable properties from a computational complexity standpoint. Among other results, we give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the q=4 SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue; both algorithms achieve constant-factor approximations with high probability.
A recurring principle in many-body physics is that sufficiently distributed interactions or correlations lead to an effectively mean-field description. For fermionic Gaussian states, we establish a quantitative version of this principle directly at the level of Majorana covariance matrices. The main observation is that the admissibility condition for fermionic covariance matrices imposes a quantitative monogamy constraint on two-point correlations: a fixed region has only a bounded covariance budget to distribute among many disjoint regions. We use this principle in three directions. First, for quadratic fermionic Hamiltonians on finite simple graphs of high degree, we obtain product-state approximations to both the ground-state energy and the finite-temperature free energy, with error of order D−1/2 for D-regular graphs. Second, we prove a finite fermionic Gaussian de Finetti theorem: a k-copy Gaussian state that is n-exchangeable under graded fermionic copy permutations is O(k/n)-close in trace norm to the product of its one-copy marginal. In particular, infinite exchangeability within the Gaussian class implies exact product structure. Third, for spatial fermionic Gaussian states with exponentially clustering mutual information, we prove that the conditional mutual information across a separating buffer decays as O(r−1), and hence, by recoverability, the state admits an O(r−1/2) trace-norm approximation by a recovered state. These results show that product and de Finetti approximations and recoverability estimates for fermionic Gaussian systems can all be derived directly from covariance-level structure.