Exponential Quantum Speedup for 3-SAT via Qutrit Amplitude Encoding

We present a quantum algorithm for 3-SAT that achieves query complexity O(1.0607^n), where n is the number of variables. This constitutes an exponential speedup over the best known classical algorithm (O(1.307^n), Hansen et al. 2019) and, remarkably, over all previously known quantum approaches including Grover-accelerated local search (O(1.153^n)).Our approach departs radically from the standard paradigm of applying quantum speedups to classical algorithms. Instead, we encode 3-SAT formulas directly into qutrit (three-level) 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(θ)⊗m · H⊗m (where m = nc is the number of qutrits for c clauses) applied to the encoded formula produces a superposition over satisfying assignments with probability P₁(n) = (15/128) · (8/9)^n. Combined with amplitude amplification, this yields the stated complexity.The key insight is that at the optimal angle θ = 300°, the interference pattern strongly favors absent variables—those not appearing in a clause. Since each 3-SAT clause involves only 3 of n variables, the remaining n-3 absent variables dominate the success probability, yielding a slow decay rate of (8/9)^n.