論文の概要: Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation
Values
- arxiv url: http://arxiv.org/abs/2111.09283v3
- Date: Tue, 11 Oct 2022 21:47:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 21:37:35.272432
- Title: Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation
Values
- Title(参考訳): 複数の期待値推定のための近似量子アルゴリズム
- Authors: William J. Huggins, Kianna Wan, Jarrod McClean, Thomas E. O'Brien,
Nathan Wiebe, Ryan Babbush
- Abstract要約: Gily'enらによる量子勾配推定アルゴリズムを利用して$mathcalO(sqrtM/varepsilon)$を対数因子にスケールアップする手法について述べる。
ブラックボックスとして処理された場合,このスケーリングが高精度なシステムでは最悪のケースであることが証明された。
- 参考スコア(独自算出の注目度): 0.17126708168238122
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many quantum algorithms involve the evaluation of expectation values. Optimal
strategies for estimating a single expectation value are known, requiring a
number of state preparations that scales with the target error $\varepsilon$ as
$\mathcal{O}(1/\varepsilon)$. In this paper, we address the task of estimating
the expectation values of $M$ different observables, each to within additive
error $\varepsilon$, with the same $1/\varepsilon$ dependence. We describe an
approach that leverages Gily\'en et al.'s quantum gradient estimation algorithm
to achieve $\mathcal{O}(\sqrt{M}/\varepsilon)$ scaling up to logarithmic
factors, regardless of the commutation properties of the $M$ observables. We
prove that this scaling is worst-case optimal in the high-precision regime if
the state preparation is treated as a black box, even when the operators are
mutually commuting. We highlight the flexibility of our approach by presenting
several generalizations, including a strategy for accelerating the estimation
of a collection of dynamic correlation functions.
- Abstract(参考訳): 多くの量子アルゴリズムは期待値の評価を含む。
単一の期待値を推定するための最適な戦略が知られており、ターゲットエラー$\varepsilon$を$\mathcal{o}(1/\varepsilon)$とスケールするいくつかの状態準備が必要である。
本稿では,各可観測値の期待値を加算誤差$\varepsilon$内で推定し,同じ1/\varepsilon$依存性を持つタスクについて述べる。
我々は、Gily\'en et al.の量子勾配推定アルゴリズムを利用して、$M$観測変数の可換性に関係なく、対数因子へのスケーリングを$$\mathcal{O}(\sqrt{M}/\varepsilon)$とするアプローチを述べる。
このスケーリングは、運転者が相互に通勤している場合でも、状態準備がブラックボックスとして扱われる場合、高精度なシステムでは最悪のケースであることを示す。
我々は,動的相関関数の集合の推定を高速化する戦略を含む,いくつかの一般化を提示することによって,このアプローチの柔軟性を強調した。
関連論文リスト
- Quantum option pricing via the Karhunen-Lo\`{e}ve expansion [11.698830761241107]
我々は、その基盤となる資産が幾何学的ブラウン運動によってモデル化されるような、T$以上のアジアオプションを個別に監視する問題を考える。
T$と1/epsilon$の2つの量子アルゴリズムを提供するが、$epsilon$は加法近似誤差である。
論文 参考訳(メタデータ) (2024-02-15T17:37:23Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳(メタデータ) (2023-11-05T03:33:44Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳(メタデータ) (2023-05-30T17:47:27Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳(メタデータ) (2023-02-22T20:21:25Z) - Quantum tomography using state-preparation unitaries [0.22940141855172028]
ユニタリへのアクセスが与えられると、$d$次元の量子状態の古典的記述を近似的に得るアルゴリズムを記述する。
状態の$varepsilon$-$ell$-approximationを得るには、$widetildeTheta(d/varepsilon)$ Unitaryのアプリケーションが必要です。
我々は、ランク=r$混合状態のシュターテン$q$最適推定値を得るための効率的なアルゴリズムを与える。
論文 参考訳(メタデータ) (2022-07-18T17:56:18Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳(メタデータ) (2021-08-25T21:30:27Z) - A Stochastic Path-Integrated Differential EstimatoR Expectation
Maximization Algorithm [19.216497414060658]
予測最大化(EM)アルゴリズムは、回帰器と専門家の混在を含む潜在変数モデルにおける推論において重要な要素である。
本稿では,条件予測推定器からの推測のための新しいEMであるtextttSPを提案する。
論文 参考訳(メタデータ) (2020-11-30T15:49:31Z) - Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。
特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
論文 参考訳(メタデータ) (2020-07-22T18:18:28Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。