論文の概要: Augmented Electronic Ising Machine as an Effective SAT Solver

• arxiv url: http://arxiv.org/abs/2305.01623v1
• Date: Mon, 1 May 2023 02:28:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-03 13:30:25.810912
• Title: Augmented Electronic Ising Machine as an Effective SAT Solver
• Title（参考訳）: 効果的なSATソルバーとしての電子イジングマシン
• Authors: Anshujit Sharma, Matthew Burns, Andrew Hahn, and Michael Huang
• Abstract要約: Augmented Ising Machine for SAT (AIMS) は、最先端のソフトウェアベース、GPUベース、従来のハードウェアSATソルバを桁違いに上回っていることを示す。
• 参考スコア（独自算出の注目度）: 0.6999740786886535
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: With the slowdown of improvement in conventional von Neumann systems, increasing attention is paid to novel paradigms such as Ising machines. They have very different approach to NP-complete optimization problems. Ising machines have shown great potential in solving binary optimization problems like MaxCut. In this paper, we present an analysis of these systems in satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a basic architecture fails to produce meaningful acceleration, thanks in no small part to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. With experimental analyses, we show that such an Augmented Ising Machine for SAT (AIMS), outperforms state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude. We also demonstrate AIMS to be relatively robust against device variation and noise.
• Abstract（参考訳）: 従来のフォン・ノイマンシステムの改善の遅れにより、イジングマシンのような新しいパラダイムに注目が集まる。 NP完全最適化問題に対するアプローチは全く異なる。 Ising MachineはMaxCutのようなバイナリ最適化問題の解決に大きな可能性を示している。 本稿では,これらのシステムを満足度(sat)問題で解析する。 そこで,3-SATの場合,従来のSATソルバの無作為な進歩により,基本アーキテクチャが有意義な加速を達成できないことを示す。 それでも、注意深い分析は、立方体相互作用と効率的なランダム化ヒューリスティックという2つの重要な要素の欠如に起因している。 これらの制限を克服するために、最先端のイジングマシン上での立方体相互作用に対する適切なアーキテクチャサポートを追加します。 さらに,検索空間のナビゲーションを既存のアニーリングヒューリスティックスよりもはるかに効率的にする,意味認識型アニーリングスケジュールを提案する。 実験により, SAT用拡張Ising Machine(AIMS)は, 最先端のソフトウェアベース, GPUベース, 従来のハードウェアSATソルバを桁違いに上回る性能を示した。 AIMSはデバイスの変化やノイズに対して比較的堅牢であることも示しています。

関連論文リスト

• TRIP: Trainable Region-of-Interest Prediction for Hardware-Efficient Neuromorphic Processing on Event-based Vision [33.803108353747305]
  Trainable Region-of-Interest Prediction (TRIP) は、ニューロモルフィックプロセッサ上でのイベントベースの視覚処理のためのフレームワークである。 TRIPはスパースイベント固有の低情報密度を利用してROI予測のオーバーヘッドを削減する。 我々の解法は、最先端の計算よりも46倍少ない精度で計算する必要がある。
  論文  参考訳（メタデータ） (2024-06-25T12:04:51Z)
• All-to-all reconfigurability with sparse and higher-order Ising machines [0.0]
  オール・ツー・オールのネットワーク機能をエミュレートする多重アーキテクチャを導入する。 適応並列テンパリングアルゴリズムの実行は、競合するアルゴリズムと事前ファクターの利点を示す。 pビットIMのスケールされた磁気バージョンは、汎用最適化のための最先端技術よりも桁違いに改善される可能性がある。
  論文  参考訳（メタデータ） (2023-11-21T20:27:02Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• Computability of Optimizers [71.84486326350338]
  様々な状況において、チューリングマシンでは実現不可能であり、結果としてデジタルコンピュータでは実現不可能であることを示す。 我々は、人工知能、金融数学、情報理論など、非常に異なる分野からよく知られた様々な問題に対して、そのような結果を証明している。
  論文  参考訳（メタデータ） (2023-01-15T17:41:41Z)
• Efficient Optimization with Higher-Order Ising Machines [5.697064222465131]
  その結果,高次Isingマシンは従来の2次Isingマシンよりも資源効率がよい。 その結果,Ising マシンの現状が向上した。
  論文  参考訳（メタデータ） (2022-12-07T03:18:05Z)
• MAPLE-X: Latency Prediction with Explicit Microprocessor Prior Knowledge [87.41163540910854]
  ディープニューラルネットワーク(DNN)レイテンシのキャラクタリゼーションは、時間を要するプロセスである。 ハードウェアデバイスの事前知識とDNNアーキテクチャのレイテンシを具体化し,MAPLEを拡張したMAPLE-Xを提案する。
  論文  参考訳（メタデータ） (2022-05-25T11:08:20Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers [0.30586855806896046]
  特定のコンピューティング集約的な課題に対処するための選択肢として、専用ハードウェアが登場した。 これらのプラットフォームには、デジタル論理の高効率ハードウェア実装から、新しいアルゴリズムを実装するアナログハードウェアの提案まで、多くの異なる特徴がある。 本研究では、解を効率的に見つけることができる線形方程式の特定のクラスの写像を用いて、これらの異なるアプローチのいくつかをベンチマークする。
  論文  参考訳（メタデータ） (2021-03-15T15:40:00Z)

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

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