論文の概要: Optimal Lower Bound for Ground-State Energy Estimation with a Guiding State
- arxiv url: http://arxiv.org/abs/2608.24493v1
- Date: Tue, 25 Aug 2026 12:43:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-26 14:09:34.987216
- Title: Optimal Lower Bound for Ground-State Energy Estimation with a Guiding State
- Title（参考訳）: 誘導状態による地中エネルギー推定のための最適下界
- Abstract要約: 結合下界$(log(1/varepsilon)/)$を、きつい$varepsilon$-dependenceで証明する。
この下限は、基底状態が一意であることが保証され、$H$はその第1と第2の固有値の間のギャップが$$であることを示す。
- 参考スコア（独自算出の注目度）: 0.5947766849585866
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The guided Hamiltonian problem is the following: given access to the unitary $U=e^{i H}$ for some Hamiltonian $H$, and given access to a unitary that prepares a guiding state promised to have overlap at least $γ>0$ with the ground space of $H$, estimate the ground-state energy of $H$ within additive error $δ> 0$ and success probability at least $1-\varepsilon $, $\varepsilon>0$. How many applications of $U$ and its inverse $U^{-1}$ are necessary and sufficient? An upper bound $O(\log(1/\varepsilon)\log(1/γ)/γδ)$ was known, and was improved to $O(\log(1/\varepsilon)/γδ)$ very recently [JW26]. A matching lower bound was known whenever one of the three parameters $δ,γ,\varepsilon$ was held constant [MdW26]. In this paper we prove the joint lower bound $Ω(\log(1/\varepsilon)/γδ)$ with the tight $\varepsilon$-dependence provided the dimension of $H$ is at least $\log(1/\varepsilon)/γ^2$. Furthermore, we show that this same lower bound (with slightly larger dimension) holds for both the special case in which the ground state is guaranteed to be unique and $H$ has a gap of $δ$ between its first and second eigenvalue; and for ground-state preparation, where $δ$ denotes the spectral gap and $\varepsilon$ now is the approximation error. The lower bounds also apply when the Hamiltonian can be accessed via its block-encoding, and when fractional powers of $U$ are allowed, as in continuous-time Hamiltonian simulation. Lastly, improved upper bounds are known when $H$ is nonnegative and presented as a sum of squares; and our results imply the lower bound $Ω(\log(1/\varepsilon)/γ\sqrtδ)$ for this case.
- Abstract（参考訳）: 案内されたハミルトニアン問題は以下の通りである: あるハミルトニアン$H$に対するユニタリ$U=e^{i H}$へのアクセスと、少なくとも$γ>0$と$H$の基底空間と重なり合うことを約束する誘導状態の準備をするユニタリへのアクセス、加法誤差$δ>0$内の基底状態エネルギー$H$と、少なくとも1-\varepsilon$, $\varepsilon>0$の成功確率を推定する。
U$とその逆の$U^{-1}$のアプリケーションは何個必要で十分か?
上界の$O(\log(1/\varepsilon)\log(1/γ)/γδ)$が知られ、非常に最近 [JW26] で$O(\log(1/\varepsilon)/γδ)$に改善された。
一致する下界は、3つのパラメータの1つであるδ,γ,\varepsilon$が定数[MdW26]で保持されたときに知られていた。
本稿では、$H$ の次元が少なくとも $\log(1/\varepsilon)/γ^2$ であれば、タイトな $\varepsilon$-dependence を持つ結合下界 $Ω(\log(1/\varepsilon)/γδ)$ を証明する。
さらに、基底状態が一意であることが保証され、$H$がその第1と第2の固有値の間に$δ$のギャップを持つ特別な場合と、$δ$がスペクトルギャップを表し、$\varepsilon$が近似誤差である場合の両方に、この下限が成り立つことを示す。
下限は、ハミルトニアンがそのブロック符号化によってアクセス可能であり、連続時間ハミルトニアンシミュレーションのように、U$の分数乗が許されるときにも適用される。
最後に、改善された上界は、$H$ が非負で平方の和として表されるときに知られており、この場合、我々の結果は下界 $Ω(\log(1/\varepsilon)/γ\sqrtδ)$ を意味する。
関連論文リスト
- Sparse Quantum State Preparation with Sublinear T-Count [5.929956715430168]
$$n$-qubit $s$-sparse状態は、$widetildeO(mins, n3/4sqrts+sqrtslog (1/)+log (1/)$ $T$ gatesを使ってエラーを発生させることができる。
0le$と2le sle 2n/2$に対して、スパース状態の準備には$(mins,sqrtns)$$Tが必要である。
論文 参考訳（メタデータ） (2026-08-01T03:33:19Z) - Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。
すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。
単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
論文 参考訳（メタデータ） (2026-07-22T17:27:20Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Inverse-free quantum state estimation with Heisenberg scaling [4.191671741497842]
ハイゼンベルクスケーリングを実現する逆フリーな純粋量子状態推定プロトコルを提案する。
この結果から,逆自由振幅推定のためのクエリ上界$O(mind3/2/varepsilon,1/varepsilon2)$が示唆された。
論文 参考訳（メタデータ） (2025-10-29T17:48:46Z) - Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。
A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。
A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
論文 参考訳（メタデータ） (2025-09-15T14:26:11Z) - Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
論文 参考訳（メタデータ） (2025-08-09T08:28:06Z) - Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。
1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
論文 参考訳（メタデータ） (2024-06-04T15:50:42Z) - Area laws and tensor networks for maximally mixed ground states [4.527719466355631]
一般ハミルトニアンの地上空間において、最大混合状態$Omega$の相互情報に地域法則を示す。
類似性は、2次元フラストレーションのない局所的ハミルトン多様体の相互情報から導かれる。
論文 参考訳（メタデータ） (2023-10-29T14:36:30Z) - $\boldsymbol{\alpha_{>}(\epsilon) = \alpha_{<}(\epsilon)}$ For The
Margolus-Levitin Quantum Speed Limit Bound [0.0]
私は$alpha_>(epsilon)$が実際に$alpha_(epsilon)$に等しいことを示す。
また、計算における数値安定性の問題として$alpha_>(epsilon)$を指摘します。
論文 参考訳（メタデータ） (2023-05-17T10:07:31Z) - Sparse Dimensionality Reduction Revisited [13.170012290527017]
スパースジョンソン・リンデンシュトラウス変換は次元還元の中心的な手法の一つである。
疎な埋め込みを再検討し、下界の抜け穴を同定する。
また,最適埋め込み次元に対する最適半空間埋め込みの空隙性も改善する。
論文 参考訳（メタデータ） (2023-02-13T08:01:25Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。