論文の概要: Transformation-Dependent Performance-Enhancement of Digital Annealer for
3-SAT
- arxiv url: http://arxiv.org/abs/2312.11645v1
- Date: Mon, 18 Dec 2023 19:01:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-20 17:55:33.607466
- Title: Transformation-Dependent Performance-Enhancement of Digital Annealer for
3-SAT
- Title（参考訳）: 3SAT用ディジタルアニールの変換依存性能向上
- Authors: Christian M\"unch, Fritz Schinkel, Sebastian Zielinski, Stefan Walter
- Abstract要約: 本研究では,QUBO,すなわちブール充足可能性(SAT)問題,特に3-SAT問題として定式化できる難解な問題のクラスについて検討する。
本稿では,Digital Annealerを特殊目的解法として用いて,変換が問題解決に与える影響について検討する。
我々は、Digital Annealerがハード3SATインスタンスの解法において量子アニールよりも優れていることを示す。
- 参考スコア（独自算出の注目度）: 0.6827423171182154
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quadratic Unconstrained Binary Optimization (QUBO) problems are NP-hard
problems and many real-world problems can be formulated as QUBO. Currently
there are no algorithms known that can solve arbitrary instances of NP-hard
problems efficiently. Therefore special-purpose hardware such as Digital
Annealer, other Ising machines, as well as quantum annealers might lead to
benefits in solving such problems. We study a particularly hard class of
problems which can be formulated as QUBOs, namely Boolean satisfiability (SAT)
problems, and specifically 3-SAT. One intriguing aspect about 3-SAT problems is
that there are different transformations from 3-SAT to QUBO. We study the
transformations' influence on the problem solution, using Digital Annealer as a
special-purpose solver. Besides well-known transformations we investigate a
novel in this context not yet discussed transformation, using less auxiliary
variables and leading to very good performance. Using exact diagonalization, we
explain the differences in performance originating from the different
transformations. We envision that this knowledge allows for specifically
engineering transformations that improve a solvers capacity to find high
quality solutions. Furthermore, we show that the Digital Annealer outperforms a
quantum annealer in solving hard 3-SAT instances.
- Abstract（参考訳）: 擬似非拘束バイナリ最適化(QUBO)問題はNPハード問題であり、実世界の多くの問題をQUBOとして定式化することができる。
現在、NPハード問題の任意のインスタンスを効率的に解くアルゴリズムは知られていない。
したがって、Digital Annealer、他のIsingマシン、および量子アニールなどの専用ハードウェアは、そのような問題を解決する利点をもたらす可能性がある。
本稿では,QUBO,すなわちブール充足可能性(SAT)問題,特に3-SAT問題として定式化できる問題について検討する。
3-SAT問題の興味深い点は、3-SATからQUBOへの変換が異なることである。
ディジタルアニーラを専用解法として,問題解に対する変換の影響について検討した。
良く知られた変換の他に、我々はこの文脈でまだ変換を議論していない新しいものを調べ、補助変数を少なくし、非常に優れたパフォーマンスをもたらす。
正確な対角化を用いて、異なる変換から生じる性能の違いを説明する。
私たちはこの知識が、高品質なソリューションを見つけるためにソルバ容量を改善するエンジニアリング変換を可能にすることを想定しています。
さらに,Digital Annealerは,ハード3SATインスタンスの解法において,量子アニールよりも優れていることを示す。
関連論文リスト
- An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
そこで本研究では,NP-Complete問題から準拘束的二項最適化問題への抽象化問題を符号化する手法を開発した。
QUBOの定式化により、QuantumやDigital Annealersといった新しいコンピューティングアーキテクチャを活用することができる。
論証や議論の実施における古典的問題の正しさと適用性を証明するために,実験を行った。
論文 参考訳（メタデータ） (2024-09-09T11:29:46Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - 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) - Influence of Different 3SAT-to-QUBO Transformations on the Solution
Quality of Quantum Annealing: A Benchmark Study [9.466991829376576]
我々はQUBO変換の選択が量子アニールが返す正しい解の数に大きな影響を与えることを示した。
また、QUBOインスタンスの異なる2次値の数とその範囲が、解の質に大きな影響を与えることを実証的に示す。
論文 参考訳（メタデータ） (2023-05-01T08:40:58Z) - 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) - Solution of SAT Problems with the Adaptive-Bias Quantum Approximate
Optimization Algorithm [4.03537866744963]
適応バイアスQAOA(ab-QAOA)は3SAT問題のハード領域とMax-3-SAT問題のハード領域の性能を大幅に向上させることを示す。
我々の研究は、NISQデバイスにおける最適化問題に対する量子アドバンテージを実現するための道を開いた。
論文 参考訳（メタデータ） (2022-10-06T11:25:26Z) - Comparing the Digital Annealer with Classical Evolutionary Algorithm [0.0]
特殊なハードウェアを使用するソルバの例として、IBMのQuantum System OneとD-waveのQuantum Annealer (QA)、富士通のDigital Annealer (DA)がある。
論文 参考訳（メタデータ） (2022-05-26T19:04:20Z) - Machine Learning Methods in Solving the Boolean Satisfiability Problem [72.21206588430645]
本論文は, Boolean satisfiability problem (SAT) を機械学習技術で解くことに関する最近の文献をレビューする。
ML-SATソルバを手作り特徴を持つナイーブ分類器からNeuroSATのような新たなエンド・ツー・エンドSATソルバまで,進化するML-SATソルバについて検討する。
論文 参考訳（メタデータ） (2022-03-02T05:14:12Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNFベースのSATとMaxSATは論理合成と検証システムの中心である。
そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
論文 参考訳（メタデータ） (2021-07-15T04:47:35Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。