論文の概要: Quantum-Inspired Mean Field Probabilistic Model for Combinatorial Optimization Problems
- arxiv url: http://arxiv.org/abs/2406.03502v1
- Date: Sat, 1 Jun 2024 01:53:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 19:34:24.441175
- Title: Quantum-Inspired Mean Field Probabilistic Model for Combinatorial Optimization Problems
- Title（参考訳）: 組合せ最適化問題に対する量子インスピレーション平均場確率モデル
- Authors: Yuhan Huang, Siyuan Jin, Yichi Zhang, Ling Pan, Qiming Shao,
- Abstract要約: 擬似非制約二項最適化問題の解を近似する新しい量子インスパイア平均場(QIMF)確率モデルを開発した。
実験により,ポートフォリオ選択,重み付きマックスカット問題,イジングモデルといった大規模問題に対するソリューション評価の大幅な改善が示された。
- 参考スコア（独自算出の注目度）: 15.435730759218776
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial optimization problems are pivotal across many fields. Among these, Quadratic Unconstrained Binary Optimization (QUBO) problems, central to fields like portfolio optimization, network design, and computational biology, are NP-hard and require exponential computational resources. To address these challenges, we develop a novel Quantum-Inspired Mean Field (QIMF) probabilistic model that approximates solutions to QUBO problems with enhanced accuracy and efficiency. The QIMF model draws inspiration from quantum measurement principles and leverages the mean field probabilistic model. We incorporate a measurement grouping technique and an amplitude-based shot allocation strategy, both critical for optimizing cost functions with a polynomial speedup over traditional methods. Our extensive empirical studies demonstrate significant improvements in solution evaluation for large-scale problems of portfolio selection, the weighted maxcut problem, and the Ising model. Specifically, using S&P 500 data from 2022 and 2023, QIMF improves cost values by 152.8% and 12.5%, respectively, compared to the state-of-the-art baselines. Furthermore, when evaluated on increasingly larger datasets for QUBO problems, QIMF's scalability demonstrates its potential for large-scale QUBO challenges.
- Abstract（参考訳）: 組合せ最適化問題は、多くの分野において重要な問題である。
これらのうち、ポートフォリオ最適化、ネットワーク設計、計算生物学といった分野の中心にある準拘束的二項最適化(QUBO)問題はNPハードであり、指数計算資源を必要とする。
これらの課題に対処するため、我々はQUBO問題の解を精度と効率を向上して近似する新しい量子インスパイアされた平均場(QIMF)確率モデルを開発した。
QIMFモデルは量子測定の原理からインスピレーションを得て、平均場確率モデルを活用する。
我々は,従来の手法よりも多項式高速化によるコスト関数の最適化に重要な,測定グループ化手法と振幅に基づくショットアロケーション戦略を取り入れた。
ポートフォリオ選択や重み付きマックスカット問題,Isingモデルといった大規模問題に対するソリューション評価の大幅な改善を実証した。
具体的には、2022年と2023年のS&P 500データを用いて、QIMFは最先端のベースラインと比較して、それぞれ152.8%と12.5%のコスト値を改善する。
さらに、QUBO問題のためのより大きなデータセットを評価すると、QIMFのスケーラビリティは大規模なQUBO課題の可能性を示している。
関連論文リスト
- Differentiation Through Black-Box Quadratic Programming Solvers [16.543673072027136]
我々は,任意の2次プログラミング(QP)ソルバに対して,プラグアンドプレイの微分を可能にするモジュール型フレームワークであるdQPを紹介する。
我々の解は、QP最適化におけるアクティブ制約セットの知識が明示的な微分を可能にするというコア理論的知見に基づいている。
我々の実装は公開され、15以上の最先端QP解決器をサポートする既存のフレームワークとインターフェースします。
論文 参考訳（メタデータ） (2024-10-08T20:01:39Z) - Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
組合せ問題はビジネスにおいて共通の課題であり、特定の制約の下で最適なソリューションを見つける必要がある。
本研究では,制約付き最適化問題に対するハイブリッド量子古典法について検討する。
提案手法は、可換写像によって定義される局所量子ハミルトニアンの緩和に依存する。
論文 参考訳（メタデータ） (2024-04-30T11:40:07Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Exploring the synergistic potential of quantum annealing and gate model
computing for portfolio optimization [2.432141667343098]
我々は、量子アニールとゲートベースの量子コンピューティングシステムの両方の利点を最大限に活用するために研究を拡大する。
インド株式市場の現実世界の株価データを最大64件の資産でテストしています。
この結果から,ハイブリッドアニールゲート量子コンピューティングは,投資ポートフォリオの最適化を目指すポートフォリオマネージャにとって貴重なツールである可能性が示唆された。
論文 参考訳（メタデータ） (2023-05-02T15:02:13Z) - DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
グラフベースの拡散フレームワークであるDIFUSCOを導入する。
本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。
MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
論文 参考訳（メタデータ） (2023-02-16T11:13:36Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳（メタデータ） (2021-07-08T18:01:02Z) - Quantum variational optimization: The role of entanglement and problem
hardness [0.0]
本稿では, 絡み合いの役割, 変動量子回路の構造, 最適化問題の構造について検討する。
数値計算の結果,絡み合うゲートの分布を問題のトポロジに適応させる利点が示唆された。
リスク型コスト関数に条件値を適用することで最適化が向上し、最適解と重複する確率が増大することを示す。
論文 参考訳（メタデータ） (2021-03-26T14:06:54Z) - Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。
このアプローチは多くの実装と最適化の課題をもたらします。
提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
論文 参考訳（メタデータ） (2021-03-18T14:26:26Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳（メタデータ） (2021-02-16T06:04:27Z) - High Dimensional Level Set Estimation with Bayesian Neural Network [58.684954492439424]
本稿では,ベイズニューラルネットワークを用いた高次元レベル集合推定問題を解く新しい手法を提案する。
各問題に対して対応する理論情報に基づく取得関数を導出してデータポイントをサンプリングする。
合成データセットと実世界データセットの数値実験により,提案手法は既存手法よりも優れた結果が得られることが示された。
論文 参考訳（メタデータ） (2020-12-17T23:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。