論文の概要: Towards Natural Gas Contract Selection via Quantum-Guided Independent Set Reduction

• arxiv url: http://arxiv.org/abs/2609.00881v1
• Date: Tue, 01 Sep 2026 08:14:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-02 16:31:36.460275
• Title: Towards Natural Gas Contract Selection via Quantum-Guided Independent Set Reduction
• Title（参考訳）: 量子誘導独立セットリダクションによる天然ガス契約選択に向けて
• Authors: Vivek Dixit, Vaibhaw Kumar, Kentaro Ohno, Alberto Maldonado Romo, Larry Bowden,
• Abstract要約: 本稿では,ノイズの多い量子ハードウェアの限界内で大規模MISインスタンスを解くための量子古典的フレームワークについて検討する。 最大900のコントラクトを含む6つの合成対契約適合性グラフ上で,アルゴリズムの評価を行った。
• 参考スコア（独自算出の注目度）: 1.2178992475191557
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Selecting mutually compatible natural gas transportation contracts is a practically important optimization task in which operators must choose from many candidate agreements subject to temporal, infrastructural, and flow-related constraints. As the number of candidates grows, the resulting search space becomes difficult to explore exhaustively. We study a pairwise abstraction of this task, formulated as a Maximum Clique problem on a contract-compatibility graph, or equivalently as a Maximum Independent Set (MIS) problem on the complement graph. Building on recent work, this paper studies a quantum-classical framework for solving large-scale MIS instances within the limitations of noisy quantum hardware. The approach combines iterative classical graph reduction with quantum-guided optimization to progressively simplify the search space while maintaining high solution quality. This enables large candidate spaces to be reduced to smaller subproblems that are more suitable for execution on current quantum computers. We evaluate the approach on fifteen benchmark instances from the Quantum Optimization Benchmarking Library (QOBLIB), obtaining an average approximation ratio of 0.996 and recovering optimal solutions for fourteen instances, including graphs with up to 186 vertices. We further evaluate the algorithm on six synthetic pairwise contract-compatibility graphs containing up to 900 contracts, where the proposed method achieves an average approximation ratio of 0.989 and obtains optimal solutions in four cases. These experiments demonstrate the ability of the hybrid MIS solver to reduce industrially motivated graphs. The pairwise abstraction serves as the first step of a two-stage screening procedure that narrows the candidate contracts to a smaller set of mutually compatible ones, which can then be verified against pipeline-capacity constraints.
• Abstract（参考訳）: 相互に互換性のある天然ガス輸送契約を選択することは、オペレーターが時間的、インフラ的、フロー関連の制約を受ける多くの候補契約から選択しなければならない、事実上重要な最適化タスクである。 候補数が増えるにつれて、結果の検索空間は徹底的に探索することが困難になる。 本稿では,契約適合性グラフ上の最大傾き問題,あるいは補グラフ上の最大独立集合(MIS)問題として定式化された,このタスクのペアワイズ抽象化について検討する。 近年の研究では、ノイズの多い量子ハードウェアの限界内で大規模MISインスタンスを解くための量子古典的フレームワークについて研究している。 このアプローチは、反復的な古典グラフの削減と量子誘導最適化を組み合わせることで、高い解品質を維持しながら、探索空間を徐々に単純化する。 これにより、現在の量子コンピュータ上での実行に適しているより小さなサブプロブレムに、大きな候補空間を縮小することができる。 本研究では,量子最適化ベンチマークライブラリ(QOBLIB)による15のベンチマークインスタンスに対するアプローチを評価し,平均近似比0.996を取得し,最大186頂点のグラフを含む14のインスタンスに対する最適解を復元する。 さらに, 最大900のコントラクトを含む6つの合成対契約適合性グラフ上で, 提案手法は平均0.989の近似比を達成し, 4つのケースで最適解を得る。 これらの実験は、ハイブリッドMISソルバが産業的に動機付けられたグラフを削減できることを実証する。 ペアワイズ抽象化は、2段階のスクリーニング手順の第1ステップとして機能し、候補コントラクトを互いに互換性のあるより小さなセットに絞り込み、パイプライン容量の制約に対して検証することができる。

関連論文リスト

• Boosting Sparsity in Graph Decompositions with QAOA Sampling [0.44407890087827867]
  本稿では,フリーコレクティブ・フランク・ウルフ (FCFW) アルゴリズムに基づくハイブリッド量子古典最適化アルゴリズム E-FCFW を提案する。 このようなサブルーチンをQAOAを用いて設計する方法を示す。 以上の結果から,QAOAを用いたE-FCFWは,他の方法よりもスペーサー分解(平均および中央値)が一貫して発生することがわかった。
  論文  参考訳（メタデータ） (2025-09-12T19:36:03Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• SCOOP: A Quantum-Computing Framework for Constrained Combinatorial Optimization [0.0]
  本稿では,制約付き最適化問題を解くための新しいフレームワークSCOOPを提案する。 SCOOPは制約付き問題を制約なしのものに変換し、SCOOP問題ツインを形成する。 本稿では,3つのNP-hard問題,最小支配集合,最小最大マッチング,最小集合被覆の枠組みを実証する。
  論文  参考訳（メタデータ） (2025-04-15T06:17:23Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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