論文の概要: Energy Landscapes for the Quantum Approximate Optimisation Algorithm
- arxiv url: http://arxiv.org/abs/2401.04784v1
- Date: Tue, 9 Jan 2024 19:17:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-11 16:06:11.315482
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。