論文の概要: On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
- arxiv url: http://arxiv.org/abs/2408.15413v2
- Date: Fri, 30 Aug 2024 19:52:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-04 16:21:29.721647
- Title: On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
- Title（参考訳）: QAOAによるMaxCut問題における小さなグラフ摂動の影響について
- Authors: Leonardo Lavagna, Simone Piperno, Andrea Ceschini, Massimo Panella,
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)を用いたグラフクラスにおける最大カット(MaxCut)問題について検討する。
特に、グラフ対称性とQAOAシミュレーションによって達成される近似比の関係に関する摂動を考察する。
グラフのスペクトルとその摂動の分析を通じて、対称性がQAOAの性能に与える影響についての貴重な知見を抽出することを目的としている。
- 参考スコア（独自算出の注目度）: 0.5999777817331315
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the Maximum Cut (MaxCut) problem on different graph classes with the Quantum Approximate Optimization Algorithm (QAOA) using symmetries. In particular, heuristics on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. To do so, we first solve the MaxCut problem on well-known graphs, then we consider a simple and controllable perturbation of the graph and find again the approximate MaxCut with the QAOA. Through an analysis of the spectrum of the graphs and their perturbations, as well as a careful study of the associated automorphism groups, we aim to extract valuable insights into how symmetry impacts the performance of QAOA. These insights can then be leveraged to heuristically reduce the quantum circuit complexity, the number of training steps, or the number of parameters involved, thus enhancing the efficiency and effectiveness of QAOA-based solutions.
- Abstract（参考訳）: 本稿では,量子近似最適化アルゴリズム(QAOA)を用いて,グラフクラスにおける最大カット(MaxCut)問題を対称性を用いて検討する。
特に、グラフ対称性とQAOAシミュレーションによって達成される近似比の関係に関するヒューリスティックスを考察する。
そのために、まずよく知られたグラフ上のMaxCut問題を解き、そのグラフの単純かつ制御可能な摂動を考え、QAOAで近似したMaxCutを求める。
グラフのスペクトルとその摂動の解析、および関連する自己同型群の慎重な研究を通じて、対称性がQAOAの性能にどのように影響するかについての貴重な知見を抽出することを目的とする。
これらの洞察は、量子回路の複雑さ、トレーニングステップの数、関連するパラメータの数をヒューリスティックに減らし、QAOAベースのソリューションの効率と有効性を高めるために利用することができる。
関連論文リスト
- Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization [0.0]
我々は、グラフ自己同型を識別するために、Nautyパッケージを使用し、エッジ同値クラスを決定することに重点を置いている。
これらの対称性を利用することで、ハミルトニアンの複雑性を著しく低減することができる。
この結果から, 自己同型に基づく対称性を用いて, 得られた解の質を損なうことなく, 計算オーバーヘッドを著しく低減できることが示唆された。
論文 参考訳（メタデータ） (2024-10-29T17:10:25Z) - MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
量子近似最適化アルゴリズム(QAOA)とその変種は、最適化問題に対処する大きな可能性を示している。
良好な性能を実現するために必要な回路深度は問題固有であり、しばしば現在の量子デバイスの最大容量を超える。
ミキサジェネレータネットワーク (MG-Net) は, 最適ミキサハミルトニアンを動的に定式化するための統合ディープラーニングフレームワークである。
論文 参考訳（メタデータ） (2024-09-27T12:28:18Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - 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) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - 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) - Impact of Graph Structures for QAOA on MaxCut [0.2609784101826761]
量子近似最適化アルゴリズム(QAOA)は、量子コンピューティングを用いて最適化問題を解くための有望な方法である。
我々は、すべての連結非同型グラフに対するMaxCut問題において、少なくとも3つの深さでのQAOAの性能を評価する。
構造と性能の関係を知ることで、量子的優位性を示す可能性のある問題のクラスを特定できる。
論文 参考訳（メタデータ） (2021-02-11T13:32:00Z) - Exploiting Symmetry Reduces the Cost of Training QAOA [6.295931120803673]
そこで本研究では,QAOAエネルギーの対称性を利用して,QAOAエネルギーの評価を高速化するための新しい手法を提案する。
目的関数の古典的対称性と、QAOAエネルギーに関するコストハミルトニアン項の対称性の関連性を示す。
我々のアプローチは一般であり、既知の対称性の任意の部分群に適用され、グラフ問題に限らない。
論文 参考訳（メタデータ） (2021-01-25T18:25:44Z) - Classical symmetries and QAOA [3.2880869992413246]
本稿では,量子近似最適化アルゴリズム(QAOA)と最適化対象関数の基本的な対称性との関係について検討する。
本稿では,QAOA力学の量子対称性特性と目的関数の古典対称性群との関係を定式化する。
論文 参考訳（メタデータ） (2020-12-08T20:02:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。