arXiv · Oct 4, 2026
Strong Refutation for Random Quantum 3-SAT at Constant Density
By Siu On Chan, Jeff Xu
We give a classical polynomial-time algorithm that strongly refutes random quantum 3-SAT at sufficiently large constant constraint density, thereby disproving the quantum analogue of Feige's random 3-SAT hypothesis. This stands in sharp contrast to classical random 3-SAT, for which polynomial-time strong refutation is known only at constraint density Δ≳ n^(1/2). Although quantum 3-SAT shares the pairwise-independence barrier of its classical counterpart, our SDP-based refutation overcomes this barrier by exploiting the noncommutativity of quantum constraints.