論文の概要: Energy Landscapes for the Quantum Approximate Optimisation Algorithm
- arxiv url: http://arxiv.org/abs/2401.04784v2
- Date: Wed, 8 May 2024 12:12:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-09 18:31:11.835553
- Title: Energy Landscapes for the Quantum Approximate Optimisation Algorithm
- Title（参考訳）: 量子近似最適化アルゴリズムのためのエネルギー景観
- Authors: Boy Choy, David J. Wales,
- Abstract要約: QAOA anszeのエネルギー景観を様々なグラフでナビゲートするために、流域ホットなグローバルな手法を用いています。
対応するランドスケープは一般的に単一のファンネル組織を持つため、Max-Cut ソリューションの確率がよい低いミニマを見つけることは比較的容易である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary near intermediate-scale quantum (NISQ) era. The quantum approximate optimisation algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of $L$ quantum circuit layers within a corresponding Trotterised ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well-documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here, we employ basin-hopping global optimisation methods to navigate the energy landscapes for QAOA ans\"atze for various graphs, and analyse QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualisations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organisation, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimisation. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima.
- Abstract（参考訳）: 変分量子アルゴリズム(VQA)は、現代の中間スケール量子(NISQ)時代のNPハード組合せ問題を解く大きな可能性を示している。
量子近似最適化アルゴリズム(QAOA)は、あるグラフの最大カット(Max-Cut)問題を、対応するトロッタ化アンサッツ内の$L$量子回路層を逐次実装することで解くアルゴリズムである。
回路深度の増加に伴う局所性ミニマの指数的増殖に起因するVQAsのコスト関数の探索は十分に文書化されている。
しかし, 回路深度がQAOA性能に及ぼす影響について, 正解であるMax-Cut法を求める研究は少ない。
ここでは,様々なグラフに対するQAOA ans\atzeのエネルギー景観を探索し,正しいMax-Cut解を求める上でのQAOA性能を分析するために,流域ホットなグローバルな最適化手法を用いる。
解空間の構造は、離散経路サンプリングを用いて、局所ミニマのデータベースを構築し、それらを接続する遷移状態を構築し、非接続性グラフを用いた洞察に富んだ可視化を提供する。
対応するランドスケープは一般的に単一のファンネル組織を持つため、Max-Cut ソリューションの確率がよい低いミニマを見つけることは比較的容易である。
アディアベート限界以下では、第2の局所最小値が大域最小値よりも高い解確率を与えることもある。
この重要な観察は、流域のグローバルな最適化から得られるミニマのコレクションに基づいて、QAOAのパフォーマンスを評価するためのより広範な指標を開発する動機となった。
そこで我々は,局所性ミニマから有用な解確率を解明するための期待しきい値を確立する。
関連論文リスト
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Trainability Barriers in Low-Depth QAOA Landscapes [0.0]
QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための変分量子アルゴリズムである。
以前の結果から、小さなパラメータの固定数の解析性能が保証された。
本研究は,近年の数値研究の焦点である中間体制における訓練の難しさについて考察する。
論文 参考訳（メタデータ） (2024-02-15T18:45:30Z) - Local to Global: A Distributed Quantum Approximate Optimization
Algorithm for Pseudo-Boolean Optimization Problems [7.723735038335632]
量子近似最適化アルゴリズム(QAOA)は、量子超越性を実証するための有望な候補と考えられている。
量子ビットの可用性が制限され、コヒーレンス時間制限がQAOAに挑戦し、大規模な擬ブール問題を解く。
本稿では,これを単純化したIsingモデルに変換することで,一般の擬似ブール問題を解く分散QAOAを提案する。
論文 参考訳（メタデータ） (2023-10-08T08:07:11Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - 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) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳（メタデータ） (2021-02-12T23:12:09Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Lower Bounds on Circuit Depth of the Quantum Approximate Optimization
Algorithm [0.3058685580689604]
回路深度に対する下位境界の同定に問題インスタンスの構造を用いる方法を示す。
我々は、MaxCut、MaxIndSet、およびVertex CoveringおよびBoolean satisifiabilityのいくつかのケースがQAOAアプローチに適していると主張している。
論文 参考訳（メタデータ） (2020-08-04T20:52:34Z) - Reachability Deficits in Quantum Approximate Optimization of Graph
Problems [0.0]
問題変数に対する問題制約の即時性は,性能指標として機能することを示す。
Googleが最近行ったQAOAの実験的実現によって、我々は理想的なノイズのない環境で再現されたレポートデータを再分析した。
論文 参考訳（メタデータ） (2020-07-17T18:00:00Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。