Fugu-MT 論文翻訳(概要): 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH

論文の概要: 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH

arxiv url: http://arxiv.org/abs/2510.07495v1
Date: Wed, 08 Oct 2025 19:45:24 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-10 17:54:14.702169
Title: 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
Title（参考訳）: 3局所ハミルトニアン問題と定相対誤差量子分割関数近似:$O(2^{\frac{n}{2}})$アルゴリズムはQSETHの下でほぼ最適である
Authors: Nai-Hui Chia, Yu-Ching Shen,
Abstract要約: 局所ハミルトン問題の計算複雑性と量子分割関数(QPF)の近似について検討する。どちらの問題もQMAハードであることが知られており、$mathsfBQP neq mathsfQMA$ という広く信じられている仮定の下では、効率的な量子アルゴリズムの出口は存在しない。量子アルゴリズムがLHまたは近似QPFを3局所ハミルトニアンに対しても$O(2n/2)$よりもかなり高速に解くことはできないことを証明している。
参考スコア（独自算出の注目度）: 0.6015898117103068
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We investigate the computational complexity of the Local Hamiltonian (LH) problem and the approximation of the Quantum Partition Function (QPF), two central problems in quantum many-body physics and quantum complexity theory. Both problems are known to be QMA-hard, and under the widely believed assumption that $\mathsf{BQP} \neq \mathsf{QMA}$, no efficient quantum algorithm exits. The best known quantum algorithm for LH runs in $O\bigl(2^{\frac{n}{2}(1 - o(1))}\bigr)$ time, while for QPF, the state-of-the-art algorithm achieves relative error $\delta$ in $O^\ast\bigl(\frac{1}{\delta}\sqrt{\frac{2^n}{Z}}\bigr)$ time, where $Z$ denotes the value of the partition function. A nature open question is whether more efficient algorithms exist for both problems. In this work, we establish tight conditional lower bounds showing that these algorithms are nearly optimal. Under the plausible Quantum Strong Exponential Time Hypothesis (QSETH), we prove that no quantum algorithm can solve either LH or approximate QPF significantly faster than $O(2^{n/2})$, even for 3-local Hamiltonians. In particular, we show: 1) 3-local LH cannot be solved in time $O(2^{\frac{n}{2}(1-\varepsilon)})$ for any $\varepsilon > 0$ under QSETH; 2) 3-local QPF cannot be approximated up to any constant relative error in $O(2^{\frac{n}{2}(1-\varepsilon)})$ time for any $\varepsilon > 0$ under QSETH; and 3) we present a quantum algorithm that approximates QPF up to relative error $1/2 + 1/\mathrm{poly}(n)$ in $O^\ast(2^{n/2})$ time, matching our conditional lower bound. Notably, our results provide the first fine-grained lower bounds for both LH and QPF with fixed locality. This stands in sharp contrast to QSETH and the trivial fine-grained lower bounds for LH, where the locality of the SAT instance and the Hamiltonian depends on the parameter $\varepsilon$ in the $O(2^{\frac{n}{2}(1-\varepsilon)})$ running time.
Abstract（参考訳）: 量子多体物理学と量子複雑性理論において,局所ハミルトン問題(LH)と量子分割関数(QPF)の近似の計算複雑性について検討する。どちらの問題も QMA-ハードであることが知られており、$\mathsf{BQP} \neq \mathsf{QMA}$ という広く信じられている仮定の下では、効率的な量子アルゴリズムの出口は存在しない。 LH に対する最もよく知られた量子アルゴリズムは $O\bigl(2^{\frac{n}{2}(1 - o(1))}\bigr)$ time であるが、QPF では、最先端のアルゴリズムは相対誤差 $\delta$ in $O^\ast\bigl(\frac{1}{\delta}\sqrt {\frac{2^n}{Z}}\bigr)$ time である。本質的には、両方の問題に対してより効率的なアルゴリズムが存在するかどうかという問題である。本研究では,これらのアルゴリズムがほぼ最適であることを示す厳密な条件付き下界を確立する。量子強度指数時間仮説 (QSETH) の下では、量子アルゴリズムがLHまたは近似QPFのいずれかを3つの局所ハミルトニアンに対しても$O(2^{n/2})$よりもかなり高速に解けることが証明される。特に、以下に示す。 1) 3局所LHは、QSETHの下では、任意の$\varepsilon > 0$に対してO(2^{\frac{n}{2}(1-\varepsilon)})$で解決できない。 2) 3つの局所QPFは、QSETHの下での任意の$\varepsilon > 0$に対して$O(2^{\frac{n}{2}(1-\varepsilon)})$時間において、任意の一定の相対誤差に近似することはできない。 3) QPF を相対誤差 $1/2 + 1/\mathrm{poly}(n)$ in $O^\ast(2^{n/2})$ time に近似する量子アルゴリズムを提案する。特に、この結果はLHとQPFの双方に対して、局所性が固定された最初のきめ細かい下界を与える。これは QSETH や SAT インスタンスとハミルトニアンの局所性は $O(2^{\frac{n}{2}(1-\varepsilon)} のパラメータ $\varepsilon$ に依存する。

論文の概要: 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH

関連論文リスト