Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
The upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability, by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup and demonstrating that the dependence of the authors' algorithms on regularity is in some sense nearly optimal.