Abstract: The holy grail of quantum computing is a practical use for today's machines. A popular suggestion is that quantum computers can approximately solve optimization problems better than classical computers, despite little theoretical evidence. I take this claim seriously, analyzing and comparing average-case algorithms on CSPs of large (but fixed) clause density. It turns out that both algorithms and obstructions from spin glass theory naturally transfer to sparse CSPs, culminating in an optimal algorithm among all bounded-fanout quantum and classical circuits of depth up to ε · log n. This talk surveys several recent works, especially BFMVZ21, JMSS22, and CHM23.