論文の概要: Solution of SAT Problems with the Adaptive-Bias Quantum Approximate
Optimization Algorithm
- arxiv url: http://arxiv.org/abs/2210.02822v3
- Date: Tue, 25 Apr 2023 08:08:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-27 03:45:27.257017
- Title: Solution of SAT Problems with the Adaptive-Bias Quantum Approximate
Optimization Algorithm
- Title（参考訳）: 適応バイアス量子近似最適化アルゴリズムによるSAT問題の解法
- Authors: Yunlong Yu, Chenfeng Cao, Xiang-Bin Wang, Nic Shannon, and Robert
Joynt
- Abstract要約: 適応バイアスQAOA(ab-QAOA)は3SAT問題のハード領域とMax-3-SAT問題のハード領域の性能を大幅に向上させることを示す。
我々の研究は、NISQデバイスにおける最適化問題に対する量子アドバンテージを実現するための道を開いた。
- 参考スコア（独自算出の注目度）: 4.03537866744963
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a promising method
for solving certain classical combinatorial optimization problems on near-term
quantum devices. When employing the QAOA to 3-SAT and Max-3-SAT problems, the
quantum cost exhibits an easy-hard-easy or easy-hard pattern respectively as
the clause density is changed. The quantum resources needed in the hard-region
problems are out of reach for current NISQ devices. We show by numerical
simulations with up to 14 variables and analytical arguments that the
adaptive-bias QAOA (ab-QAOA) greatly improves performance in the hard region of
the 3-SAT problems and hard region of the Max-3-SAT problems. For similar
accuracy, on average, ab-QAOA needs 3 levels for 10-variable 3-SAT problems as
compared to 22 for QAOA. For 10-variable Max-3-SAT problems, the numbers are 7
levels and 62 levels. The improvement comes from a more targeted and more
limited generation of entanglement during the evolution. We demonstrate that
classical optimization is not strictly necessary in the ab-QAOA since local
fields are used to guide the evolution. This leads us to propose an
optimization-free ab-QAOA that can solve the hard-region 3-SAT and Max-3-SAT
problems effectively with significantly fewer quantum gates as compared to the
original ab-QAOA. Our work paves the way for realizing quantum advantages for
optimization problems on NISQ devices.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、短期量子デバイスにおける古典的な組合せ最適化問題を解くための有望な方法である。
QAOA を 3-SAT および Max-3-SAT 問題に使用する場合、量子コストは、節密度が変化するにつれて、それぞれ容易にハードなパターンまたは簡単なハードなパターンを示す。
ハードリージョン問題で必要とされる量子リソースは、現在のNISQデバイスには及ばない。
本稿では,最大14変数の数値シミュレーションにより,適応バイアスQAOA(ab-QAOA)が3SAT問題のハード領域とMax-3-SAT問題のハード領域の性能を大幅に向上させることを示す。
同様の精度では、ab-QAOAは平均で10変数の3SAT問題に対して3レベルを必要とする。
10変数のMax-3-SAT問題では、数値は7レベルと62レベルである。
この改良は、進化の過程でより標的にされ、より限定された絡み合いから生じる。
本稿では,ab-QAOAでは局所場を用いて進化を導くため,古典最適化は必須ではないことを示す。
これにより,Ab-QAOAに比べて量子ゲートが著しく少ないハードリージョン3SATとMax-3-SATの問題を効果的に解くことができる最適化フリーなAb-QAOAを提案する。
我々の研究は、NISQデバイスにおける最適化問題に対する量子アドバンテージを実現するための道を開いた。
関連論文リスト
- 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) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。
そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
論文 参考訳（メタデータ） (2023-06-14T13:44:35Z) - 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) - Solving boolean satisfiability problems with the quantum approximate
optimization algorithm [0.05076419064097732]
量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。
我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。
約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
論文 参考訳（メタデータ） (2022-08-14T20:39:48Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Quantum Computational Phase Transition in Combinatorial Problems [0.966840768820136]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、量子コンピュータにおける離散最適化問題の近似解を求めることを目的としたアルゴリズムである。
SATのような難解な問題を解く際に,QAOAの計算位相遷移を同定する。
本稿では,QAOAの性能に限界がある高問題密度領域が,実際はQAOAを利用するのに最適であることを示す。
論文 参考訳（メタデータ） (2021-09-27T20:46:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。