2026-09-10T09:44:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27795 2026-09-09T12:19:39Z ddc:004 open_access

Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs Chen, Antares Huang, Neng Marwaha, Kunal Random CSP message-passing algorithm 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 [Alaoui et al., 2023] through a connection between random CSPs and mean-field Ising spin glasses [Alaoui et al., 2021; Jones et al., 2023]. 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 [Huang and Sellke, 2025], notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to ε ⋅ log n depth [Chou et al., 2022]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antares Chen and Neng Huang and Kunal Marwaha 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.78 urn:nbn:de:0030-drops-277952 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.78 eng https://creativecommons.org/licenses/by/4.0/legalcode