論文の概要: Optimal Query Complexity for Ground-State Preparation
- arxiv url: http://arxiv.org/abs/2609.35668v1
- Date: Mon, 28 Sep 2026 17:26:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 19:47:47.821527
- Title: Optimal Query Complexity for Ground-State Preparation
- Title（参考訳）: 地中準備のための最適クエリ複雑性
- Abstract要約: スペクトルギャップのエネルギーしきい値が分かっている場合, 地中距離誤差$varepsilon$に対する基底状態準備の最適クエリ複雑性を決定する。
トレース距離$varepsilon$の基底状態の状態を準備するアルゴリズムを2つ与える。
- 参考スコア（独自算出の注目度）: 7.005823894951329
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known. Let $U_H$ be an $α$-block-encoding of a Hamiltonian with unique ground state $|ψ_0\rangle$, and suppose $|\langleψ_0|U_I|0\rangle|\geγ$ for a state-preparation oracle $U_I$. The threshold lies at least $Δ/2$ above the ground-state energy and at least $Δ/2$ below every excited-state energy. We give two algorithms that prepare a state within trace distance $\varepsilon$ of the ground state. One uses $O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))$ calls to $U_H$ in expectation; the other uses $O((α/(γΔ))\log(1/\varepsilon))$ calls to $U_H$ in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to $U_I$ are $O(1/γ)$ in expectation and $O(γ^{-1}\log(1/\varepsilon))$ in the worst case. On $(N+1)$-dimensional systems, these $U_I$ bounds are also optimal when the expected or worst-case count of $U_H$ calls, respectively, is $o((α/Δ)\sqrt N)$. Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.
- Abstract（参考訳）: スペクトルギャップのエネルギーしきい値が分かっていれば, トレーサランス誤差$\varepsilon$に対する基底状態準備の最適クエリ複雑性を決定する。
U_H$ を一意な基底状態を持つハミルトニアンの$α$ブロックエンコーディングとし、状態準備のオラクル $U_I$ に対して $|\langle =_0|U_I|0\rangle|\geγ$ と仮定する。
閾値は基底状態エネルギーよりも少なくとも$Δ/2$高く、励起状態エネルギーよりも少なくとも$Δ/2$低い。
トレース距離$\varepsilon$の基底状態の状態を準備するアルゴリズムを2つ与える。
1つは$O((α/Δ)(γ^{-1}+\log(1/\varepsilon))、もう1つは$O((α/(γΔ))\log(1/\varepsilon))である。
我々は、期待されるクエリ数と一致する低いバウンダリを証明し、対応する最悪のバウンダリは、Somma と de Wolf [SdW26] から従う。
U_I$の呼び出しのそれぞれのバウンダリは、予想で$O(1/γ)$、最悪の場合は$O(γ^{-1}\log(1/\varepsilon)$である。
$(N+1)$-dimensionalシステムでは、これらの$U_I$境界は、それぞれ$U_H$コールの期待値と最悪の値が$o((α/Δ)\sqrt N)$であるときに最適である。
両アルゴリズムは、一定の精度のスペクトルフィルタを用いて浄化器を構築し、振幅増幅時に順次構成し、基底状態と一定の重なり合う状態を作成する。
期待されたクエリーアルゴリズムは準備を繰り返すが、成功まで1つの高精度スペクトルフィルタが続く。
最悪ケースアルゴリズムは、精度を高め、クエリの総数を制限するフィルタを使用する。
関連論文リスト
- Simultaneously Query-Optimal Quantum Linear-System Algorithm [2.8802622551493773]
Oleft(logfrac1varepsilonright)$ query to $U_A$ and $Oleft(/sright)$ query to $U_b$。
すべての量子線型系アルゴリズムと全ての解ノルムスケールに対して、そのアルゴリズムは$(/s)$行列クエリと$(/s)$状態準備クエリの両方を必要とする単一のエルミートインスタンスが存在する。
論文 参考訳（メタデータ） (2026-09-27T15:49:21Z) - 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) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - 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) - Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。
本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。
微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
論文 参考訳（メタデータ） (2024-10-23T18:00:01Z) - Online Robust Mean Estimation [37.746091744197656]
オンライン環境における高次元ロバスト平均推定問題について検討する。
このモデルでは、オンラインロバスト平均推定の主な2つの結果が証明されている。
論文 参考訳（メタデータ） (2023-10-24T15:28:43Z) - Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
論文 参考訳（メタデータ） (2023-02-07T22:58:12Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Fast digital methods for adiabatic state preparation [0.0]
ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-08T18:00:01Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。