TY - JOUR

T1 - Optimizing sparse fermionic Hamiltonians

AU - Herasymenko, Yaroslav

AU - Stroeks, Maarten

AU - Helsen, Jonas

AU - Terhal, Barbara

PY - 2023

Y1 - 2023

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=85169681399&partnerID=8YFLogxK

U2 - 10.22331/q-2023-08-10-1081

DO - 10.22331/q-2023-08-10-1081

M3 - Article

AN - SCOPUS:85169681399

SN - 2521-327X

VL - 7

SP - 1081

JO - QUANTUM

JF - QUANTUM

ER -