Approximation algorithms for quantum many-body problems

Abstract

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 ${\lambda }_{\max }/O(\log n)$, where ${\lambda }_{\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 ${\lambda }_{\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 ${\lambda }_{\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 ${\lambda }_{\max }$ within a fraction $1-O(n^{-1})$ and $O(n^{-1})$ respectively.

17 pages

References in corpus (2)

• Variational Monte Carlo Method Combined with Quantum-Number Projection and Multi-Variable Optimization
• Complexity of quantum impurity problems

Cited by in corpus (16)

• Fermionic Wave Functions from Neural-Network Constrained Hidden States
• Initial state preparation for quantum chemistry on quantum computers
• Quantum Neuronal Sensing of Quantum Many-Body States on a 61-Qubit Programmable Superconducting Processor
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Optimizing sparse fermionic Hamiltonians
• Triply efficient shadow tomography
• Variational wavefunctions for Sachdev-Ye-Kitaev models
• Deterministic Bethe state preparation
• High ground state overlap via quantum embedding methods
• Improved approximation algorithms for bounded-degree local Hamiltonians
• An Improved Approximation Algorithm for Quantum Max-Cut
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators
• Fast semidefinite programming with feedforward neural networks
• Expanding the reach of quantum optimization with fermionic embeddings
• Optimizing Sparse SYK