Quantum Speedup for 3-SAT via Qutrit Amplitude Encoding: Regime Analysis and Complexity Bounds

We present a quantum algorithm for 3-SAT based on direct qutrit amplitude encoding. For underconstrained formulas (clause-to-variable ratio $c/n ≪ 4.27$), where the number of satisfying assignments scales as $Θ(2^n/poly(n))$, the algorithm achieves query complexity $O(1.0607^n)$—an exponential speedup over classical $O(1.307^n)$ algorithms and quantum Grover-based approaches ($O(1.153^n)$). Our approach encodes 3-SAT formulas into qutrit quantum states, where the ternary alphabet $\{-1, 0, +1\}$ naturally captures the three possible states of a variable in a clause: negative literal, absent, or positive literal. A simple, entanglement-free circuit $U = H^{⊗ m} · R(\theta)^{⊗ m} · H^{⊗ m}$ applied to the encoded formula produces a superposition with success probability decaying as $(8/9)^n$ in the underconstrained regime. Combined with amplitude amplification, this yields the stated complexity. We provide a complete regime analysis showing that the $(8/9)^n$ decay arises from two multiplicative factors: a $(4/9)^n$ contribution from clause-variable interactions, and a factor of $2^n$ from solution counting. Near the satisfiability threshold where solutions are $O(1)$, only the $(4/9)^n$ factor remains, yielding $O(1.5^n)$ complexity. The qutrit encoding thus provides quantum advantage specifically in the solution-rich regime.