論文の概要: Amplitude amplification-inspired QAOA: Improving the success probability
for solving 3SAT
- arxiv url: http://arxiv.org/abs/2303.01183v1
- Date: Thu, 2 Mar 2023 11:52:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-03 14:47:58.016482
- Title: Amplitude amplification-inspired QAOA: Improving the success probability
for solving 3SAT
- Title（参考訳）: 振幅増幅によるQAOA:3SAT解決の成功確率の改善
- Authors: Alexander Mandl, Johanna Barzen, Marvin Bechtold, Frank Leymann,
Karoline Wild
- Abstract要約: 振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。
Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。
振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
- 参考スコア（独自算出の注目度）: 55.78588835407174
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Boolean satisfiability problem (SAT), in particular 3SAT with its bounded
clause size, is a well-studied problem since a wide range of decision problems
can be reduced to it. Due to its high complexity, examining potentials of
quantum algorithms for solving 3SAT more efficiently is an important topic.
Since 3SAT can be formulated as unstructured search for satisfying variable
assignments, the amplitude amplification algorithm can be applied. However, the
high circuit complexity of amplitude amplification hinders its use on near-term
quantum systems. On the other hand, the Quantum Approximate Optimization
Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy
Intermediate-Scale Quantum devices in the near future due to its simple quantum
ansatz. However, although QAOA generally exhibits a high approximation ratio,
there are 3SAT problem instances where its success probability decreases using
current implementations. To address this problem, in this paper we introduce
amplitude amplification-inspired variants of QAOA to improve the success
probability for 3SAT. For this, (i) three amplitude amplification-inspired QAOA
variants are introduced and implemented, (ii) the variants are experimental
compared with a standard QAOA implementation, and (iii) the impact on the
success probability and ansatz complexity is analyzed. The experiment results
show that an improvement in the success probability can be achieved with only a
moderate increase in circuit complexity.
- Abstract（参考訳）: Boolean satisfiability problem (SAT) は、特に有界節のサイズを持つ 3SAT は、幅広い決定問題をそれに還元できるため、よく研究されている問題である。
高複雑性のため、より効率的に3SATを解く量子アルゴリズムの可能性を調べることが重要なトピックである。
3SATは可変代入を満たすための非構造化探索として定式化できるため、振幅増幅アルゴリズムを適用することができる。
しかし、振幅増幅の高回路複雑さは、短期量子システムでの使用を妨げる。
一方,Quantum Approximate Optimization Algorithm (QAOA) は,その単純な量子アンサッツにより,近い将来にノイズの多い中間量子デバイスに対して3SATを解くための候補となる。
しかし、QAOAは一般に高い近似比を示すが、現在の実装では成功確率が減少する3SAT問題がある。
本稿では,3SAT の成功確率を改善するために,振幅増幅によるQAOAの変種を提案する。
このために
(i)振幅増幅によるQAOA変種を3種類導入して実装する。
(ii)この変種は標準qaoa実装と比較して実験的であり、
(iii)成功確率とアンサッツ複雑性への影響を分析する。
実験の結果,回路の複雑度を適度に向上させるだけで,成功確率の向上が達成できることがわかった。
関連論文リスト
- 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) - Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter
Clustering [6.86850788361785]
本研究では,Grover Quantum Approximate Optimization Algorithm (G-QAOA) の2次高速化の数値的証拠を示す。
G-QAOAはGroverのアルゴリズムよりもリソース集約性が低く、3-SATやMax-SATに適応しやすい。
また、小さなインスタンスに対してIonQ Aria量子コンピュータのG-QAOAの利点を観察し、現在のハードウェアが全てのソリューションを決定・サンプリングするのに十分であることを示した。
論文 参考訳（メタデータ） (2024-02-04T19:01:27Z) - 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) - 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) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - A Quantum-Inspired Classical Solver for Boolean k-Satisfiability
Problems [0.0]
本稿では,k-satisfiability(k-SAT)問題に対するアルゴリズム的アプローチについて述べる。
次に、AmplifySATの強みと限界を特定するために、古典的なデジタルまたはアナログコンピューティング環境でこの設定を有意義に活用することについて議論する。
論文 参考訳（メタデータ） (2021-09-21T16:10:52Z) - 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) - Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
本稿では、QAS(Quantum Architecture Search)と呼ばれるリソースと実行時の効率的なスキームを提案する。
QASは、よりノイズの多い量子ゲートを追加することで得られる利点と副作用のバランスをとるために、自動的にほぼ最適アンサッツを求める。
数値シミュレータと実量子ハードウェアの両方に、IBMクラウドを介してQASを実装し、データ分類と量子化学タスクを実現する。
論文 参考訳（メタデータ） (2020-10-20T12:06:27Z) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。
本稿では,QAOAの回路深度依存性能について実験的に検討する。
この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
論文 参考訳（メタデータ） (2020-05-11T17:20:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。