Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs

Antares Chen, Neng Huang, Kunal Marwaha

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 Sell…