論文の概要: Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations
- arxiv url: http://arxiv.org/abs/2305.02659v1
- Date: Thu, 4 May 2023 08:57:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 16:19:47.534128
- Title: Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations
- Title（参考訳）: パターンQUBO:3SAT-to-QUBO変換のアルゴリズム構築
- Authors: Sebastian Zielinski, Jonas N\"u{\ss}lein, Jonas Stein, Thomas Gabor,
Claudia Linnhoff-Popien, Sebastian Feld
- Abstract要約: 3SAT-to-QUBO変換の構成において暗黙的に使用されている概念として,Pattern QUBOという名称を導入する。
近似的な3SAT-to-QUBO変換は、それでも、場合によっては非常に効果的であることを示す。
- 参考スコア（独自算出の注目度）: 9.466991829376576
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 3SAT instances need to be transformed into instances of Quadratic
Unconstrained Binary Optimization (QUBO) to be solved on a quantum annealer.
Although it has been shown that the choice of the 3SAT-to-QUBO transformation
can impact the solution quality of quantum annealing significantly, currently
only a few 3SAT-to-QUBO transformations are known. Additionally, all of the
known 3SAT-to-QUBO transformations were created manually (and not procedurally)
by an expert using reasoning, which is a rather slow and limiting process. In
this paper, we will introduce the name Pattern QUBO for a concept that has been
used implicitly in the construction of 3SAT-to-QUBO transformations before. We
will provide an in-depth explanation for the idea behind Pattern QUBOs and show
its importance by proposing an algorithmic method that uses Pattern QUBOs to
create new 3SAT-to-QUBO transformations automatically. As an additional
application of Pattern QUBOs and our proposed algorithmic method, we introduce
approximate 3SAT-to-QUBO transformations. These transformations sacrifice
optimality but use significantly fewer variables (and thus physical qubits on
quantum hardware) than non-approximate 3SAT-to-QUBO transformations. We will
show that approximate 3SAT-to-QUBO transformations can nevertheless be very
effective in some cases.
- Abstract（参考訳）: 3SATインスタンスは、量子アニール上で解決される準非拘束バイナリ最適化(QUBO)のインスタンスに変換する必要がある。
3SAT-to-QUBO変換の選択は量子アニールの解の質に大きな影響を与えることが示されているが、現在知られている3SAT-to-QUBO変換はわずかである。
さらに、既知の3SAT-to-QUBO変換はすべて、推論を使用する専門家によって手作業で(手続き的にではなく)作成されました。
本稿では,これまで3SAT-to-QUBO変換の構成において暗黙的に使用されてきた概念として,Pattern QUBOという名称を導入する。
本稿では,パターンQUBOの考え方を詳細に説明するとともに,パターンQUBOを用いて3SAT-to-QUBO変換を自動生成するアルゴリズムを提案する。
パターンQUBOと提案手法のさらなる応用として,近似3SAT-to-QUBO変換を導入する。
これらの変換は最適性を犠牲にするが、非近似3SAT-to-QUBO変換よりも変数(量子ハードウェア上の物理量子ビット)が著しく少ない。
近似 3sat-to-qubo 変換は、いくつかの場合において非常に効果的であることを示す。
関連論文リスト
- 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) - Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs [8.364707571011266]
MAX-3SAT問題のQUBO表現を自動的に生成する進化的アルゴリズムを2つの手法を提案する。
得られたQUBOを500および1000クロース3SAT式で評価し,最先端のベースラインと競合する性能を示した。
論文 参考訳（メタデータ） (2024-05-15T11:41:13Z) - Transformation-Dependent Performance-Enhancement of Digital Annealer for
3-SAT [0.6827423171182154]
本研究では,QUBO,すなわちブール充足可能性(SAT)問題,特に3-SAT問題として定式化できる難解な問題のクラスについて検討する。
本稿では,Digital Annealerを特殊目的解法として用いて,変換が問題解決に与える影響について検討する。
我々は、Digital Annealerがハード3SATインスタンスの解法において量子アニールよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-12-18T19:01:02Z) - A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。
この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
論文 参考訳（メタデータ） (2023-06-07T12:19:22Z) - 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) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions [0.46040036610482665]
より高次擬似ブール問題をQUBO形式に変換する方法を持つことは有用である。
本稿では, 加算変数数とペナルティ係数を最小化することにより, 既存の立方体-四方体変換法を改善する。
論文 参考訳（メタデータ） (2021-07-24T22:13:42Z) - 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) - Orbital MCMC [82.54438698903775]
任意の微分同相写像から周期軌道を構築するための2つの実用的なアルゴリズムを提案する。
また,両カーネルの実用的メリットを実証した実証的研究を行った。
論文 参考訳（メタデータ） (2020-10-15T22:25:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。