論文の概要: Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
- arxiv url: http://arxiv.org/abs/2609.34532v1
- Date: Mon, 28 Sep 2026 08:02:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 12:43:51.300167
- Title: Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
- Title（参考訳）: $k$ローカルハミルトニアンと高速量子アルゴリズムの低エネルギー状態密度に関する準最適境界
- Abstract要約: 一般の$k$ローカルハミルトニアンの低エネルギー推定と状態準備は、量子複雑性理論の基本的な課題である。
これらの問題に対して、二進エントロピー関数が実行時指数を支配できる高速指数量子アルゴリズムを提案する。
我々の主な技術的結果は、ハミルトンの低エネルギー部分空間の次元上のエントロピーが支配する下界であり、基底状態の分極によって得られる。
- 参考スコア（独自算出の注目度）: 1.5049442691806056
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound $O^\ast(2^{n/2})$ for both problems, with the improvement depending on the relative accuracy $\varepsilon$ and the locality $k$. In this work, we present faster exponential quantum algorithms for these problems, where the binary entropy function governs the runtime exponent. For sufficiently small $\varepsilon/k$, our algorithms improve the exponent by a factor of $\log(k/\varepsilon)$ over [BGLGST, PRL 2025]. Our main technical result is an entropy-governed lower bound on the dimension of the Hamiltonian's low-energy subspace, obtained by depolarizing its ground state. For fixed $k$, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg, $XY$, and Ising models on arbitrary interaction graphs.
- Abstract（参考訳）: 一般の$k$ローカルハミルトニアンの低エネルギー推定と状態準備は、量子複雑性理論の基本的な課題である。
Buhrman et al ~ [BGLGST, PRL 2025] は、両方の問題に対して自然グロバー境界$O^\ast(2^{n/2})$を破り、改善は相対精度$\varepsilon$と局所性$k$に依存する。
本研究では,2進エントロピー関数が実行時指数を制御し,これらの問題に対する高速指数量子アルゴリズムを提案する。
十分小さな$\varepsilon/k$の場合、我々のアルゴリズムは$\log(k/\varepsilon)$ over [BGLGST, PRL 2025] で指数を改善する。
我々の主な技術的結果は、ハミルトンの低エネルギー部分空間の次元上のエントロピーが支配する下界であり、基底状態の分極によって得られる。
固定$k$の場合、この境界は指数の定数要素まで最適である。
同じフレームワークは、任意の相互作用グラフ上のHeisenberg, $XY$, Isingモデルに対してより厳密な境界を与える。
関連論文リスト
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians [1.0323063834827415]
一般の$k$ローカルハミルトニアンの低エネルギー推定と状態準備は、量子複雑性理論の基本的な課題である。
より高速な量子アルゴリズムは、すべての深さ$d$状態に対して最小エネルギーで束縛された量子状態を出力する。
論文 参考訳（メタデータ） (2026-05-18T11:36:43Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions [1.43494686131174]
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による最先端アルゴリズムを改善する量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-02-16T01:11:55Z) - Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
我々は、ハミルトニアン復号量子干渉計(HDQI)を紹介する。
HDQIはコヒーレントな測定とパウリ群のシンプレクティック表現を利用して、ギブスサンプリングとハミルトン・ベリアンを減少させる。
そこで,HDQI はギブズ状態を任意の温度で効率的に生成し,物理的にモチベーションを持つハミルトニアンのクラスに適応することを示した。
論文 参考訳（メタデータ） (2025-10-09T08:06:15Z) - Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Beating the natural Grover bound for low-energy estimation and state preparation [0.23034630097498876]
多体ハミルトニアンの基底状態エネルギーの推定は、量子物理学の多くの分野において中心的な課題である。
量子アルゴリズムは、任意の$k$-body Hamiltonian $H$を与えられた場合、基底状態エネルギーの見積もりを計算する。
論文 参考訳（メタデータ） (2024-07-03T12:47:06Z) - On stability of k-local quantum phases of matter [0.4999814847776097]
一般量子低密度パリティチェック符号に対応するハミルトンのユークリッドに対するエネルギーギャップの安定性を解析する。
局所ハミルトニアンは広い零温度エントロピーを持つことができるので、熱力学の第3法則の意味を論じる。
論文 参考訳（メタデータ） (2024-05-29T18:00:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。