論文の概要: Mean Field Approximation for solving QUBO problems

• arxiv url: http://arxiv.org/abs/2106.03238v1
• Date: Sun, 6 Jun 2021 20:35:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-27 11:30:44.059268
• Title: Mean Field Approximation for solving QUBO problems
• Title（参考訳）: QUBO問題の解法における平均場近似
• Authors: M\'at\'e Tibor Veszeli and G\'abor Vattay
• Abstract要約: 平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。 提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quadratic Unconstrained Binary Optimization (QUBO) problems are NP hard; thus, so far, there are no algorithms to solve them efficiently. There are exact methods like the Branch-and-Bound algorithm for smaller problems, and for larger ones, many good approximations like stochastic simulated annealing for discrete variables or the mean field annealing for continuous variables. This paper will show that the statistical physics approach and the quantum mechanical approach in the mean field annealing give the same result. We examined the Ising problem, which is an alternative formulation of the QUBO problem. Our methods consist of a set of simple gradient-based minimizations with continuous variables, thus easy to simulate. We benchmarked our methods with solving the Maximum Cut problem with the G-sets. In many graphs, we could achieve the best-known Cut Value.
• Abstract（参考訳）: 擬似非拘束バイナリ最適化(QUBO)問題はNPが難しいため、今のところ効率よく解くアルゴリズムは存在しない。 より小さな問題に対する分岐・境界アルゴリズムのような厳密な方法があり、より大きな問題に対しては、離散変数に対する確率的シミュレートアニーリングや連続変数の平均場アニーリングのような多くの良い近似がある。 本稿では, 平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが, 同じ結果をもたらすことを示す。 我々は,QUBO問題に代わる定式化であるIsing問題を検討した。 提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。 我々はg集合による最大カット問題の解法をベンチマークした。 多くのグラフでは、最もよく知られたカット値が得られる。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• 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)
• Quantum optimization algorithm based on multistep quantum computation [0.0]
  本稿では,多段階量子計算に基づく関数の最小値を求める量子アルゴリズムを提案する。 このアルゴリズムでは、問題の探索空間の次元を指数関数的に段階的に減らすことができる。 連続的なテスト関数のアルゴリズムを検証した。
  論文  参考訳（メタデータ） (2023-06-30T01:58:23Z)
• Numerical Approximation in CFD Problems Using Physics Informed Machine Learning [0.0]
  この論文は、幅広いCFD問題に普遍的に使用できる代替近似法を見つけるための様々な手法に焦点を当てている。 その焦点は、微分方程式を計算データによるトレーニングなしで解くことができるような、物理情報に基づく機械学習技術に留まっている。 極端な学習機械(ELM)は、チューナブルパラメーターを犠牲にして非常に高速なニューラルネットワークアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-01T22:54:51Z)
• Converting ADMM to a Proximal Gradient for Convex Optimization Problems [4.56877715768796]
  融解ラッソや凸クラスタリングなどのスパース推定では、問題を解くために、近位勾配法またはマルチプライヤー(ADMM)の交互方向法のいずれかを適用します。 本論文では,制約と目的が強く凸であると仮定し,ADMM溶液を近位勾配法に変換する一般的な方法を提案する。 数値実験により, 効率の面で有意な改善が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-22T07:41:12Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer [0.966840768820136]
  量子アニールを用いた不等式制約下でのバイナリ最適化問題の解法を提案する。 本研究では,乗算器の交互方向法を用いる。 本手法の計算時間は,高密度グラフ上で定義された様々なQKPに取り組み,精度の高い解法よりも高速であることがわかった。
  論文  参考訳（メタデータ） (2020-12-11T04:30:16Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• A H\"olderian backtracking method for min-max and min-min problems [0.0]
  本稿では,凸空間外におけるmin-maxあるいはmin-min問題の解法を提案する。 我々は、学習においてユビキタスな剛性を仮定し、この手法を多くの最適化問題に適用する。
  論文  参考訳（メタデータ） (2020-07-17T08:12:31Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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