論文の概要: Efficient Optimization Accelerator Framework for Multistate Ising Problems

• arxiv url: http://arxiv.org/abs/2505.20250v1
• Date: Mon, 26 May 2025 17:23:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 14:37:20.347665
• Title: Efficient Optimization Accelerator Framework for Multistate Ising Problems
• Title（参考訳）: 多状態イジング問題に対する効率的な最適化高速化フレームワーク
• Authors: Chirag Garg, Sayeef Salahuddin,
• Abstract要約: イジングマシン(Ising Machine)は、NPハード最適化問題の解決を目的とした、ハードウェアアーキテクチャの傑出したクラスである。 スピン相互作用を一般化論理関数としてモデル化し,探索空間を大幅に削減する。 また、最大10000倍の性能向上を示す1024ニューロン全接続型確率Isingアクセラレータを設計した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Ising Machines are a prominent class of hardware architectures that aim to solve NP-hard combinatorial optimization problems. These machines consist of a network of interacting binary spins/neurons that evolve to represent the optimum ground state energy solution. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form to harness the computational efficiency of these Ising machines. However, this transformation, especially for multi-state problems, often leads to a more complex exploration landscape than the original problem, thus severely impacting the solution quality. To address this challenge, we model the spin interactions as a generalized boolean logic function to significantly reduce the exploration space. We benchmark the graph coloring problem from the class of multi-state NP-hard optimization using probabilistic Ising solvers to illustrate the effectiveness of our framework. The proposed methodology achieves similar accuracy compared to state-of-the-art heuristics and machine learning algorithms, and demonstrates significant improvement over the existing Ising methods. Additionally, we demonstrate that combining parallel tempering with our existing framework further reduces the coloring error by up to 50% compared to the conventionally used Gibbs sampling algorithm. We also design a 1024-neuron all-to-all connected probabilistic Ising accelerator that shows up to 10000x performance acceleration compared to heuristics while reducing the number of required physical neurons by 1.5-4x compared to conventional Ising machines. Indeed, this accelerator solution demonstrates improvement across all metrics over the current methods, i.e., energy, performance, area, and solution quality. Thus, this work expands the potential of existing Ising hardware to solve a broad class of these multistate optimization problems.
• Abstract（参考訳）: Ising Machinesは、NPハード組合せ最適化問題を解決することを目的とした、ハードウェアアーキテクチャの傑出したクラスである。 これらの機械は相互作用する二軸スピン/ニューロンのネットワークで構成され、最適基底状態エネルギー解を表すように進化する。 一般に、組合せ問題は、これらのIsingマシンの計算効率を活用するために、2次非制約バイナリ最適化(QUBO)形式に変換される。 しかし、この変換は、特に多状態問題に対して、しばしば元の問題よりも複雑な探索環境をもたらすため、ソリューションの品質に深刻な影響を及ぼす。 この課題に対処するために、スピン相互作用を一般化されたブール論理関数としてモデル化し、探索空間を大幅に削減する。 確率的イジング解法を用いて,多状態NP-ハード最適化のクラスからグラフカラー化問題をベンチマークし,本フレームワークの有効性を示す。 提案手法は、最先端のヒューリスティックスや機械学習アルゴリズムと類似の精度を実現し、既存のIsing手法よりも大幅に改善されていることを示す。 さらに,従来のGibbsサンプリングアルゴリズムと比較して,並列テンパリングと既存フレームワークを組み合わせることで着色誤差を最大50%削減できることが実証された。 また,従来のIsingマシンに比べて,必要な物理的ニューロン数を1.5～4倍減らしながら,ヒューリスティックスと比較して最大10000倍の性能向上を示す1024ニューロン全接続型Isingアクセラレータを設計した。 実際、このアクセラレーターソリューションは、現在の手法、すなわちエネルギー、性能、面積、およびソリューションの品質に対するすべての指標の改善を示す。 このように、この研究は既存のIsingハードウェアの可能性を拡大し、これらの多状態最適化問題の幅広いクラスを解決している。

関連論文リスト

• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization [0.0]
  組合せ最適化問題は、産業応用において至るところに存在している。 過去数十年間、Isingタイプの問題解決ツールの開発に精力的に取り組んできた。 量子システムと古典システムの制御と操作の最近の進歩は、新しい計算パラダイムを可能にしている。
  論文  参考訳（メタデータ） (2025-03-19T17:08:55Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。 これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。 本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Joint inference and input optimization in equilibrium networks [68.63726855991052]
  ディープ均衡モデル(Deep equilibrium model)は、従来のネットワークの深さを予測し、代わりに単一の非線形層の固定点を見つけることによってネットワークの出力を計算するモデルのクラスである。 この2つの設定の間には自然なシナジーがあることが示されています。 この戦略は、生成モデルのトレーニングや、潜時符号の最適化、デノベートやインペインティングといった逆問題に対するトレーニングモデル、対逆トレーニング、勾配に基づくメタラーニングなど、様々なタスクにおいて実証される。
  論文  参考訳（メタデータ） (2021-11-25T19:59:33Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems [101.18253437732933]
  本研究では,連続空間の逆設計問題を,制約のないバイナリ最適化問題にマッピングする,汎用的な機械学習ベースのフレームワークを開発する。 本研究では, 熱発光トポロジを熱光応用に最適化し, (ii) 高効率ビームステアリングのための拡散メタグレーティングを行うことにより, 2つの逆設計問題に対するフレームワークの性能を示す。
  論文  参考訳（メタデータ） (2021-05-06T02:22:23Z)
• Computational Overhead of Locality Reduction in Binary Optimization Problems [0.0]
  本稿では,2つの局所的(二次的)コスト関数のみに対応可能な解法の大部分に必要な局所性低減の効果について論じる。 Microsoft Azure Quantumのモンテカルロ並列解法を用いて、2つの局所表現へのポスト還元により、問題の解決がかなり困難になることを示す。
  論文  参考訳（メタデータ） (2020-12-17T15:49:55Z)
• A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization [5.460573052311485]
  本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。 通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-27T07:15:25Z)
• TIGER: Topology-aware Assignment using Ising machines Application to Classical Algorithm Tasks and Quantum Circuit Gates [2.4047296366832307]
  ゲートベースの量子コンピューティングでは、トポロジー的な方法でタスクをゲートにマップすることを目的とするマッピング問題が存在する。 既存のタスクアプローチは、物理最適化アルゴリズムのいずれかに基づいており、異なるスピードとソリューション品質のトレードオフを提供する。 本稿では,Ising マシンを用いてトポロジ対応の代入問題を解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-21T19:46:59Z)

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

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