論文の概要: 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からの推定誤差はサンプル数に逆線形を収束させることが知られている(古典モンテカルロの平方根の最良のケース逆数とは対照的に)。 したがって、確率分布の波動関数を効率的に作成できると仮定すると、期待値関数を推定するための古典的手法よりも多項式の高速化(最適化問題によっては様々な程度)が可能であると結論付ける。 我々は,このアルゴリズムを気象不確実性の下で電力網を動作させることに着想を得た確率的プログラミング問題に対して実証することによって結論付けた。

関連論文リスト

• Non-linear Quantum Monte Carlo [1.237454174824584]
  量子コンピューティングは、平均推定のための古典モンテカルロ法よりも2次的なスピードアップを提供する。 本研究では,非線形推定問題の幅広いクラスに対して,そのような高速化を実現する量子インサイド量子モンテカルロアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-07T17:13:27Z)
• Mixed State Variational Quantum Eigensolver for the Estimation of Expectation Values at Finite Temperature [0.0]
  有限温度における量子系における期待値の短期計算のための新しいハイブリッド量子古典アルゴリズムを提案する。 これは2つの段階に基づいており、第1段階では、変分量子固有解法(VQE)技術を用いて、フィデューシャル・トランケート密度行列を近似した混合状態を作成する。 次に、関心の観測対象に対する期待値を計算した再重み付けステージが続く。
  論文  参考訳（メタデータ） (2024-01-30T17:29:58Z)
• Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games [31.554420227087043]
  そこで本稿では,関数近似を用いた2時間スムーズなQ$学習アルゴリズムを提案する。 2時間スケールの$Q$ラーニングでは、高速スケールは勾配降下に精力的に更新され、より遅いスケールは、前回と最新の高速スケールのコンベックスを組み合わせて更新される。 重要な新規性は、遅い時間スケールの進化を捉えるために有効なリャプノフ函数を構築することである。
  論文  参考訳（メタデータ） (2023-12-08T08:39:36Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
  本稿では,ギブス分割関数を線形時間で推定する新しい量子アルゴリズムを提案する。 これは、vStefankovivc, Vempala, Vigodaの半周期的なほぼ直線時間で得られる最初のスピードアップである。
  論文  参考訳（メタデータ） (2022-07-18T14:41:48Z)
• 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)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  量子化学と材料は、量子コンピューティングの最も有望な応用の1つである。 これらの領域における産業関連問題とそれを解決する量子アルゴリズムとの整合性については、まだ多くの研究が続けられている。
  論文  参考訳（メタデータ） (2022-03-14T16:51:36Z)
• Quantum algorithms for numerical differentiation of expected values with respect to parameters [0.0]
  本稿では,変数の関数と実数値パラメータの期待値と,パラメータの期待値の導関数を計算する方法について考察する。 数値微分のためのQMCIと一般階中央差分式に基づいて,この問題に対する2つの量子法を提案する。 関数の滑らかさと利用可能なキュービット数によっては、2つの方法のどちらかが他方よりも優れていることが分かる。
  論文  参考訳（メタデータ） (2021-11-22T06:50:25Z)
• Continuous black-box optimization with quantum annealing and random subspace coding [2.839269856680851]
  ベイズ最適化のようなブラックボックス最適化アルゴリズムは、基礎関数の推論と獲得関数の最適化を交互に行い、未知関数の極端を見つける。 高次元空間では、そのようなアルゴリズムは獲得関数の最適化が困難であるため、性能が劣る。 連続ブラックボックス最適化の難しさを克服するために量子アニールを適用する。
  論文  参考訳（メタデータ） (2021-04-30T06:19:07Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

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

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