論文の概要: 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計算と実験のベンチマークとして機能する。
構造と性能の関係を知ることで、量子的な優位性を示す可能性のある組合せ問題のクラスを識別することができる。
関連論文リスト
- A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。
完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。
ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
論文 参考訳（メタデータ） (2025-01-02T05:06:16Z) - On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA [0.5999777817331315]
量子近似最適化アルゴリズム(QAOA)を用いたグラフクラスにおける最大カット(MaxCut)問題について検討する。
特に、グラフ対称性とQAOAシミュレーションによって達成される近似比の関係に関する摂動を考察する。
グラフのスペクトルとその摂動の分析を通じて、対称性がQAOAの性能に与える影響についての貴重な知見を抽出することを目的としている。
論文 参考訳（メタデータ） (2024-08-27T21:38:23Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - 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 [93.83016310295804]
AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。
本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。
最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。
これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
論文 参考訳（メタデータ） (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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。