論文の概要: What do QAOA energies reveal about graphs?

• arxiv url: http://arxiv.org/abs/1912.12277v2
• Date: Tue, 31 Dec 2019 09:23:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-09 23:19:07.111068
• Title: What do QAOA energies reveal about graphs?
• Title（参考訳）: qaoa energiesはグラフについて何を明らかにするのか?
• Authors: Mario Szegedy
• Abstract要約: グラフ構造に対するQAOAエネルギーの依存を利用して、ランダムにあるいは司法的に選択されたパラメータをグラフについて学習する。 我々の発見の多くは、様々な制約の下で$U(G)$と解釈できる。
• 参考スコア（独自算出の注目度）: 2.0305676256390934
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) is a hybrid classical-quantum algorithm to approximately solve NP optimization problems such as MAX-CUT. We describe a new application area of QAOA circuits: graph structure discovery. We omit the time-consuming parameter-optimization phase and utilize the dependence of QAOA energy on the graph structure for randomly or judiciously chosen parameters to learn about graphs. In the first part, Following up on Wang et. al. and Brandao et. al. we give explicit formulas. We show that the layer-one QAOA energy for the MAX-CUT problem for three regular graphs carries exactly the information: {\em (# of vertices, # of triangles)}. We have calculated our explicit formulas differently from \cite{wang2018quantum}, by developing the notion of the $U$ polynomial of a graph $G$. Many of our discoveries can be interpreted as computing $U(G)$ under various restrictions. The most basic question when comparing the structure of two graphs is if they are isomorphic or not. We find that the QAOA energies separate all non-isomorphic three-regular graphs up to size 18, all strongly regular graphs up to size 26 and the Praust and the smallest Miyazaki examples. We observe that the QAOA energy values can be also used as a proxy to how much graphs differ. Unfortunately, we have also found a sequence of non-isomorphic pairs of graphs, for which the energy gap seems to shrink at an exponential rate as the size grows. Our negative findings however come with a surprise: if the QAOA energies do not measurably separate between two graphs, then both of their energy landscapes must be extremely flat (indistinguishable from constant), already when the number of QAOA layers is intermediately large. This holds due to a remarkable uncoupling phenomenon that we have only deduced from computer simulation.
• Abstract（参考訳）: 量子近似最適化アルゴリズム (quantum approximation optimization algorithm,qaoa) は、マックスカットのようなnp最適化問題を近似解くハイブリッド古典量子アルゴリズムである。 本稿では,qaoa回路の新たな応用領域であるグラフ構造発見について述べる。 時間消費パラメータ最適化フェーズを省略し、グラフ構造に対するqaoaエネルギーの依存性をランダムに選択したパラメータに活用し、グラフについて学ぶ。 第一部では、wangらに続きます。 al. と brandao など。 明示的な公式を与えます 3つの正則グラフに対するMAX-CUT問題の層1QAOAエネルギーは、ちょうど同じ情報を持つことを示す。 我々は、グラフ $g$ の $u$ 多項式の概念を発展させることで、明示的な公式を \cite{wang2018quantum} とは異なるものとして計算した。 私たちの発見の多くは、様々な制限の下で u(g)$ の計算と解釈できる。 2つのグラフの構造を比較する際の最も基本的な問題は、それらが同型かどうかである。 qaoaエネルギーは、非同型な3-正則グラフをサイズ18まで分離し、サイズ26までの強正則グラフとプラウストおよび最小の宮崎例を分離する。 また,QAOAのエネルギー値は,グラフの差分に対するプロキシとしても利用することができる。 残念なことに、我々はまた非同型グラフの列を見つけており、そこではエネルギーギャップはサイズが大きくなるにつれて指数的に小さくなる。 しかし、我々の負の発見は、QAOAのエネルギーが2つのグラフの間に測定不能に分離されない場合、これらのエネルギーランドスケープはどちらも非常に平坦でなければならない(定数と区別できない)。 これは、コンピュータシミュレーションからしか導出されていない驚くべきアンカップリング現象のためである。

関連論文リスト

• Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
  本稿では,新しいQAOAアンサッツについて述べる。 我々は、新しいアンザッツの一般式を$p=1$で導き、サイクルグラフの近似比の改善を解析的に示す。
  論文  参考訳（メタデータ） (2024-11-07T22:20:01Z)
• Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs [26.8902894372334]
  量子コンピューティングにおいて、Farhi、Gutmann、GoldstoneはMaxCutの問題を解決するためにQuantum Approximate Optimization Algorithm (QAOA)を提案した。 加法積グラフとして知られるMohantyとO'Donnellによって提案された拡張グラフの集合上で、MaxCutにQAOAを適用する。 我々は、よく知られた古典的局所アルゴリズムとQAOAを一定の深さで比較するために数値実験を行う。
  論文  参考訳（メタデータ） (2024-10-06T08:57:30Z)
• Graph Generation with Diffusion Mixture [57.78958552860948]
  グラフの生成は、非ユークリッド構造の複雑な性質を理解する必要がある実世界のタスクにとって大きな課題である。 本稿では,拡散過程の最終グラフ構造を明示的に学習することにより,グラフのトポロジーをモデル化する生成フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-02-07T17:07:46Z)
• G-Mixup: Graph Data Augmentation for Graph Classification [55.63157775049443]
  Mixupは、2つのランダムサンプル間の特徴とラベルを補間することにより、ニューラルネットワークの一般化とロバスト性を改善する上で優位性を示している。 グラフ分類のためのグラフを増補するために$mathcalG$-Mixupを提案し、グラフの異なるクラスのジェネレータ(すなわちグラフ)を補間する。 実験により、$mathcalG$-MixupはGNNの一般化とロバスト性を大幅に改善することが示された。
  論文  参考訳（メタデータ） (2022-02-15T04:09:44Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Application of graph theory in quantum computer science [0.0]
  連続時間量子ウォークモデルが非自明なグラフ構造に対して強力であることを示す。 CTQWで定義された量子空間探索は、様々な無向グラフでうまく機能することが証明されている。 この側面のスコープでは、複雑なグラフ構造に対しても量子スピードアップが観測されるかどうかを分析する。
  論文  参考訳（メタデータ） (2021-09-27T12:07:25Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。 提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
  論文  参考訳（メタデータ） (2021-07-05T11:41:16Z)
• Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks [74.26734952400925]
  ノード埋め込み次元選択(NEDS)のための最小グラフエントロピー(MinGE)アルゴリズムを提案する。 ミンゲは、グラフ上の特徴エントロピーと構造エントロピーの両方を考えており、それらはそれらのリッチな情報の特徴に従って慎重に設計されている。 ベンチマークデータセット上で人気のグラフニューラルネットワーク(GNN)を用いた実験は,提案したMinGEの有効性と一般化性を示す。
  論文  参考訳（メタデータ） (2021-05-07T11:40:29Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  本稿では,グラフクラスタメンバシップを潜在因子とするDGVAE(Dirichlet Graph Variational Autoencoder)を提案する。 バランスグラフカットにおける低パス特性により、入力グラフをクラスタメンバシップにエンコードする、Heattsと呼ばれるGNNの新しい変種を提案する。
  論文  参考訳（メタデータ） (2020-10-09T07:35:26Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。 我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
  論文  参考訳（メタデータ） (2020-05-18T14:23:09Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case [6.810856082577402]
  量子回路は、グラフの局所性を尊重するユニタリ作用素の p 個の応用を持つ。 我々は、d と n を大きく保った dn/2 エッジを持つランダムグラフにおいて、大きな独立集合を見つけることに集中する。
  論文  参考訳（メタデータ） (2020-04-20T00:48:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。