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.
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.
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).
Learning compact, interpretable descriptions of quantum many-body states is an important task in quantum science. We study the task of learning the Slater determinant with maximum fidelity to an arbitrary fermionic many-body state, with motivation from both Hartree-Fock methods and agnostic tomography. Given an n-fermion wavefunction built from m fermionic modes, we provide classical and quantum algorithms returning a Slater determinant with fidelity within ε of maximal in time mpoly(n,1/ε). We prove matching hardness lower bounds, assuming standard complexity conjectures, along some parameter axes. Given access to quantum copies, we prove this can be accomplished with poly(m,n,1/ε) copies of ρ. We also show that above a fidelity of 2/3 any stationary point is the unique global maximum while below 2/3 the optimization landscape can have spurious stationary points, and hence 2/3 marks a transition point in the optimization landscape for this problem. We apply the algorithm to the Fermi-Hubbard model, extracting the closest Slater determinant from neural quantum state solutions. Together, our results provide algorithmic tools with provable guarantees in understanding fermionic many-body systems with classical or quantum simulation.
We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem's approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3- or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).
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].
In this thesis a method for doing approximate calculations of the ground state of quantum mechanical many-body systems is developed and implemented. This method uses the Hartree-Fock method as a starting point and approximates the ground state as a linear combination of non-orthogonal Slater determinants. The Slater determinants are added consecutively by minimising their associated energy while keeping the previously found Slater determinants fixed. This method was tested on a quantum harmonic oscillator filled with interacting fermions and was found to give good approximations to the ground state of this system with only a few Slater determinants. Error estimation of the approximated ground state is done by calculating the energy variance. The energy variance was used in two different methods for improving upon the approximated energy, both of which was found to work well.