論文の概要: Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm

• arxiv url: http://arxiv.org/abs/2402.15029v2
• Date: Mon, 11 Nov 2024 19:30:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-13 13:16:46.068076
• Title: Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm
• Title（参考訳）: 量子アルゴリズムによる2段階確率最適化プログラムの期待値関数の計算
• Authors: Caleb Rotello, Peter Graf, Matthew Reynolds, Eric B. Jones, Cody James Winkleblack, Wesley Jones,
• Abstract要約: 2段階プログラミングは不確実性の下での意思決定における問題定式化である。 この研究は量子アルゴリズムを用いて、期待値関数をスピードアップで推定する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Two-stage stochastic programming is a problem formulation for decision-making under uncertainty. In the first stage, the actor makes a best "here and now" decision in the presence of uncertain quantities that will be resolved in the future, represented in the objective function as the expected value function. This function is a multi-dimensional integral of the second stage optimization problem, which must be solved over all possible future scenarios. This work uses a quantum algorithm to estimate the expected value function with a polynomial speedup. Our algorithm gains its advantage through the two following observations. First, by encoding the probability distribution as a quantum wavefunction in an auxilliary register, and using this register as control logic for a phase-separation unitary, Digitized Quantum Annealing (DQA) can converge to the minimium of each scenario in the random variable in parallel. Second, Quantum Amplitude Estimation (QAE) on DQA can calculate the expected value of this per-scenario optimized wavefunction, producing an estimate for the expected value function. Quantum optimization is theorized to have a polynomial speedup for combinatorial optimization problems, and estimation error from QAE is known to converge inverse-linear in the number of samples (as opposed to the best case inverse of a square root in classical Monte Carlo). Therefore, assuming the probability distribution wavefunction can be prepared efficiently, we conclude our method has a polynomial speedup (of varying degree, depending on the optimization problem) over classical methods for estimating the expected value function. We conclude by demonstrating this algorithm on a stochastic programming problem inspired by operating the power grid under weather uncertainty.
• Abstract（参考訳）: 2段階確率プログラミングは不確実性の下での意思決定における問題定式化である。 第1段階では、期待値関数として目的関数で表される、将来解決されるであろう不確実量の存在下で、俳優は最高の「現在と現在」決定を行う。 この関数は第2段階最適化問題の多次元積分であり、将来のあらゆるシナリオで解決しなければならない。 この研究は、多項式スピードアップで期待値関数を推定するために量子アルゴリズムを用いる。 我々のアルゴリズムは以下の2つの観測を通してその優位性を得る。 第一に、確率分布を補助レジスタの量子波動関数として符号化し、このレジスタを位相分離ユニタリの制御ロジックとして使用することにより、DQA(Digitized Quantum Annealing)は、ランダム変数の各シナリオの最小値に並列に収束させることができる。 第2に、DQA上の量子振幅推定(QAE)は、このシナリオごとの最適化された波動関数の期待値を計算することができ、期待値関数の見積もりを生成する。 量子最適化は組合せ最適化問題の多項式スピードアップを持つように理論化され、QAEからの推定誤差はサンプル数に逆線形を収束させることが知られている(古典モンテカルロの平方根の最良のケース逆数とは対照的に)。 したがって、確率分布の波動関数を効率的に作成できると仮定すると、期待値関数を推定するための古典的手法よりも多項式の高速化(最適化問題によっては様々な程度)が可能であると結論付ける。 我々は,このアルゴリズムを気象不確実性の下で電力網を動作させることに着想を得た確率的プログラミング問題に対して実証することによって結論付けた。

関連論文リスト

• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。 このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
  論文  参考訳（メタデータ） (2024-07-29T13:54:28Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Algorithmic Cluster Expansions for Quantum Problems [0.0]
  計算問題のクラスに対して近似アルゴリズムを開発するための一般的な枠組みを確立する。 我々は,その同一性に近い量子回路の確率振幅を近似するために,我々の枠組みを適用した。 我々のアルゴリズム条件は期待値に対してほぼ最適であり、ゼロ自由度という意味での熱予測値に対して最適であることを示す。
  論文  参考訳（メタデータ） (2023-06-15T09:11:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
  雑音は量子回路のバイアスによる目的関数の評価を行う。 我々は、欠落した保証を導き、収束率が影響を受けないことを見出す。
  論文  参考訳（メタデータ） (2022-09-21T19:18:41Z)
• 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)
• Quantum algorithms for numerical differentiation of expected values with respect to parameters [0.0]
  本稿では,変数の関数と実数値パラメータの期待値と,パラメータの期待値の導関数を計算する方法について考察する。 数値微分のためのQMCIと一般階中央差分式に基づいて,この問題に対する2つの量子法を提案する。 関数の滑らかさと利用可能なキュービット数によっては、2つの方法のどちらかが他方よりも優れていることが分かる。
  論文  参考訳（メタデータ） (2021-11-22T06:50:25Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization [26.313415590777858]
  我々は,非構成最適化問題のクラスを解くための2つの新しいガウスニュートンアルゴリズムを開発した。 標準的な仮定では、期待と有限サムの設定の両方を考慮する。
  論文  参考訳（メタデータ） (2020-02-17T22:56:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。