  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.
