  We construct and analyze a message-passing algorithm for random constraint
satisfaction problems (CSPs) at large clause density, generalizing work of El
Alaoui, Montanari, and Sellke for Maximum Cut [arXiv:2111.06813] through a
connection between random CSPs and mean-field Ising spin glasses. For CSPs with
even predicates, the algorithm asymptotically solves a stochastic optimal
control problem dual to an extended Parisi variational principle. This gives an
optimal fraction of satisfied constraints among algorithms obstructed by the
branching overlap gap property of Huang and Sellke [arXiv:2110.07847], notably
including the Quantum Approximate Optimization Algorithm and all quantum
circuits on a bounded-degree architecture of up to $\epsilon \cdot \log n$
depth.
