論文の概要: 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)$とするアプローチを述べる。
このスケーリングは、運転者が相互に通勤している場合でも、状態準備がブラックボックスとして扱われる場合、高精度なシステムでは最悪のケースであることを示す。
我々は,動的相関関数の集合の推定を高速化する戦略を含む,いくつかの一般化を提示することによって,このアプローチの柔軟性を強調した。
関連論文リスト
- Heisenberg-limited adaptive gradient estimation for multiple observables [0.39102514525861415]
量子力学において、一般観測値の期待値を測定することは、固有の統計的不確実性を持つ。
我々は,ルート平均二乗誤差内における一般可観測値の期待値を推定する適応量子アルゴリズムを提案する。
本手法は,量子コンピュータを用いた複雑な量子システムにおいて,様々な物理特性を正確に理解し,予測する新しい手法である。
論文 参考訳（メタデータ） (2024-06-05T14:16:47Z) - Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation [0.0]
量子モンテカルロ積分(Quantum Monte Carlo integration, QMCI)は、確率変数の予測を推定する量子アルゴリズムである。
本稿では直交級数密度推定に基づいて$U_X(t)$を分割する手法を提案する。
本手法は,回路深度と総クエリ複雑性のスケーリングを,それぞれ$O(sqrtN)$と$O(N3/2)$として達成する。
論文 参考訳（メタデータ） (2024-06-04T01:50:21Z) - Quantum option pricing via the Karhunen-Lo\`{e}ve expansion [11.698830761241107]
我々は、その基盤となる資産が幾何学的ブラウン運動によってモデル化されるような、T$以上のアジアオプションを個別に監視する問題を考える。
T$と1/epsilon$の2つの量子アルゴリズムを提供するが、$epsilon$は加法近似誤差である。
論文 参考訳（メタデータ） (2024-02-15T17:37:23Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。