論文の概要: Calculating the expected value function of a two-stage stochastic
optimization program with a quantum algorithm
- arxiv url: http://arxiv.org/abs/2402.15029v1
- Date: Fri, 23 Feb 2024 00:07:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-26 15:59:00.064273
- 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, Cody James Winkleblack,
Wesley Jones
- Abstract要約: 2段階の最適化では、将来の決定の期待されるコストを計算し、現在の最良の決定を知らせる。
本研究では,2段階最適化問題における期待値関数を,確率変数の複雑性から大きく独立して推定する量子アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic optimization problems are powerful models for the operation of
systems under uncertainty and are in general computationally intensive to
solve. Two-stage stochastic optimization is one such problem, where the
objective function involves calculating the expected cost of future decisions
to inform the best decision in the present. In general, even approximating this
expectation value is a #P-Hard problem. We provide a quantum algorithm to
estimate the expected value function in a two-stage stochastic optimization
problem in time complexity largely independent from the complexity of the
random variable. Our algorithm works in two steps: (1) By representing the
random variable in a register of qubits and using this register as control
logic for a cost Hamiltonian acting on the primary system of qubits, we use the
quantum alternating operator ansatz (QAOA) with operator angles following an
annealing schedule to converge to the minimal decision for each scenario in
parallel. (2) We then use Quantum Amplitude Estimation (QAE) to approximate the
expected value function of the per-scenario optimized wavefunction. We show
that the annealing time of the procedure in (1) is independent of the number of
scenarios in the probability distribution. Additionally, estimation error in
QAE converges inverse-linear in the number of "repetitions" of the algorithm,
as opposed to converging as the inverse of the square root in traditional Monte
Carlo sampling. Because both QAOA and QAE are expected to have polynomial
advantage over their classical computing counterparts, we expect our algorithm
to have polynomial advantage over classical methods to compute the expected
value function. We implement our algorithms for a simple optimization problem
inspired by operating the power grid with renewable generation and uncertainty
in the weather, and give numerical evidence to support our arguments.
- Abstract（参考訳）: 確率的最適化問題は不確実性の下でのシステムの操作の強力なモデルであり、一般に計算集約的な解法である。
2段階確率最適化は、目標関数が将来の決定の予測コストを計算し、現在の最良の決定を知らせる問題である。
一般に、この期待値の近似でさえ#pハード問題である。
本稿では,2段階確率最適化問題における期待値関数を,確率変数の複雑性から大きく独立して推定する量子アルゴリズムを提案する。
提案アルゴリズムは,(1) キュービットのレジスタにランダム変数を表現し,このレジスタをコストハミルトニアンがキュービットのプライマリシステムに作用する制御論理として用いることにより,演算子アンサッツ(QAOA)をアニーリングスケジュールに従って演算子アンサッツを用いて,各シナリオの最小決定に並列に収束させる。
次に、量子振幅推定(QAE)を用いて、シナリオごとの最適化波動関数の期待値関数を近似する。
1)における手順のアニール時間は,確率分布のシナリオ数とは無関係であることを示す。
さらに、qaeにおける推定誤差は、従来のモンテカルロサンプリングにおける平方根の逆収束とは対照的に、アルゴリズムの「繰り返し」数で逆線形に収束する。
QAOA と 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。