Optimizing sparse fermionic Hamiltonians

• Published in: arXiv.org 2023-08
• Main Authors: Herasymenko, Yaroslav, Stroeks, Maarten, Helsen, Jonas, Terhal, Barbara
• Format: Article
• Language: English
• Subjects: Approximation; Fermions; Mathematical analysis
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2211.16518

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 \(\rm {\textit {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.