論文の概要: Quantum Approximate Optimisation for Not-All-Equal SAT
- arxiv url: http://arxiv.org/abs/2401.02852v1
- Date: Fri, 5 Jan 2024 15:11:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-08 14:53:51.098054
- Title: Quantum Approximate Optimisation for Not-All-Equal SAT
- Title（参考訳）: not-all-equal sat の量子近似最適化
- Authors: Andrew El-Kadi, Roberto Bondesan
- Abstract要約: 変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
- 参考スコア（独自算出の注目度）: 9.427635404752936
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Establishing quantum advantage for variational quantum algorithms is an
important direction in quantum computing. In this work, we apply the Quantum
Approximate Optimisation Algorithm (QAOA) -- a popular variational quantum
algorithm for general combinatorial optimisation problems -- to a variant of
the satisfiability problem (SAT): Not-All-Equal SAT (NAE-SAT). We focus on
regimes where the problems are known to have solutions with low probability and
introduce a novel classical solver that outperforms existing solvers.
Extensively benchmarking QAOA against this, we show that while the runtime of
both solvers scales exponentially with the problem size, the scaling exponent
for QAOA is smaller for large enough circuit depths. This implies a polynomial
quantum speedup for solving NAE-SAT.
- Abstract（参考訳）: 変分量子アルゴリズムの量子アドバンテージを確立することは、量子コンピューティングにおいて重要な方向である。
本研究では、一般的な組合せ最適化問題に対する一般的な変分量子アルゴリズムである量子近似最適化アルゴリズム(QAOA)を、満足度問題(SAT)の変種(NAE-SAT)に適用する。
我々は,低確率解が知られているレジームに着目し,既存の解法よりも優れた新しい古典的解法を導入する。
これに対し,QAOAの大規模ベンチマークでは,両解決器のランタイムは問題サイズに比例して指数関数的にスケールするが,QAOAのスケーリング指数は回路深さが大きいほど小さくなることを示す。
これはNAE-SATを解くための多項式量子スピードアップを意味する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
変分アルゴリズム (VQA) は, NISQシステムの実用化に向けた最有力候補の1つである。
本稿では,VQAの現状と最近の発展を考察し,近似最適化への適用性を強調した。
10ノードと20ノードのグラフ上でMaxCut問題を解くために,深さの異なるQAOA回路を実装した。
論文 参考訳（メタデータ） (2024-07-08T22:02:39Z) - Solving Combinatorial Optimization Problems with a Block Encoding Quantum Optimizer [0.0]
Block ENcoding Quantum (BEQO) は、ブロック符号化を用いてコスト関数を表現するハイブリッド量子ソルバである。
以上の結果から,BENQOはQAOAよりも有意に優れた性能を示し,VQEと各種のパフォーマンス指標を比較検討した。
論文 参考訳（メタデータ） (2024-04-22T10:10:29Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - 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 Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳（メタデータ） (2021-12-21T12:41:31Z) - Quantum mean value approximator for hard integer value problems [19.4417702222583]
正確な予想よりも近似を用いることで、最適化を大幅に改善できることを示す。
効率的な古典的サンプリングアルゴリズムとともに、極小ゲート数を持つ量子アルゴリズムは、一般的な整数値問題の効率を向上させることができる。
論文 参考訳（メタデータ） (2021-05-27T13:03:52Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - An adaptive quantum approximate optimization algorithm for solving
combinatorial problems on a quantum computer [0.0]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くハイブリッド変分量子古典アルゴリズムである。
我々は,QAOAの反復バージョンを開発し,特定のハードウェア制約に適応することができる。
アルゴリズムをMax-Cutグラフのクラス上でシミュレートし、標準QAOAよりもはるかに高速に収束することを示す。
論文 参考訳（メタデータ） (2020-05-20T18:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。