Classical algorithm strongly refutes random quantum 3-sat at fixed density
Strong Refutation for Random Quantum 3-SAT at Constant Density
Computational Complexity
Summary
The paper studies a quantum version of a complex puzzle called 3-SAT, which is about figuring out if certain conditions can all be met at once. The authors developed a classical computer algorithm that can confidently say when these quantum puzzles have no solution when they are sufficiently packed with constraints. This result is surprising because the classical version of the puzzle is much harder to rule out quickly at similar levels of complexity. They use a special mathematical tool, semidefinite programming, and exploit unique quantum properties to overcome known barriers.
What this means in practice
- •For quantum cryptography developers: Check security assumptions by efficiently ruling out certain unsatisfiable quantum conditions in cryptographic protocols.
- •For quantum algorithm designers: Use the algorithm to verify no-solution cases efficiently in designing or analyzing quantum algorithms involving complex constraints.
A theory result. No direct application yet.
Authors
Siu On Chan, Jeff Xu
Abstract
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 $Δ\gtrsim 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.