Optimizing sparse fermionic Hamiltonians

Abstract

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, we prove that strictly $q$-local $\text{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(n^{1/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.

34 pages, 4 figures; v.2 - corrected typos and edited for clarity; improved discussion section

References in corpus (16)

• Quantum Hamiltonian Complexity
• Estimates of moments and tails of Gaussian chaoses
• Complexity of quantum impurity problems
• Sparse Sachdev-Ye-Kitaev model, quantum chaos and gravity duals
• Generalized Hartree-Fock Theory for Interacting Fermions in Lattices: Numerical Methods
• The Power of Noisy Fermionic Quantum Computation
• Product-state Approximations to Quantum Ground States
• The Quantum PCP Conjecture
• A Sparse Model of Quantum Holography
• Approximation algorithms for quantum many-body problems
• Approximation algorithms for QMA-complete problems
• Extremal eigenvalues of local Hamiltonians
• Variational wavefunctions for Sachdev-Ye-Kitaev models
• Improved approximation algorithms for bounded-degree local Hamiltonians
• Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs
• Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians

Cited by in corpus (9)

• Speed limits and locality in many-body quantum dynamics
• Quantum advantage in batteries for Sachdev-Ye-Kitaev interactions
• Sparse random Hamiltonians are quantumly easy
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• Fermionic quantum computation with Cooper pair splitters
• Efficient Representation of Gaussian Fermionic Pure States in Non-Computational Bases
• Explicit Pfaffian Formula for Amplitudes of Fermionic Gaussian Pure States in Arbitrary Pauli Bases
• Optimal Fermionic Joint Measurements for Estimating Non-Commuting Majorana Observables
• Optimizing Sparse SYK