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].
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].
Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachdev–Ye–Kitaev (SYK) model is a representative example of such a system; it is particularly interesting not only due to the existence of efficient quantum algorithms preparing approximations to the ground state such as Hastings–O'Donnell (STOC 2022), but also known no-go results for many classical ansatzes in preparing low-energy states. However, this quantum-classical separation is known to not persist when the SYK model is sufficiently sparsified, i.e., when terms in the model are discarded with probability 1 − p , where p = Θ ( 1 / n 3 ) and n is the system size. This raises the question of how robust the quantum and classical complexities of the SYK model are to sparsification.In this work we initiate the study of the sparse SYK model where p ∈ [ Θ ( 1 / n 3 ) , 1 ] and show there indeed exists a certain robustness of sparsification. We prove that with high probability, Gaussian states achieve only a Θ ( 1 / n ) -factor approximation to the true ground state energy of sparse SYK for all p ≥ Ω ( log n / n 2 ) , and that Gaussian states cannot achieve constant-factor approximations unless p ≤ O ( log 2 n / n 3 ) . Additionally, we prove that the quantum algorithm of Hastings–O'Donnell still achieves a constant-factor approximation to the ground state energy when p ≥ Ω ( log n / n ) . Combined, these show a provable separation between classical algorithms outputting Gaussian states and efficient quantum algorithms for the goal of finding approximate sparse SYK ground states whenever p ≥ Ω ( log n / n ) , extending the analogous p = 1 result of Hastings–O'Donnell.
We consider the optimization problem (ground energy search) for fermionic Hamiltonians with classical interactions. This QMA-hard problem is motivated by the Coulomb electron-electron interaction being diagonal in the position basis, a fundamental fact that underpins electronic-structure Hamiltonians in quantum chemistry and condensed matter. We prove that fermionic Gaussian states achieve an approximation ratio of at least 1/3 for such Hamiltonians, independent of sparsity. This shows that classical interactions are sufficient to prevent the vanishing Gaussian approximation ratio observed in SYK-type models. We also give efficient semi-definite programming algorithms for Gaussian approximations to several families of traceless and positive-semidefinite classically interacting Hamiltonians, with the ability to enforce a fixed particle number. The technical core of our results is the concept of a Gaussian blend, a construction for Gaussian states via mixtures of covariance matrices.
We study the Sachdev-Ye-Kitaev (SYK) Hamiltonian HSYK on n Majorana modes with k-body interactions, and prove that E∥HSYK∥op=(1−o(1))⋅2n/k for super-constant k≤o(n), where the expectation is over the disorder variables in the Hamiltonian. This confirms predictions due to Garcia-Garcia, Jia and Verbaarschot and answers a question posed by Feng, Tian, and Wei. Our results extend to the sparse SYK Hamiltonian. As a corollary, we obtain that a dissipative quantum algorithm due to Basso, Chen, and Dalzell provably computes the ground state energy of the SYK Hamiltonian up to an O(1)-multiplicative factor for all k<n/4.
Our key technical idea is identifying an explicit, deterministic linear operator x such that a fixed quadratic form of x2ℓ exactly equals the expected trace moments of the SYK Hamiltonian for every n and k. This linear operator can be naturally viewed as a twisted model of bosons on the space of hyperedges of a hypergraph. The problem thus reduces to identifying the spectral edge of x, which we show is dominated by the spectrum of a natural (kn)-dimensional matrix from the Johnson scheme and is straightforward to compute using known results. To show that our bound is sharp, we construct a witness state with a large quadratic form on x and transform it into a certificate of a lower bound on the largest quadratic form on HSYK.
Beyond the SYK Hamiltonian, our techniques also apply to the k−local quantum spin glass (QSG), yielding E∥Hk−QSG∥op≤O(n/k) for all 1≤k≤n/2, thus improving the standard O(n) bound by a factor of k.
We give a polynomial-time randomized classical algorithm that approximates the largest eigenvalue λmax of a traceless quartic fermionic Hamiltonian H on n modes. The algorithm achieves energy at least λmax/O(n) and outputs either a fermionic Gaussian state or a polynomially sparse state in the Fock basis. This is achieved through a new upper bound on λmax in terms of the maximum energy of a Gaussian state and 2−nTr(H2).
The fundamental problem in much of physics and quantum chemistry is to optimize a low-degree polynomial in certain anticommuting variables. Being a quantum mechanical problem, in many cases we do not know an efficient classical witness to the optimum, or even to an approximation of the optimum. One prominent exception is when the optimum is described by a so-called “Gaussian state”, also called a free fermion state. In this work we are interested in the complexity of this optimization problem when no good Gaussian state exists. Our primary testbed is the Sachdev–Ye–Kitaev (SYK) model of random degree-q polynomials, a model of great current interest in condensed matter physics and string theory, and one which has remarkable properties from a computational complexity standpoint. Among other results, we give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the q=4 SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue; both algorithms achieve constant-factor approximations with high probability.
The ground state of random Hamiltonians with all-to-all interactions such as the quantum Sherrington-Kirkpatrick (SK) model and the Sachdev-Ye-Kitaev (SYK) model follow volume-law entanglement and are expected to be hard to model using tensor networks. In recent years, some progress has been made to push the limit of classical methods using neural quantum states. However, it remains an open question whether there exist quantum algorithms that could offer a quantum advantage over the state-of-the-art classical methods in simulating random Hamiltonians. In this work, we show that one such algorithm, TETRIS-ADAPT-VQE, can construct accurate ground states for dense and sparse SYK models containing up to N=20 Majorana fermions achieving fidelities ≥99.3% and for the quantum SK model with up to L=18 sites achieving fidelities ≥99.9998%. We find that while the preparation of ground states is efficient (in terms of operator pool size and circuit depth) for the SK model, it is not efficient for either dense or moderately sparse SYK models.