Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
Abstract
The local Hamiltonian problem is the canonical QMA-complete problem, and O(2n) time classical algorithms and O(2n/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(√n) qubits participate in only constantly many constraints, while the remaining O(√n) qubits each participate in O(√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− ε)n) for some ε>0. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.
Related
- Quantum Query Complexity of Maximum Degree and its Generalizations
- Investigation of balance disorders through the clinical Sudden Stop Test: influence of the kinematics and the boundary conditions
- Effect of surface boundary conditions on heat transport and geostrophic balance in simulations of baroclinic waves in confined domains
- Coarse-grained models for loop quantum gravity and their renormalization
- Solutions for neutron stars in General Relativity from a complexity structure scalar boundary condition
BibTeX
@misc{hasegawa2026degree,
title = {{Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT}},
author = {Atsuya Hasegawa and Jonas Kamminga and François Le Gall and Suguru Tamaki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36464},
eprint = {2609.36464},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36464},
}
RIS
TY - UNPB
TI - Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
AU - Atsuya Hasegawa
AU - Jonas Kamminga
AU - François Le Gall
AU - Suguru Tamaki
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36464
UR - https://arxiv.org/abs/2609.36464
AB - The local Hamiltonian problem is the canonical 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(√n) qubits participate in only constantly many constraints, while the remaining O(√n) qubits each participate in O(√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− ε)n) for some ε>0. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.
ER -