Three States Per Variable: Interference-Induced Ensemble Witness Extraction for 3-SAT and the Window for Quantum Advantage

Every variable in a 3-SAT clause plays one of three roles—positive, negative, or absent—matching the three basis states of a qutrit. We build on this correspondence: a formula with M clauses on n variables is encoded as a register of nM qutrits, a parameterised unitary circuit is applied, and the resulting qutrit values are measured. Any classical strategy may then be applied to the outcomes; the one we study partitions them into M clause windows, each checked as a candidate satisfying assignment. For product circuits these windows are provably independent, yielding a closed-form success probability. Exhaustive optimisation over all structurally distinct four-variable formulas with up to twelve clauses, reaching 564,954 satisfiable canonical forms at M=12, reveals a window for quantum advantage: the worst-case witness probability stays between 0.39 and 0.48 across the entire tested frontier, even when the hardest formula has a unique satisfying assignment. The hardest instances fall into a small library of combinatorial motifs—non-affine blocks, all-but-one blocks, free-variable factors, and pinned-variable factors—whose structure explains how success probability is distributed across the ensemble. At the largest tested clause counts, the ensemble of windows drives the success probability upward again—the ensemble fights back. We conjecture that this optimised witness probability does not decrease exponentially with the number of clauses.