{"id":"arxiv/2602.14379","url":"https://arxiv.org/abs/2602.14379","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions","domain":"quant-ph","source":"arxiv","authors":["Nai-Hui Chia","Atsuya Hasegawa","François Le Gall","Yu-Ching Shen"],"reviews":0,"subject":"quant-ph","summary":"The local Hamiltonian (LH) problem is the canonical $\\mathsf{QMA}$-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2^{(1-\\varepsilon)n})$ for any $\\varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time $O(2^{(1-\\varepsilon)n/2})$ for any $\\varepsilon>0$ under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-02-16","reactions":{}}