論文の概要: Impact of Graph Structures for QAOA on MaxCut
- arxiv url: http://arxiv.org/abs/2102.05997v1
- Date: Thu, 11 Feb 2021 13:32:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-11 12:12:20.490823
- Title: Impact of Graph Structures for QAOA on MaxCut
- Title(参考訳): QAOAグラフ構造がMaxCutに及ぼす影響
- Authors: Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw,
Travis S. Humble and George Siopsis
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は、量子コンピューティングを用いて最適化問題を解くための有望な方法である。
我々は、すべての連結非同型グラフに対するMaxCut問題において、少なくとも3つの深さでのQAOAの性能を評価する。
構造と性能の関係を知ることで、量子的優位性を示す可能性のある問題のクラスを特定できる。
- 参考スコア(独自算出の注目度): 0.2609784101826761
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a promising method
of solving combinatorial optimization problems using quantum computing. QAOA on
the MaxCut problem has been studied extensively on specific families of graphs,
however, little is known about the algorithm on arbitrary graphs. We evaluate
the performance of QAOA at depths at most three on the MaxCut problem for all
connected non-isomorphic graphs with at most eight vertices and analyze how
graph structure affects QAOA performance. Some of the strongest predictors of
QAOA success are the existence of odd-cycles and the amount of symmetry in the
graph. The data generated from these studies are shared in a
publicly-accessible database to serve as a benchmark for QAOA calculations and
experiments. Knowing the relationship between structure and performance can
allow us to identify classes of combinatorial problems that are likely to
exhibit a quantum advantage.
- Abstract(参考訳): 量子近似最適化アルゴリズム(QAOA)は、量子コンピューティングを用いて組合せ最適化問題を解決するための有望な方法である。
MaxCut問題に関するQAOAは、グラフの特定の族について広く研究されているが、任意のグラフ上のアルゴリズムについてはほとんど知られていない。
我々は,最大8頂点の連結非同型グラフに対して,最大3の深さでのQAOAの性能を評価し,グラフ構造がQAOAのパフォーマンスに与える影響を分析する。
QAOAの成功の最も強い予測要因は、奇環の存在とグラフ内の対称性の量である。
これらの研究から得られたデータは、公開アクセス可能なデータベースで共有され、QAOA計算と実験のベンチマークとして機能する。
構造と性能の関係を知ることで、量子的な優位性を示す可能性のある組合せ問題のクラスを識別することができる。
関連論文リスト
- Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing [0.0]
本稿では,QAのパラメータ化バージョンを新たに導入し,アルゴリズムの正確な1局所解析を実現する。
1局所解析を持つ線形スケジュールQAは0.7020以上の近似比を達成し、既知の1局所アルゴリズムよりも優れていることを示す。
論文 参考訳(メタデータ) (2023-11-21T17:15:21Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum
Computing [99.34965725525188]
AQC(Adiabatic quantum computing)は、NP-hard最適化問題に対する有望な量子コンピューティング手法である。
本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。
最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。
論文 参考訳(メタデータ) (2023-10-18T17:59:45Z) - Similarity-Based Parameter Transferability in the Quantum Approximate
Optimization Algorithm [2.985148456817082]
特定の値に関する最適なQAOAパラメータのクラスタリングを示す。
異なるQAOAインスタンス間のパラメータの転送性がうまく説明できる。
近似比が等しい大きなアクセプタグラフに対して、最適ドナーグラフQAOAパラメータをほぼ最適パラメータとして使用できることを示す。
論文 参考訳(メタデータ) (2023-07-11T16:35:49Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳(メタデータ) (2023-06-15T15:28:12Z) - An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文 参考訳(メタデータ) (2023-02-09T07:47:06Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳(メタデータ) (2022-05-28T15:37:03Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。