論文の概要: Quantum approximate stochastic combinatorial optimisation

• arxiv url: http://arxiv.org/abs/2610.22876v1
• Date: Fri, 16 Oct 2026 03:26:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 00:56:07.739888
• Title: Quantum approximate stochastic combinatorial optimisation
• Title（参考訳）: 量子近似確率組合せ最適化
• Abstract要約: 2段階最適化は、すべての関連する情報が知られる前に決定される。 目的は、事前コストと最適適応の期待されるコストを最小化する最初の決定を見つけることである。
• 参考スコア（独自算出の注目度）: 0.27998963147546146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Two-stage stochastic combinatorial optimisation concerns discrete decisions made before all relevant information is known. An initial decision is made; once uncertainty is resolved, it can be adapted to the realised scenario, at a cost. The aim is to find the initial decision that minimises the upfront cost plus the expected cost of optimal adaptation. The first-stage decision problem is often NP-hard, and computing the expected minimum recourse cost can be $\#\mathrm{P}$-hard for a single first-stage candidate. We introduce Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse into its dynamics to search over first-stage decisions without explicitly evaluating expected minimum recourse costs. We demonstrate QASCO for MaxCut with stochastic edge weights, obtain a circuit with polynomial per-layer gate complexity, and study the ansatz via exact state-vector simulation. Across the instances considered, QASCO concentrates amplitude more effectively on stochastic-optimal first-stage decisions than a previously proposed two-stage QAOA construction. We further show that the ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without further circuit-parameter optimisation, including joint decision--scenario--recourse spaces spanning more than $2^{32}$ configurations. Under a query-cost model, comparison with the tested classical heuristics using sample-average approximations of the expected minimum recourse cost shows that QASCO more reliably reaches globally optimal first-stage solutions while requiring fewer cut evaluations. These results show how to incorporate scenario-dependent recourse into the ansatz dynamics, providing a general framework for variational quantum walks in two-stage stochastic combinatorial optimisation.
• Abstract（参考訳）: 2段階の確率的組合せ最適化は、すべての関連する情報が知られる前に決定された離散的な決定に関するものである。 最初の決定が下され、不確実性が解決されれば、実現したシナリオに、コストで適応することができる。 目的は、事前コストと最適適応の期待されるコストを最小化する最初の決定を見つけることである。 第一段階決定問題は、しばしばNPハードであり、期待される最小リコースコストは、1つの第一段階候補に対して$\#\mathrm{P}$-hardとなる。 本稿では,QASCO(Quantum Approximate Stochastic Combinatorial Optimisation)について紹介する。QASCOは,シナリオに依存したリコースを動的にコヒーレントに組み込んで,期待される最小リコースコストを明示的に評価することなく,第一段階決定を探索する。 確率的エッジ重みを持つMaxCutのQASCOを実演し, 層ごとのゲート複雑性を持つ回路を求め, 正確な状態ベクトルシミュレーションによりアンザッツについて検討する。 検討された事例全体において、QASCOは以前に提案された2段階のQAOA構築よりも確率的最適第一段階決定に振幅を効率よく集中させる。 さらに、アンザッツは、深さに依存しないパラメータ数を用いて校正でき、さらに回路パラメータの最適化を行なわずに未確認のインスタンスに適用できることを示す。 クエリコストモデルでは、期待最小リコースコストのサンプル平均近似を用いた古典的ヒューリスティックスと比較すると、QASCOはカット評価を少なくしながら、より確実にグローバルな第1ステージソリューションに到達している。 これらの結果は、シナリオ依存のリコースをアンザッツ力学に組み込む方法を示し、二段階確率組合せ最適化における変分量子ウォークの一般的な枠組みを提供する。

関連論文リスト

• Principled Design of Expected Improvement for Continuous Simulation Optimization [5.140215372395416]
  未知の異方性雑音は 3つの基本設計選択を伴います 改善、レプリケーションアロケーション、最終的なレコメンデーションを定義するために、既存のものを選択します。 これは、連続領域EI型シミュレーション最適化法において、この形式に対する最初の単純回帰保証である。
  論文  参考訳（メタデータ） (2026-10-13T14:10:35Z)
• Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization [59.75358446504504]
  本稿では,複数のスムーズな非パラメータからなるネスト構成を目的とするマルチレベル最適化について検討する。 我々は、運動量勾配推定器を構築するために、ミニバッチを持つ運動量ベース推定器を用いる。 また,関数値のクリッピングに一階近似を組み込んだバッチフリー手法を開発した。
  論文  参考訳（メタデータ） (2026-10-01T12:32:40Z)
• Model Compression with Exact Budget Constraints via Riemannian Manifolds [39.54576236079211]
  トータルコスト予算の下で各NグループにKオプションの1つを割り当てることは、効率的なAIにおいて繰り返し発生する問題である。 我々は、ソフトマックス緩和の下で、予算制約がロジット空間における滑らかなリーマン多様体を異常に単純な幾何学で定義することを示す新しいアプローチを示す。 これらの特性に基づいて、接射影、二分探索リトラクション、運動量輸送を標準とするリーマン制約最適化(RCO)を提案する。
  論文  参考訳（メタデータ） (2026-05-01T13:30:23Z)
• First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints [9.141425189503794]
  フェデレート学習に適した1次ソフトマックス重み付きスイッチング勾配法を提案する。 完全なクライアント参加の下で、我々のアルゴリズムは標準的な $mathcalO(-4)$ Oracle complexity を達成する。 我々は、統一されたエラー分解を提供し、シャープな$mathcalO(logfrac1)$高確率収束保証を確立する。
  論文  参考訳（メタデータ） (2026-03-06T00:14:46Z)
• Quantum-Circuit Framework for Two-Stage Stochastic Programming via QAOA Integrated with a Quantum Generative Neural Network [1.7240671897505615]
  2段階プログラミングは、しばしば不確実性をシナリオに識別するが、シナリオはシナリオ数において少なくとも線形にrecourse予測評価尺度を作成する。 本稿では,事前学習した逆数ネットワークがシナリオ分布を符号化する量子回路統合ワークフローを提案する。
  論文  参考訳（メタデータ） (2025-12-27T02:03:33Z)
• Bayesian Optimization for Non-Convex Two-Stage Stochastic Optimization Problems [2.9016548477524156]
  知識段階に基づく獲得関数を定式化し、最初の変数を協調的に最適化し、一貫性の保証を確立し、近似を与える。 2つの変数型間で交互にフォーカスを減らして定式化する方法と同等な経験結果を示す。
  論文  参考訳（メタデータ） (2024-08-30T16:26:31Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)

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

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