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 algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$ -time quantum circuit acting on $N$ qubits into a $(d+1)$ -local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.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 algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$-time quantum circuit acting on $N$ qubits into a $(d+1)$-local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.

quant-pharXiv:2602.14379Leibniz international proceedings in informaticsFeb 17, 20260 citations

Non-interactive Key Exchange: New Notions, New Constructions, and Forward Security

Suvradip Chakraborty, Dennis Hofheinz, Roman Langrehr

Lecture notes in computer scienceJan 1, 20251 citation

Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM

Jeremy Huang, Young Kun Ko, Chunhao Wang

In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial reduction to the SetDisjointness problem. However, there is an $\tilde{O}(n)$ -time quantum algorithm for 3SUM and a direct application of Grover's algorithm to SetDisjointness queries beats the state-of-the-art classical conditional bound by Kopelowitz, Pettie, and Porat (SODA 2016); this shows that these classical bounds do not apply in the quantum setting. Thus establishing analogous conditional lower bounds in the quantum setting requires applying the quantum 3SUM Conjecture to a \emph{quantum} fine-grained reduction from 3SUM to SetDisjointness. We give the first sub-linear time quantum reductions from 3SUM to online SetDisjointness. Via our reduction, the quantum 3SUM conjecture implies a $p + 2q \geqslant 1$ tradeoff bound for quantum SetDisjointness algorithms with $O(N^p)$ preprocessing time and $O(N^q)$ query time. We also give an analogous reduction from 3XOR. These results are derived from a general framework for fine-grained reductions to SetDisjointness which applies to any Abelian 3-Orthogonal Array (3OA) problem with suitable almost-linear hash functions.In classical fine-grained complexity, the 3SUM Conjecture is used to prove a variety of conditional lower bounds on data structure and graph problems via an initial reduction to the SetDisjointness problem. However, there is an $\tilde{O}(n)$-time quantum algorithm for 3SUM and a direct application of Grover's algorithm to SetDisjointness queries beats the state-of-the-art classical conditional bound by Kopelowitz, Pettie, and Porat (SODA 2016); this shows that these classical bounds do not apply in the quantum setting. Thus establishing analogous conditional lower bounds in the quantum setting requires applying the quantum 3SUM Conjecture to a \emph{quantum} fine-grained reduction from 3SUM to SetDisjointness. We give the first sub-linear time quantum reductions from 3SUM to online SetDisjointness. Via our reduction, the quantum 3SUM conjecture implies a $p + 2q \geqslant 1$ tradeoff bound for quantum SetDisjointness algorithms with $O(N^p)$ preprocessing time and $O(N^q)$ query time. We also give an analogous reduction from 3XOR. These results are derived from a general framework for fine-grained reductions to SetDisjointness which applies to any Abelian 3-Orthogonal Array (3OA) problem with suitable almost-linear hash functions.

cs.CCCross-listedarXiv:2609.40293Oct 1, 20260 citations

On Tightly Secure Non-Interactive Key Exchange

Julia Hesse, Dennis Hofheinz, Lisa Kohl

Lecture notes in computer scienceJan 1, 201830 citations

Fine-grained uncertainty relation and entropic uncertainty relation in the presence of quantum memory

Tanumoy Pramanik, Priyanka Chowdhury

In presence of quantum memory [M. Berta, M. Christandl, R. Colbeck, J.M. Renes, and R. Renner, Nature Phys. 6, 659 (2010)] the lower bound of entropic uncertainty relation depends on amount of entanglement between the particle (on which two incompatible observable are measured) and the quantum memory. On other hand, fine grained uncertainty relation [J. Oppenheim and S. Wehner, Science 330, 1072 (2010)] gives the upper bound of winning non-local (CHSH) game. We construct similar kind of quantum game and relate two uncertainty relation for measurement of any two observable on the quantum system in presence of quantum memory and show there are certain region where the lower bound of entropic uncertainty relation in presents of quantum memory given by Berta et. al. should not be achieve by spin projective measurement.In presence of quantum memory [M. Berta, M. Christandl, R. Colbeck, J.M. Renes, and R. Renner, Nature Phys. 6, 659 (2010)] the lower bound of entropic uncertainty relation depends on amount of entanglement between the particle (on which two incompatible observable are measured) and the quantum memory. On other hand, fine grained uncertainty relation [J. Oppenheim and S. Wehner, Science 330, 1072 (2010)] gives the upper bound of winning non-local (CHSH) game. We construct similar kind of quantum game and relate two uncertainty relation for measurement of any two observable on the quantum system in presence of quantum memory and show there are certain region where the lower bound of entropic uncertainty relation in presents of quantum memory given by Berta et. al. should not be achieve by spin projective measurement.

arXiv:1201.4884Jan 23, 20120 citations

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 algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of

\mathsf{QMA}

problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in

O(\sqrt{2^n})

time for an arbitrary

1/\mathrm{poly}(n)

relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a

T

-time quantum circuit acting on

N

qubits into a

(d+1)

-local Hamiltonian acting on

N+O(T^{1/d})

qubits. This improves the standard construction based on the unary clock, which uses

N+O(T)

qubits.

\tilde{O}(n)

-time quantum algorithm for 3SUM and a direct application of Grover's algorithm to SetDisjointness queries beats the state-of-the-art classical conditional bound by Kopelowitz, Pettie, and Porat (SODA 2016); this shows that these classical bounds do not apply in the quantum setting. Thus establishing analogous conditional lower bounds in the quantum setting requires applying the quantum 3SUM Conjecture to a \emph{quantum} fine-grained reduction from 3SUM to SetDisjointness. We give the first sub-linear time quantum reductions from 3SUM to online SetDisjointness. Via our reduction, the quantum 3SUM conjecture implies a

p + 2q \geqslant 1

tradeoff bound for quantum SetDisjointness algorithms with

O(N^p)

preprocessing time and

O(N^q)

query time. We also give an analogous reduction from 3XOR. These results are derived from a general framework for fine-grained reductions to SetDisjointness which applies to any Abelian 3-Orthogonal Array (3OA) problem with suitable almost-linear hash functions.