論文の概要: Influence of Different 3SAT-to-QUBO Transformations on the Solution
Quality of Quantum Annealing: A Benchmark Study
- arxiv url: http://arxiv.org/abs/2305.00720v1
- Date: Mon, 1 May 2023 08:40:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-02 13:43:38.172843
- Title: Influence of Different 3SAT-to-QUBO Transformations on the Solution
Quality of Quantum Annealing: A Benchmark Study
- Title（参考訳）: 量子アニールの溶液品質に及ぼす3SAT-to-QUBO変換の影響:ベンチマークによる検討
- Authors: Sebastian Zielinski, Jonas N\"u{\ss}lein, Jonas Stein, Thomas Gabor,
Claudia Linnhoff-Popien, Sebastian Feld
- Abstract要約: 我々はQUBO変換の選択が量子アニールが返す正しい解の数に大きな影響を与えることを示した。
また、QUBOインスタンスの異なる2次値の数とその範囲が、解の質に大きな影響を与えることを実証的に示す。
- 参考スコア（独自算出の注目度）: 9.466991829376576
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: To solve 3SAT instances on quantum annealers they need to be transformed to
an instance of Quadratic Unconstrained Binary Optimization (QUBO). When there
are multiple transformations available, the question arises whether different
transformations lead to differences in the obtained solution quality. Thus, in
this paper we conduct an empirical benchmark study, in which we compare four
structurally different QUBO transformations for the 3SAT problem with regards
to the solution quality on D-Wave's Advantage_system4.1. We show that the
choice of QUBO transformation can significantly impact the number of correct
solutions the quantum annealer returns. Furthermore, we show that the size of a
QUBO instance (i.e., the dimension of the QUBO matrix) is not a sufficient
predictor for solution quality, as larger QUBO instances may produce better
results than smaller QUBO instances for the same problem. We also empirically
show that the number of different quadratic values of a QUBO instance, combined
with their range, can significantly impact the solution quality.
- Abstract（参考訳）: 量子アニーラー上の3SATインスタンスを解決するには、準非制約バイナリ最適化(QUBO)のインスタンスに変換する必要がある。
利用可能な複数の変換がある場合、異なる変換が得られた解の品質に差をもたらすかどうかが問題となる。
そこで本研究では,D-WaveのAdvantage_system4.1における解の質について,構造的に異なる4つのQUBO変換を3SAT問題に対して比較した。
我々はQUBO変換の選択が量子アニールが返す正しい解の数に大きな影響を与えることを示した。
さらに、QUBOインスタンスのサイズ(すなわち、QUBO行列の次元)は、同じ問題に対してより小さなQUBOインスタンスよりも優れた結果が得られるため、ソリューション品質の予測には不十分であることを示す。
また、QUBOインスタンスの異なる2次値の数とその範囲が、解の質に大きな影響を与えることを実証的に示す。
関連論文リスト
- 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) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。
本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。
また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
論文 参考訳（メタデータ） (2024-04-17T11:00:12Z) - 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) - 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) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions [0.46040036610482665]
より高次擬似ブール問題をQUBO形式に変換する方法を持つことは有用である。
本稿では, 加算変数数とペナルティ係数を最小化することにより, 既存の立方体-四方体変換法を改善する。
論文 参考訳（メタデータ） (2021-07-24T22:13:42Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z) - Modeling Linear Inequality Constraints in Quadratic Binary Optimization
for Variational Quantum Eigensolver [0.0]
本稿では, 変分量子固有解法における配向型変分形式の利用について紹介する。
通常、いくつかの最適化問題に現れる4つの制約がモデル化されている。
提案手法の主な利点は、変分形式のパラメータの数が一定であることである。
論文 参考訳（メタデータ） (2020-07-26T23:36:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。