Quantum SAT difficulty depends on constraint balance and degree
Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
Computational ComplexityData Structures and Algorithms
Summary
Quantum SAT is a hard problem about finding solutions to quantum systems, and usually takes a very long time to solve. The authors show that if the problem has certain regularity—meaning each quantum bit is involved in about the same number of constraints—then new algorithms can solve it faster. They also prove that if this balance condition is only slightly broken, the problem remains just as hard as before. This work draws a clear line showing when quantum SAT can be solved more quickly and when it cannot.
What this means in practice
- •For quantum algorithm developers: Identify specific quantum SAT problem instances where efficient classical and quantum algorithms can be applied based on constraint regularity.
- •For quantum complexity analysts: Exclude certain quantum SAT problem simplifications by proving hardness under realistic irregular constraint configurations.
A theory result. No direct application yet.
Authors
Atsuya Hasegawa, Jonas Kamminga, François Le Gall, Suguru Tamaki
Abstract
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 the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs. In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints. We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but $O(\sqrt{n})$ qubits participate in only constantly many constraints, while the remaining $O(\sqrt{n})$ qubits each participate in $O(\sqrt{n})$ constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of $n^δ$, for any $δ>0$, our algorithm solves the problem in time $O(2^{(1- \varepsilon)n})$ for some $\varepsilon>0$. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.