論文の概要: Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs

• arxiv url: http://arxiv.org/abs/2405.09272v1
• Date: Wed, 15 May 2024 11:41:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-16 13:36:32.825438
• Title: Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs
• Title（参考訳）: 進化的アルゴリズムによる(MAX)-3SAT QUBOsの作成
• Authors: Sebastian Zielinski, Maximilian Zorn, Thomas Gabor, Sebastian Feld, Claudia Linnhoff-Popien,
• Abstract要約: MAX-3SAT問題のQUBO表現を自動的に生成する進化的アルゴリズムを2つの手法を提案する。 得られたQUBOを500および1000クロース3SAT式で評価し,最先端のベースラインと競合する性能を示した。
• 参考スコア（独自算出の注目度）: 8.364707571011266
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: A common way of solving satisfiability instances with quantum methods is to transform these instances into instances of QUBO, which in itself is a potentially difficult and expensive task. State-of-the-art transformations from MAX-3SAT to QUBO currently work by mapping clauses of a 3SAT formula associated with the MAX-3SAT instance to an instance of QUBO and combining the resulting QUBOs into a single QUBO instance representing the whole MAX-3SAT instance. As creating these transformations is currently done manually or via exhaustive search methods and, therefore, algorithmically inefficient, we see potential for including search-based optimization. In this paper, we propose two methods of using evolutionary algorithms to automatically create QUBO representations of MAX-3SAT problems. We evaluate our created QUBOs on 500 and 1000-clause 3SAT formulae and find competitive performance to state-of-the-art baselines when using both classical and quantum annealing solvers.
• Abstract（参考訳）: 量子メソッドで満足度インスタンスを解決する一般的な方法は、これらのインスタンスをQUBOのインスタンスに変換することである。 MAX-3SATからQUBOへの最先端の変換は現在、MAX-3SATインスタンスに関連する3SAT公式をQUBOのインスタンスにマッピングし、結果のQUBOをMAX-3SATインスタンス全体を表す単一のQUBOインスタンスに結合することで機能している。 これらの変換は、現在、手動または網羅的な探索手法によって行われており、アルゴリズム的に非効率であるので、探索に基づく最適化を含む可能性を見出すことができる。 本稿では,MAX-3SAT問題のQUBO表現を自動生成する進化的アルゴリズムの2つの方法を提案する。 我々は500および1000クロース3SATの公式上で作成したQUBOを評価し,古典的および量子的アニール解法を用いて,最先端のベースラインと競合する性能を示した。

関連論文リスト

• Resource-Constrained Heuristic for Max-SAT [0.848762374187855]
  より大規模な問題をより小さなサブコンポーネントに繰り返し分解する,Max-SATのインスタンスに対するリソース制約を提案する。 本研究では,所定のSATインスタンスの構造を利用するグラフベースの新しい手法を含む,変数選択手法の集合を分析する。 我々は,Max-SAT評価ベンチマークを用いて,ランダムに生成されたMax-SATインスタンスと実世界の実例について実験を行った。
  論文  参考訳（メタデータ） (2024-10-11T18:20:08Z)
• Solving Max-3SAT Using QUBO Approximation [7.894094635723313]
  MAX-3SAT問題におけるQUBO表現の体系的近似により,現代の量子ハードウェア上での解法品質が向上するか否かを検討する。 実験的な評価では、D-Waveの量子アニールAdvantage_System6.4上でのMAX-3SAT問題の解法にQUBO近似を用いることで、最先端の正確なQUBO変換よりも優れた結果が得られることを示した。
  論文  参考訳（メタデータ） (2024-09-24T09:02:34Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。 この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
  論文  参考訳（メタデータ） (2023-06-07T12:19:22Z)
• Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations [9.466991829376576]
  3SAT-to-QUBO変換の構成において暗黙的に使用されている概念として,Pattern QUBOという名称を導入する。 近似的な3SAT-to-QUBO変換は、それでも、場合によっては非常に効果的であることを示す。
  論文  参考訳（メタデータ） (2023-05-04T08:57:51Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。 Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。 振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
  論文  参考訳（メタデータ） (2023-03-02T11:52:39Z)
• Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization [10.156623881772362]
  任意の3SATインスタンスを擬似非制約バイナリ最適化(QUBO)に変換する新しい手法を提案する。 我々のアプローチでは、現在の最先端技術よりもカップリングが少なく、物理量子ビットも少なく、結果として解の質が向上する。
  論文  参考訳（メタデータ） (2023-02-07T15:38:29Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
  本稿では,最小長の制約付き混合被覆アレイを構築するためのSAT(Satifiability)に基づくアプローチを提案する。 この問題はシステム障害検出のためのコンビネータテストの中心である。
  論文  参考訳（メタデータ） (2021-05-26T14:00:56Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。 エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。 これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
  論文  参考訳（メタデータ） (2020-09-15T17:28:42Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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