DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.12

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

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

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

The local Hamiltonian (LH) problem is the canonical 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-ε)n}) for any ε > 0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2^{(1-ε)n/2}) for any ε > 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 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(√{2ⁿ}) time for an arbitrary 1/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.

Cite as

Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, and Yu-Ching Shen. Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-To-Hamiltonian Constructions. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 12:1-12:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.CCC.2026.12,
  author =	{Chia, Nai-Hui and Hasegawa, Atsuya and Le Gall, Fran\c{c}ois and Shen, Yu-Ching},
  title =	{{Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-To-Hamiltonian Constructions}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{12:1--12:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.12},
  URN =		{urn:nbn:de:0030-drops-270543},
  doi =		{10.4230/LIPIcs.CCC.2026.12},
  annote =	{Keywords: Fine-grain complexity, SETH, QSETH, Local Hamiltonian problem, Quantum partition problem}
}

Document

DOI: 10.4230/LIPIcs.CCC.2023.33

On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation

Authors: Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract

Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and the evolution time T for the simulation greatly affect algorithm runtime as expected. While there are some specific types of Hamiltonians that can be fast-forwarded, i.e., simulated within time o(T), for some large classes of Hamiltonians (e.g., all local/sparse Hamiltonians), existing simulation algorithms require running time at least linear in the evolution time T. On the other hand, while there exist lower bounds of Ω(T) circuit size for some large classes of Hamiltonian, these lower bounds do not rule out the possibilities of Hamiltonian simulation with large but "low-depth" circuits by running things in parallel. As a result, physical systems with system size scaling with T can potentially do a fast-forwarding simulation. Therefore, it is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism. In this work, we give a negative result for the above open problem in various settings. In the oracle model, we prove that there are time-independent sparse Hamiltonians that cannot be simulated via an oracle circuit of depth o(T). In the plain model, relying on the random oracle heuristic, we show that there exist time-independent local Hamiltonians and time-dependent geometrically local Hamiltonians on n qubits that cannot be simulated via an oracle circuit of depth o(T/n^c), where the Hamiltonians act on n qubits, and c is a constant. Lastly, we generalize the above results and show that any simulators that are geometrically local Hamiltonians cannot do the simulation much faster than parallel quantum algorithms.

Cite as

Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen. On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 33:1-33:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.CCC.2023.33,
  author =	{Chia, Nai-Hui and Chung, Kai-Min and Hsieh, Yao-Ching and Lin, Han-Hsuan and Lin, Yao-Ting and Shen, Yu-Ching},
  title =	{{On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{33:1--33:45},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.33},
  URN =		{urn:nbn:de:0030-drops-183038},
  doi =		{10.4230/LIPIcs.CCC.2023.33},
  annote =	{Keywords: Hamiltonian simulation, Depth lower bound, Parallel query lower bound}
}

Search Results

Documents authored by Shen, Yu-Ching

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

Abstract

Cite as

On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation

Abstract

Cite as

Thanks for your feedback!

Could not send message