  We consider the problem of finding a near ground state of a $p$-spin model
with Rademacher couplings by means of a low-depth circuit. As a direct
extension of the authors' recent work [Gamarnik, Jagannath, Wein 2020], we
establish that any poly-size $n$-output circuit that produces a spin assignment
with objective value within a certain constant factor of optimality, must have
depth at least $\log n/(2\log\log n)$ as $n$ grows. This is stronger than the
known state of the art bounds of the form $\Omega(\log n/(k(n)\log\log n))$ for
similar combinatorial optimization problems, where $k(n)$ depends on the
optimality value. For example, for the largest clique problem $k(n)$
corresponds to the square of the size of the clique [Rossman 2010]. At the same
time our results are not quite comparable since in our case the circuits are
required to produce a solution itself rather than solving the associated
decision problem. As in our earlier work, the approach is based on the overlap
gap property (OGP) exhibited by random $p$-spin models, but the derivation of
the circuit lower bound relies further on standard facts from Fourier analysis
on the Boolean cube, in particular the Linial-Mansour-Nisan Theorem.
  To the best of our knowledge, this is the first instance when methods from
spin glass theory have ramifications for circuit complexity.
