論文の概要: Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems
- arxiv url: http://arxiv.org/abs/2506.14250v1
- Date: Tue, 17 Jun 2025 07:11:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-18 17:34:59.371587
- Title: Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems
- Title(参考訳): 制約付き組合せ問題の量子最適化のための適応的グラフシンキング
- Authors: Monit Sharma, Hoong Chuin Lau,
- Abstract要約: 最適化問題のQUBO定式化における変数数と制約を減らすために,グラフ縮小に基づく古典量子ハイブリッドフレームワークを提案する。
提案手法は, ソリューションの実現性の向上, 修理の複雑さの低減, ハードウェア限定インスタンスの量子最適化品質の向上を実現する。
- 参考スコア(独自算出の注目度): 4.266376725904727
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A range of quantum algorithms, especially those leveraging variational parameterization and circuit-based optimization, are being studied as alternatives for solving classically intractable combinatorial optimization problems (COPs). However, their applicability is limited by hardware constraints, including shallow circuit depth, limited qubit counts, and noise. To mitigate these issues, we propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of COPs, while preserving problem structure. Our approach introduces three key ideas: (i) constraint-aware shrinking that prevents merges that will likely violate problem-specific feasibility constraints, (ii) a verification-and-repair pipeline to correct infeasible solutions post-optimization, and (iii) adaptive strategies for recalculating correlations and controlling the graph shrinking process. We apply our approach to three standard benchmark problems: Multidimensional Knapsack (MDKP), Maximum Independent Set (MIS), and the Quadratic Assignment Problem (QAP). Empirical results show that our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances. These findings demonstrate a scalable pathway for applying near-term quantum algorithms to classically challenging constrained optimization problems.
- Abstract(参考訳): 様々な量子アルゴリズム、特に変分パラメータ化と回路ベースの最適化を活用して、古典的に難解な組合せ最適化問題(COP)の解法として研究されている。
しかし、それらの適用性は、浅い回路深さ、限られた量子ビット数、ノイズなど、ハードウェアの制約によって制限されている。
これらの問題を緩和するために,問題構造を保ちながらCOPのQUBO定式化における変数数や制約を減らすために,グラフ縮小に基づく古典量子ハイブリッドフレームワークを提案する。
私たちのアプローチでは,3つの重要なアイデアを導入しています。
(i)問題固有の実行可能性制約に違反する可能性のあるマージを防止する制約対応縮小。
(二 有効でない解を最適化後補正するための検証再生パイプライン、及び
三 相関を計算し、グラフ縮小過程を制御するための適応的戦略。
我々は,Multidimensional Knapsack (MDKP), Maximum Independent Set (MIS), Quadratic Assignment Problem (QAP)の3つの標準ベンチマーク問題に適用した。
実験結果から,本手法はソリューションの実現可能性の向上,修理の複雑さの低減,ハードウェア限定インスタンスの量子最適化品質の向上を実現している。
これらの結果は、古典的な制約付き最適化問題に近距離量子アルゴリズムを適用するためのスケーラブルな経路を示す。
関連論文リスト
- Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers [4.266376725904727]
変分量子アルゴリズム(VQA)は、通常、ペナルティ法を用いて制約のない問題として再構成されるように制約付き問題を要求する。
一般的なアプローチでは、不等式制約を扱うためにQUBOの定式化においてスラック変数と二次罰則を導入する。
我々は、カスタムペナルティ関数を使って不等式制約を直接エンコードするスラックフリーな定式化について検討する。
これらのステップのような罰則は、追加の量子ビットを導入するか、微調整された重みを必要とすることなく、実現不可能な解を抑える。
論文 参考訳(メタデータ) (2025-04-17T03:20:02Z) - Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
組合せ問題はビジネスにおいて共通の課題であり、特定の制約の下で最適なソリューションを見つける必要がある。
本研究では,制約付き最適化問題に対するハイブリッド量子古典法について検討する。
提案手法は、可換写像によって定義される局所量子ハミルトニアンの緩和に依存する。
論文 参考訳(メタデータ) (2024-04-30T11:40:07Z) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。
本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。
また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
論文 参考訳(メタデータ) (2024-04-17T11:00:12Z) - Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno
Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
本稿では,制約のサブセットを解決するために標準イジング・ハミルトニアン(Ising Hamiltonian)を併用したハイブリッドフレームワークを提案する。
これらの非Ising制約の解決は、ペナルティの軽視または量子ゼノ効果によって達成される。
論文 参考訳(メタデータ) (2023-05-14T03:49:10Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。
我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。
実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
論文 参考訳(メタデータ) (2023-02-08T17:09:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。