論文の概要: Numerical Evidence for Exponential Speed-up of QAOA over Unstructured
Search for Approximate Constrained Optimization
- arxiv url: http://arxiv.org/abs/2202.00648v3
- Date: Tue, 9 May 2023 22:44:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 18:07:14.722860
- Title: Numerical Evidence for Exponential Speed-up of QAOA over Unstructured
Search for Approximate Constrained Optimization
- Title（参考訳）: 近似制約最適化のための非構造探索におけるQAOAの指数速度アップの数値的エビデンス
- Authors: John Golden, Andreas B\"artschi, Stephan Eidenbenz, Daniel O'Malley
- Abstract要約: 本稿では,Grover-style unstructured searchによるQAOAの指数的高速化の証拠を示す。
以上の結果から,QAOA性能の最大化にはミキサーと位相分離器の選択が必要であることが示唆された。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite much recent work, the true promise and limitations of the Quantum
Alternating Operator Ansatz (QAOA) are unclear. A critical question regarding
QAOA is to what extent its performance scales with the input size of the
problem instance, in particular the necessary growth in the number of QAOA
rounds to reach a high approximation ratio. We present numerical evidence for
an exponential speed-up of QAOA over Grover-style unstructured search in
finding approximate solutions to constrained optimization problems. Our result
provides a strong hint that QAOA is able to exploit the structure of an
optimization problem and thus overcome the lower bound for unstructured search.
To this end, we conduct a comprehensive numerical study on several
Hamming-weight constrained optimization problems for which we include
combinations of all standardly studied mixer and phase separator Hamiltonians
(Ring mixer, Clique mixer, Objective Value phase separator) as well as quantum
minimum-finding inspired Hamiltonians (Grover mixer, Threshold-based phase
separator). We identify Clique-Objective-QAOA with an exponential speed-up over
Grover-Threshold-QAOA and tie the latter's scaling to that of unstructured
search, with all other QAOA combinations coming in at a distant third. Our
result suggests that maximizing QAOA performance requires a judicious choice of
mixer and phase separator, and should trigger further research into other QAOA
variations.
- Abstract（参考訳）: 最近の研究にもかかわらず、量子交換演算子 Ansatz (QAOA) の真の可能性と限界は明らかでない。
QAOAに関する重要な問題は、その性能が問題インスタンスの入力サイズとどの程度スケールするか、特に高い近似比に達するために必要なQAOAラウンド数の増加である。
本稿では,Grover-style unstructured searchによるQAOAの指数的高速化の数値的証明を行い,制約付き最適化問題の近似解を求める。
この結果から,QAOAが最適化問題の構造を活かし,非構造探索の下位境界を克服できることが示唆された。
この目的のために、ハミング重み付き最適化問題の総合的な数値計算を行い、標準的なミキサーとフェーズセパレータの組合せであるハミルトニアス(リングミキサー、クリッドミキサー、オブジェクト値位相セパレータ)と、量子最小フィンディングにインスパイアされたハミルトニアス(グラバーミキサー、スレッショルドベースの位相セパレータ)を組み合わせた。
我々は,Clique-Objective-QAOAをGrover-Threshold-QAOAよりも指数的なスピードアップで同定し,後者のスケーリングを非構造化検索に結びつける。
以上の結果から,QAOA性能の最大化にはミキサと相分離器の任意選択が必要であることが示唆された。
関連論文リスト
- MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
量子近似最適化アルゴリズム(QAOA)とその変種は、最適化問題に対処する大きな可能性を示している。
良好な性能を実現するために必要な回路深度は問題固有であり、しばしば現在の量子デバイスの最大容量を超える。
ミキサジェネレータネットワーク (MG-Net) は, 最適ミキサハミルトニアンを動的に定式化するための統合ディープラーニングフレームワークである。
論文 参考訳（メタデータ） (2024-09-27T12:28:18Z) - Connecting the Hamiltonian structure to the QAOA performance and energy landscape [0.0]
量子交互演算子 Ansatz (QAOA) は2次非制約二項最適化問題の解法に有効である。
本研究は,短期量子デバイスにおけるアルゴリズムの堅牢性と最適化タスクの可能性を強調する。
論文 参考訳（メタデータ） (2024-07-05T11:32:46Z) - Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz [3.5023108034606256]
QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための量子アルゴリズムの一分野である。
特定の変種であるGrover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA)は、等価な目的値を共有する状態間で均一な振幅を保証する。
GM-QAOAはサンプリング確率を2次的に向上させ,一貫した性能を維持するために,問題サイズと指数関数的にスケールする回路深度を必要とすることを示す。
論文 参考訳（メタデータ） (2024-05-06T05:47:27Z) - Lower Bounds on Number of QAOA Rounds Required for Guaranteed
Approximation Ratios [0.0]
量子交互作用素アンサッツ(QAOA)に必要なラウンド数に対する最初の下界のいくつかを提供する。
このタイプのQAOAは、ほとんどの問題に対して一定の近似比を保証するために少なくとも複数のラウンドを必要とすることを示す。
我々のフレームワークは、すべての局所的なコスト問題に自明な制約を与えます。
論文 参考訳（メタデータ） (2023-08-29T17:10:20Z) - 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) - General Hamiltonian Representation of ML Detection Relying on the
Quantum Approximate Optimization Algorithm [74.6114458993128]
最適化問題を解くために考案された量子近似最適化アルゴリズム(QAOA)は、既存のノイズのある中間スケール量子(NISQ)デバイス上で実行することができる。
我々は、QAOAを適切に適応させることにより、一般星座の最大可能性(ML)検出問題を解く。
特に、M-ary Gray-mapped Quarature amplitude modulation (MQAM) 星座では、同相成分をコードする特定の量子ビットと二次成分をコードする量子ビットが、興味のある量子系において独立であることを示す。
論文 参考訳（メタデータ） (2022-04-11T14:11:24Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Mixer-Phaser Ans\"atze for Quantum Optimization with Hard Constraints [1.011960004698409]
パラメタライズド・サーキット・アンス・アットーを導入し,その性能を標準的な量子交互演算子・アンザッツ法と比較した数値実験の結果を示す。
アンスアッツはQAOAの混合と相分離にインスパイアされ、また高温超伝導量子プロセッサ上での動作を目的としたコンパイルの考慮によって動機付けられる。
論文 参考訳（メタデータ） (2021-07-13T04:50:56Z) - Quantum Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
論文 参考訳（メタデータ） (2021-07-11T10:56:24Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳（メタデータ） (2021-02-12T23:12:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。