Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT

Atsuya Hasegawa, Jonas Kamminga, François Le Gall +1

The local Hamiltonian problem is the canonical $\mathsf{QMA}$-complete problem, and $O(2^n)$ time classical algorithms and $O(2^{n/2})$ time quantum algorithms are known to solve t…