2018/08/06 by Sergey Bravyi, David Gosset, Robert Koenig +1 · 2 citations
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1063/1.5085428
published as J. Math. Phys. 60, 032203 (2019) · 17 pages
arxiv created 2018/08/06 · arxiv updated 2019/10/08
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. Secondly, 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(nlog 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.