論文の概要: Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

• arxiv url: http://arxiv.org/abs/2602.14379v1
• Date: Mon, 16 Feb 2026 01:11:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 16:22:50.037324
• Title: Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
• Title（参考訳）: サイズ保存型サーキット・ト・ハミルトニアン構成による量子問題に対する微粒化複素性
• Authors: Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen,
• Abstract要約: 1-varepsilon)n)$ for any $varepsilon>0$ for any $varepsilon>0$ under the Strong Exponential-Time hypothesis (SETH)。 我々は、任意の1/mathrmpoly(n)$相対誤差に対して$O(sqrt2n)$ timeで実行し、下位境界にマッチし、Bravyi、Chowdhury、Gossによる最先端アルゴリズムを改善する量子アルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 1.43494686131174
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: 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.
• Abstract（参考訳）: 局所ハミルトニアン(LH)問題は、北エフによって導入された標準の$\mathsf{QMA}$-完全問題である。 強い指数時間仮説(SETH)の下では、任意の$\varepsilon>0$に対して$(2^{(1-\varepsilon)n/2})$に対して$\varepsilon>0$に対して$(2^{(1-\varepsilon)n/2})$に対して$\varepsilon>0$に対して$\varepsilon>0$において量子的に解決できないことを示す。 これらの下界は、現在知られているLHの古典的および量子的アルゴリズムが著しく改善できないことを示す。 さらに、量子分割関数(QPF)を任意の定値相対誤差で近似するために、より微細な複雑さの低い境界を示すことができる。 相対誤差でQPFを近似することは、$\mathsf{QMA}$問題の解部分空間の次元を概算することと同値であることが知られている。 一定の相対誤差でQPFを推定するためにSETHとQSETHの硬さを示す。 次に、任意の1/\mathrm{poly}(n)$相対誤差に対して$O(\sqrt{2^n})$時間で実行し、以下の境界をマッチングし、低温状態におけるBravyi, Chowdhury, Gosset, Wocjan (Nature Physics 2022)による最先端のアルゴリズムを改善する量子アルゴリズムを提供する。 より微細な下界を証明するために、$N$ qubits に作用する$T$-time量子回路を$N+O(T^{1/d})$ qubits に作用する$(d+1)$-local Hamiltonian に符号化した最初のサイズ保存回路-ハミルトニアン構成を導入する。 これにより、N+O(T)$ qubitsを使用する単一クロックに基づく標準構成が改善される。

関連論文リスト

• 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH [0.6015898117103068]
  局所ハミルトン問題の計算複雑性と量子分割関数(QPF)の近似について検討する。 どちらの問題もQMAハードであることが知られており、$mathsfBQP neq mathsfQMA$ という広く信じられている仮定の下では、効率的な量子アルゴリズムの出口は存在しない。 量子アルゴリズムがLHまたは近似QPFを3局所ハミルトニアンに対しても$O(2n/2)$よりもかなり高速に解くことはできないことを証明している。
  論文  参考訳（メタデータ） (2025-10-08T19:45:24Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。 我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-04T17:58:01Z)
• A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
  我々は、古典的にハードなハミルトン群の基底状態を解決するために、複雑性時間量子アルゴリズムを与える。 アルゴリズムによって効率的に解けるハミルトニアンには、古典的な難解な例が含まれていることを示す。
  論文  参考訳（メタデータ） (2024-01-25T05:01:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。