⚛️ quantum physics

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

This paper establishes strong fine-grained complexity lower bounds for the local Hamiltonian problem and quantum partition function approximation under SETH and QSETH by introducing a novel size-preserving circuit-to-Hamiltonian construction, while simultaneously presenting a matching quantum algorithm that improves the state-of-the-art for low-temperature regimes.

Original authors: Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Unsolvable" Puzzle

Imagine you have a massive, incredibly complex puzzle. In the world of quantum physics, this puzzle is called the Local Hamiltonian (LH) problem. It's like trying to find the absolute lowest point in a mountain range made of billions of peaks and valleys. Finding this "lowest point" (the ground state energy) tells us how a quantum system behaves, but it is notoriously difficult.

For decades, scientists have known that solving this puzzle is hard. They have algorithms (recipes) to solve it, but these recipes take a very long time—so long that if you added just one more piece to the puzzle, the time required would double. This is called an exponential time cost.

The big question this paper asks is: "Is there a secret shortcut? Can we build a faster recipe that doesn't double the time every time we add a piece?"

The authors say: "No. Not unless we break the fundamental laws of computing."

They prove that the current slow recipes are actually the best we can possibly do. If you could solve this puzzle significantly faster, you would also be able to solve other famous "impossible" logic puzzles (like the SAT problem) instantly, which most computer scientists believe is impossible.

The Core Innovation: The "Smart Clock"

To prove this, the authors had to build a bridge between two different worlds:

The Logic World: Where we check if a math problem has a solution (like a Sudoku).
The Physics World: Where we calculate the energy of a quantum system.

Usually, to build this bridge, scientists use a "Clock" to keep track of the steps a computer takes.

The Old Clock (Unary): Imagine a clock that counts to 1,000 by laying out 1,000 light switches in a row. To get to step 500, you have to flip 500 switches. This is slow and takes up a lot of space (qubits).
The New Clock (Compressed): The authors invented a Smart Clock. Instead of laying out 1,000 switches, they use a clever arrangement of just a few switches that can represent 1,000 steps. It's like using a digital watch instead of a row of light bulbs.

Why does this matter?
Because the "size" of the clock matters. If the clock is too big, the proof falls apart. By shrinking the clock, they proved that even with a tiny, efficient system, the problem remains just as hard as the hardest logic puzzles. This is the "Size-Preserving Circuit-to-Hamiltonian Construction" mentioned in the title. It's like proving that even if you shrink a factory down to the size of a shoebox, it still takes the same amount of time to build a car.

The Two Main Results

1. The "Speed Limit" for Quantum Physics

The authors proved that for a specific type of quantum puzzle (3-local Hamiltonian), there is a hard speed limit.

Classical Computers: You cannot solve it faster than roughly $2^n$ (where $n$ is the number of pieces).
Quantum Computers: You cannot solve it faster than roughly $2^{n/2}$ .

The Analogy: Imagine trying to find a specific grain of sand on a beach.

A classical computer is like a person walking the beach, checking every grain.
A quantum computer is like a super-powered scanner that can check two grains at once (Grover's search).
The authors proved that even with the super-powered scanner, you can't do it much faster than checking half the beach. There is no "teleportation" shortcut.

2. The "Temperature" Problem (Quantum Partition Function)

There is a related, even harder problem called the Quantum Partition Function (QPF). This isn't just about finding the lowest point; it's about counting all the possible states of the system, weighted by how hot or cold the system is.

The Old Way: Previous algorithms were like trying to count every guest at a massive party. If the party was "cold" (low temperature), the counting became incredibly slow and inefficient.
The New Way: The authors built a new algorithm that is as fast as theoretically possible ( $O(2^{n/2})$ $O (2^{n /2})$ ).
- The Metaphor: Imagine you need to count the number of people in a stadium. Instead of asking every single person (slow), you use a quantum trick to sample the crowd in a way that gives you the exact number almost instantly, regardless of how "cold" or "hot" the crowd is behaving.

Why Should You Care?

This paper is a "reality check" for the future of quantum computing.

It manages expectations: It tells us that we shouldn't waste time looking for a magic algorithm that solves these physics problems instantly. The current "slow" algorithms are likely the best we will ever get.
It sets the bar: By proving these limits, it helps scientists know where to focus their energy. If we can't make the algorithm faster, maybe we should focus on building better hardware or finding new types of problems that don't have these limits.
It connects the dots: It shows that the difficulty of solving quantum physics problems is deeply tied to the difficulty of solving basic logic puzzles. If you could crack one, you would crack the other.

Summary in One Sentence

The authors built a tiny, efficient "quantum clock" to prove that solving certain complex physics puzzles is fundamentally hard, meaning our current slow methods are actually the fastest possible, and they also created a new, ultra-fast method to count quantum states that matches this theoretical speed limit.

1. Problem Statement

The paper addresses the computational hardness of two fundamental problems in quantum complexity theory:

The Local Hamiltonian (LH) Problem: Estimating the ground-state energy of a $k$ -local Hamiltonian. This is the canonical QMA-complete problem.
The Quantum Partition Function (QPF) Problem: Approximating the partition function $Z = \text{tr}(e^{-\beta H})$ of a quantum system with a relative error. This problem is known to be equivalent to approximately counting the number of witnesses accepted by a QMA verifier.

The Core Question: Do there exist classical or quantum algorithms that significantly improve upon the current best-known running times?

Current Classical Bounds: $O^*(2^n)$ for LH.
Current Quantum Bounds: $O^*(2^{n/2})$ for LH (via Grover search) and $O^*(2^{n/2})$ for QPF in high-temperature regimes, but potentially slower in low-temperature regimes.
Hypotheses: The authors aim to prove that these running times are essentially optimal under the Strong Exponential Time Hypothesis (SETH) for classical algorithms and the Quantum Strong Exponential Time Hypothesis (QSETH) for quantum algorithms.

The Barrier: Standard reductions from $k$ -SAT to Local Hamiltonian (via circuit-to-Hamiltonian constructions) typically introduce a "size overhead."

Unary Clock: Uses $O(T)$ qubits for a circuit of $T$ gates, leading to a Hamiltonian on $N+O(T)$ qubits. This breaks fine-grained reductions because $T$ can be large.
Binary Clock: Reduces qubits to $O(\log T)$ but increases locality to $O(\log T)$ , failing to prove hardness for fixed locality (e.g., 3-local).
Goal: A reduction that is both size-preserving (qubits $= N + o(N)$ ) and locality-independent (fixed constant locality, e.g., 3-local).

2. Methodology and Key Techniques

A. Size-Preserving Circuit-to-Hamiltonian Construction

The authors introduce the first construction that simultaneously achieves constant locality and size preservation.

Novel Clock State: They combine two existing clock constructions:
1. $(n, d)$ -clock (from [CCH+23]): Based on a Johnson graph, allowing time evolution with $d$ -local operations but encoding time in a subspace of dimension $\binom{n}{d}$ .
2. Unary Clock: Standard unary encoding.
Hybrid Mechanism: They construct a clock using two registers of size $a$ $a$ (where $T \approx \binom{a}{d-1} \cdot a$ $T \approx (d - 1 a) \cdot a$ ).
- The first register uses the $(a, d-1)$ -clock structure.
- The second register uses a unary clock that moves periodically (0 to $a$ and back).
- This periodic movement allows the system to increment/decrement time using $d$ -local operators on the first register and 1-local operators on the second.
Result: A $(d+1)$ -local Hamiltonian acting on $N + O(T^{1/d})$ qubits. By setting $d=2$ , they achieve a 3-local Hamiltonian on $N + O(T^{1/2})$ qubits.
Ground State Encoding: Unlike previous works using Johnson graphs for time evolution, they introduce a penalty term ( $H_{stab}$ ) to ensure the computation history is encoded in the ground state of the Hamiltonian, not just the time evolution.

B. Efficient Verification Circuit for SAT

To apply the reduction to $k$ -SAT, they construct a quantum verification circuit $U_\Phi$ for a $k$ -CNF formula $\Phi$ with $n$ variables and $m$ clauses.

Ancilla Efficiency: They use a counter to track satisfied clauses. Since counting up to $m$ requires only $\log m$ qubits, the ancilla count is $O(\log m) = o(n)$ .
Gate Count: The circuit size is $O(n \log^2 n)$ , which is small enough to ensure the resulting Hamiltonian size remains $n + o(n)$ .

C. Fine-Grained Reductions

LH to QPF: They show that approximating the QPF with constant relative error allows distinguishing between the "YES" and "NO" cases of the LH problem. If the ground state energy is low, $Z$ is large; if high, $Z$ is exponentially small. This establishes that QPF is at least as hard as LH.
Algorithm for QPF: They design a quantum algorithm that avoids the temperature-dependent slowdown of previous methods.
- Technique: Partition the energy spectrum into intervals. Use Hamiltonian simulation and Phase Estimation to map eigenstates to energy values.
- Counting: Use Amplitude Estimation on an EPR state (maximally entangled state) to count the number of eigenstates in each interval without needing to prepare specific eigenstates.
- Error Mitigation: To handle the "double-counting" error near interval boundaries, they run the algorithm over multiple partitions with disjoint boundaries and average the results, achieving $1/\text{poly}(n)$ relative error.

3. Key Contributions and Results

Theorem 1: Size-Preserving Construction

They prove the existence of a $(d+1)$ -local Hamiltonian $H_x$ acting on $N + O(T^{1/d})$ qubits that encodes the verification of a QMA circuit with $T$ gates.

Significance: This is the first construction to achieve $O(1)$ locality with $o(T)$ clock qubits.

Theorem 2: Hardness of 3-Local Hamiltonian

Assuming SETH (classical) and QSETH (quantum):

Classical: No algorithm can solve 3-LH in time $O(2^{(1-\epsilon)n})$ for any $\epsilon > 0$ .
Quantum: No algorithm can solve 3-LH in time $O(2^{(1-\epsilon)n/2})$ for any $\epsilon > 0$ .
Implication: The current best algorithms ( $O^*(2^n)$ and $O^*(2^{n/2})$ ) are essentially optimal.

Theorem 3: Hardness of Quantum Partition Function

Assuming SETH and QSETH:

Approximating the QPF for 3-local Hamiltonians with constant relative error cannot be done in $O(2^{(1-\epsilon)n})$ (classical) or $O(2^{(1-\epsilon)n/2})$ (quantum).
This holds even in the low-temperature regime where previous algorithms struggled.

Theorem 4: Optimal Quantum Algorithm for QPF

They present a quantum algorithm that approximates the QPF with relative error $1/\text{poly}(n)$ in $O^*(2^{n/2})$ time.

Significance: This matches the conditional lower bound derived from QSETH and improves upon the state-of-the-art algorithm by Bravyi et al. (Nature Physics 2022), which had a running time dependent on the partition function value $Z$ (slower at low temperatures).

4. Significance and Impact

Resolution of Fine-Grained Complexity: The paper settles the fine-grained complexity of the Local Hamiltonian problem for fixed locality (3-local). It confirms that the "Grover barrier" ( $2^{n/2}$ ) and the brute-force barrier ( $2^n$ ) are likely unbreakable for these problems under standard complexity conjectures.
New Construction Paradigm: The size-preserving circuit-to-Hamiltonian construction is a major technical breakthrough. It resolves a long-standing bottleneck in quantum complexity theory where reductions to fixed-locality Hamiltonians usually incurred massive qubit overheads.
Algorithmic Improvement: The new QPF algorithm demonstrates that the low-temperature regime does not inherently require super-Grover speedups or exponential slowdowns, provided one uses amplitude estimation on entangled states rather than direct state preparation.
Bridging Physics and CS: The work strengthens the link between condensed matter physics (Hamiltonian complexity) and theoretical computer science (fine-grained complexity), showing that physical constraints (locality) do not necessarily make problems easier to solve than their general counterparts.

5. Open Questions

The authors highlight several open directions:

Can a size-preserving reduction be achieved for 2-local Hamiltonians? (Current construction requires 3-local).
Does the hardness hold for geometrically local Hamiltonians or specific interaction types (e.g., Heisenberg)?
What is the complexity when the energy gap is large ( $\Omega(1)$ ) rather than inverse polynomial?
Can QPF be reduced back to LH?

In summary, this paper provides a rigorous proof that the Local Hamiltonian and Quantum Partition Function problems are likely intractable beyond current exponential-time bounds, while simultaneously providing a new, optimal quantum algorithm for the latter.