Search Results

Documents authored by Hasegawa, Atsuya

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.ISAAC.2022.6
An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes

Authors: Atsuya Hasegawa and François Le Gall

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle 𝒪 such that BQP^𝒪 ≠ (BPP^BQNC)^𝒪 ∪ (BQNC^BPP)^𝒪. In fact, Chia et al. proved a stronger statement: for any depth parameter d, there exists an oracle that separates quantum depth d and 2d+1, when polynomial-time classical computation is allowed. This implies that relative to an oracle, doubling quantum depth gives classical and quantum hybrid schemes more computational power. In this paper, we show that for any depth parameter d, there exists an oracle that separates quantum depth d and d+1, when polynomial-time classical computation is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes. To prove our result, we consider d-Bijective Shuffling Simon’s Problem (which is a variant of d-Shuffling Simon’s Problem considered by Chia et al.) and an oracle inspired by an "in-place" permutation oracle.
Cite as

Atsuya Hasegawa and François Le Gall. An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hasegawa_et_al:LIPIcs.ISAAC.2022.6,
  author =	{Hasegawa, Atsuya and Le Gall, Fran\c{c}ois},
  title =	{{An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.6},
  URN =		{urn:nbn:de:0030-drops-172918},
  doi =		{10.4230/LIPIcs.ISAAC.2022.6},
  annote =	{Keywords: small-depth quantum circuit, hybrid quantum computer, oracle separation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.74
Quantum Advantage with Shallow Circuits Under Arbitrary Corruption

Authors: Atsuya Hasegawa and François Le Gall

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separations between the computational powers of shallow (i.e., small-depth) quantum and classical circuits: quantum circuits can solve in constant depth computational problems that require logarithmic depth to solve with classical circuits. Using quantum error correction, Bravyi, Gosset, König and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. In this paper, we consider the case where any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We make a first step forward towards establishing a quantum advantage even in this extremely challenging setting: we show that there exists a computational problem that can be solved in constant depth by a quantum circuit but such that even solving any large subproblem of this problem requires logarithmic depth with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits. In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the "robustness" of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.
Cite as

Atsuya Hasegawa and François Le Gall. Quantum Advantage with Shallow Circuits Under Arbitrary Corruption. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 74:1-74:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hasegawa_et_al:LIPIcs.ISAAC.2021.74,
  author =	{Hasegawa, Atsuya and Le Gall, Fran\c{c}ois},
  title =	{{Quantum Advantage with Shallow Circuits Under Arbitrary Corruption}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{74:1--74:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.74},
  URN =		{urn:nbn:de:0030-drops-155076},
  doi =		{10.4230/LIPIcs.ISAAC.2021.74},
  annote =	{Keywords: Quantum computing, circuit complexity, constant-depth circuits}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact