論文の概要: Solving Max-3SAT Using QUBO Approximation

• arxiv url: http://arxiv.org/abs/2409.15891v1
• Date: Tue, 24 Sep 2024 09:02:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-26 08:11:26.902775
• Title: Solving Max-3SAT Using QUBO Approximation
• Title（参考訳）: QUBO近似を用いたMax-3SATの解法
• Authors: Sebastian Zielinski, Jonas Nüßlein, Michael Kölle, Thomas Gabor, Claudia Linnhoff-Popien, Sebastian Feld,
• Abstract要約: MAX-3SAT問題におけるQUBO表現の体系的近似により,現代の量子ハードウェア上での解法品質が向上するか否かを検討する。 実験的な評価では、D-Waveの量子アニールAdvantage_System6.4上でのMAX-3SAT問題の解法にQUBO近似を用いることで、最先端の正確なQUBO変換よりも優れた結果が得られることを示した。
• 参考スコア（独自算出の注目度）: 7.894094635723313
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As contemporary quantum computers do not possess error correction, any calculation performed by these devices can be considered an involuntary approximation. To solve a problem on a quantum annealer, it has to be expressed as an instance of Quadratic Unconstrained Binary Optimization (QUBO). In this work, we thus study whether systematically approximating QUBO representations of the MAX-3SAT problem can improve the solution quality when solved on contemporary quantum hardware, compared to using exact, non-approximated QUBO representations. For a MAX-3SAT instance consisting of a 3SAT formula with n variables and m clauses, we propose a method of systematically creating approximate QUBO representations of dimension (n x n), which is significantly smaller than the QUBO matrices of any exact, non-approximated MAX-3SAT QUBO transformation. In an empirical evaluation, we demonstrate that using our QUBO approximations for solving MAX-3SAT problems on D-Wave's quantum annealer Advantage_System6.4 can yield better results than using state-of-the-art exact QUBO transformations. Furthermore, we demonstrate that using naive QUBO approximation methods, based on removing values from exact (n+m)x(n+m)-dimensional QUBO representations of MAX-3SAT instances is ineffective.
• Abstract（参考訳）: 現代の量子コンピュータは誤り訂正を持たないため、これらの装置で実行される計算は不随意近似と見なすことができる。 量子アニールの問題を解くには、準非拘束バイナリ最適化(QUBO)の例として表さなければならない。 そこで本研究では, MAX-3SAT問題におけるQUBO表現の体系的近似が, 正確な非近似QUBO表現と比較して, 現代の量子ハードウェア上での解法品質を向上させるかを検討する。 n 個の変数と m 個の節を持つ 3SAT の式からなる MAX-3SAT インスタンスに対して,非近似の MAX-3SAT QUBO 変換の QUBO 行列よりもかなり小さい次元 (n x n) の近似 QUBO 表現を体系的に生成する方法を提案する。 実験的な評価では、D-Waveの量子アニールAdvantage_System6.4上でのMAX-3SAT問題の解法にQUBO近似を用いることで、最先端の正確なQUBO変換よりも優れた結果が得られることを示した。 さらに, MAX-3SAT インスタンスの正確な (n+m)x(n+m) 次元 QUBO 表現から値を削除することで, 単純 QUBO 近似法が有効でないことを示す。

関連論文リスト

• Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields [0.0]
  IST-SAT(Iterative Symphonic Tunneling for Satisfiability Problem)と呼ばれる新しい反復量子アルゴリズムを導入する。 IST-SATは高周波振動横場を用いた量子スピンガラス最適化問題を解く。
  論文  参考訳（メタデータ） (2024-08-13T02:09:30Z)
• Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs [8.364707571011266]
  MAX-3SAT問題のQUBO表現を自動的に生成する進化的アルゴリズムを2つの手法を提案する。 得られたQUBOを500および1000クロース3SAT式で評価し,最先端のベースラインと競合する性能を示した。
  論文  参考訳（メタデータ） (2024-05-15T11:41:13Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• 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)
• How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization [11.095381943951539]
  ほぼ任意の問題を擬似非制約バイナリ最適化(QUBO)に変換する手法のツールキットを提案する。 2つの事例問題(比率削減とロジスティック回帰)に対する我々のアプローチの使用例を示す。
  論文  参考訳（メタデータ） (2022-04-23T09:43:06Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• 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)

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

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