Fugu-MT 論文翻訳(概要): Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization

論文の概要: Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization

arxiv url: http://arxiv.org/abs/2302.03536v1
Date: Tue, 7 Feb 2023 15:38:29 GMT
ステータス: 処理完了
システム内更新日: 2023-02-08 15:57:19.991656
Title: Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization
Title（参考訳）: 二次非拘束二項最適化による解法(Max) 3-SAT
Authors: Jonas N\"u{\ss}lein, Sebastian Zielinski, Thomas Gabor, Claudia Linnhoff-Popien and Sebastian Feld
Abstract要約: 任意の3SATインスタンスを擬似非制約バイナリ最適化(QUBO)に変換する新しい手法を提案する。我々のアプローチでは、現在の最先端技術よりもカップリングが少なく、物理量子ビットも少なく、結果として解の質が向上する。
参考スコア（独自算出の注目度）: 10.156623881772362
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We introduce a novel approach to translate arbitrary 3-SAT instances to Quadratic Unconstrained Binary Optimization (QUBO) as they are used by quantum annealing (QA) or the quantum approximate optimization algorithm (QAOA). Our approach requires fewer couplings and fewer physical qubits than the current state-of-the-art, which results in higher solution quality. We verified the practical applicability of the approach by testing it on a D-Wave quantum annealer.
Abstract（参考訳）: 量子アニーリング(QA)や量子近似最適化アルゴリズム(QAOA)で用いられるように、任意の3SATインスタンスを擬似非拘束バイナリ最適化(QUBO)に変換する新しい手法を提案する。当社のアプローチでは,現在の最先端技術よりもカップリングの削減と物理キュービットの削減が求められているため,ソリューションの品質が向上しています。 D-Wave量子アニールを用いて,本手法の実用性を検証する。

関連論文リスト

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)
Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文参考訳（メタデータ） (2024-01-05T15:11:24Z)
A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
論文参考訳（メタデータ） (2023-06-07T12:19:22Z)
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)
Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文参考訳（メタデータ） (2021-08-18T09:26:17Z)
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文参考訳（メタデータ） (2021-07-08T17:59:55Z)
Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文参考訳（メタデータ） (2021-04-30T08:50:24Z)
Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms [0.0]
分割・対数手法を用いて、元の問題を小さな問題の集合に還元する。この手法は任意のQUBOインスタンスに適用でき、全古典的またはハイブリッドな量子古典的アプローチにつながる。
論文参考訳（メタデータ） (2021-01-19T19:00:40Z)
Improving the Quantum Approximate Optimization Algorithm with postselection [0.0]
組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
論文参考訳（メタデータ） (2020-11-10T22:17:50Z)
Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文参考訳（メタデータ） (2020-03-11T13:52:41Z)

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