  We provide the first iterative spectral algorithm to find near-optima of a
random quadratic objective over the discrete hypercube. The algorithm is a
randomized Hessian ascent in the solid cube, where we modify the objective by
subtracting a specific instance-independent potential function [Chen et al.,
Communications on Pure and Applied Mathematics, 76(7), 2023]. This extends
Subag's algorithmic program of Hessian ascent from the sphere [Subag,
Communications on Pure and Applied Mathematics, 74(5), 2021] to the more
complex geometry of the cube.
  Utilizing tools from free probability theory, we construct an approximate
projector into the top-eigenspaces of the Hessian with well-behaved diagonal
entries, and use it as the covariance matrix for the random increments. With
high probability, the empirical distribution of the iterates approximates the
solution to the primal version of the Auffinger-Chen SDE [Auffinger et al.,
Communications in Mathematical Physics, 335, 2015]. We then bound the change to
the modified objective function for every iterate via a Taylor expansion whose
derivatives are controlled using various Gaussian concentration bounds and
smoothness properties of (a semiconcave regularization of) the Fenchel-Legendre
dual to the solution of the Parisi PDE.
  These results lay the groundwork for demonstrating the (possible) existence
of low-degree sum-of-squares certificates over high-entropy step distributions
for a relaxed version of the Parisi formula [Open Question 1.8,
arXiv:2401.14383].
