Nearly Linear Sample Bounds for Testing Product-State Satisfiability of Dense Quantum -SATResearch Paper
A constraint satisfaction problem asks whether one assignment can meet every local requirement in a large system. Property testing asks a different question: can a small random induced subsystem distinguish a satisfiable instance from one requiring many constraint deletions? The distinction matters when the number of variables is large but the allowed error…