論文の概要: Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs

• arxiv url: http://arxiv.org/abs/2511.13531v1
• Date: Mon, 17 Nov 2025 16:05:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:25.351897
• Title: Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs
• Title（参考訳）: パウリ弦の同時分散、重み付き独立数、新しいグラフの完全性
• Authors: Zhen-Peng Xu, Jie Wang, Qi Ye, Gereon Koßmann, René Schwonnek, Andreas Winter,
• Abstract要約: 可換性構造を符号化するグラフ、すなわちフラストレーショングラフによって、グラフ理論と量子情報の間の自然なインターフェースを提供する。 このクラスを$hbar$-perfectと呼び、完全グラフと$hbar-perfectグラフのクラスを拡張します。 絡み合い検出のための効率的なスキーム,シャドウトモグラフィーの複雑さへの接続,厳密な不確実性関係,地中エネルギーの低い計算のための構成を見いだす。
• 参考スコア（独自算出の注目度）: 13.60873698530933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A set of Pauli stings is well characterized by the graph that encodes its commutatitivity structure, i.e., by its frustration graph. This graph provides a natural interface between graph theory and quantum information, which we explore in this work. We investigate all aspects of this interface for a special class of graphs that bears tight connections between the groundstate structures of a spin systems and topological structure of a graph. We call this class $\hbar$-perfect, as it extends the class of perfect and $h$-perfect graphs. Having an $\hbar$-perfect graph opens up several applications: we find efficient schemes for entanglement detection, a connection to the complexity of shadow tomography, tight uncertainty relations and a construction for computing good lower on bounds ground state energies. Conversely this also induces quantum algorithms for computing the independence number. Albeit those algorithms do not immediately promise an advantage in runtime, we show that an approximate Hamilton encoding of the independence number can be achieved with an amount of qubits that typically scales logarithmically in the number of vertices. We also we also determine the behavior of $\hbar$-perfectness under basic graph operations and evaluate their prevalence among all graphs.
• Abstract（参考訳）: パウリのスティングの集合は、その可換性構造を符号化するグラフ、すなわちフラストレーショングラフによって、よく特徴づけられる。 このグラフは、グラフ理論と量子情報の間の自然なインターフェースを提供し、この研究で検討する。 スピン系の基底状態構造とグラフの位相構造との間に密接な関係を持つグラフの特別なクラスに対して、このインターフェースのすべての側面について検討する。 私たちはこのクラスを$\hbar$-perfectと呼び、完全グラフと$h$-perfectグラフのクラスを拡張します。 エンタングルメント検出の効率的なスキーム、シャドウトモグラフィーの複雑さへの接続、厳密な不確実性関係、境界基底エネルギーのより低い計算のための構成など。 逆に、これは独立数を計算するための量子アルゴリズムも引き起こす。 これらのアルゴリズムは、すぐには実行時の利点を約束しないが、独立数の近似ハミルトン符号化は、典型的には頂点数で対数的にスケールする量子ビットの量で達成可能であることを示す。 また、基本グラフ演算の下での$\hbar$-perfectnessの挙動を判定し、すべてのグラフの有意性を評価する。

関連論文リスト

• Multi-View Graph Learning with Graph-Tuple [13.991938982402807]
  効率的なグラフニューラルネットワーク(GNN)のためのマルチビューグラフタプルフレームワークを提案する。 グラフタプルフレームワークはグラフを1つのグラフの代わりに非結合部分グラフに分割し、主要な局所的な相互作用とより弱い長距離接続をキャプチャする。 我々は2つの科学的領域の枠組みをインスタンス化し、特徴量を持つクーロン行列からの分子特性予測と幾何学的点雲からの宇宙パラメータ推定を行う。
  論文  参考訳（メタデータ） (2025-10-11T20:57:03Z)
• Data-Adaptive Graph Framelets with Generalized Vanishing Moments for Graph Machine Learning [4.498623132806496]
  分割木に基づく局所化サポート付きグラフ上でのタイトなフレームレットシステムを構築する。 提案するグラフフレームレットシステムの汎用性をヘテロ親和性グラフ学習に活用する。 グラフフレームレットの特定の系を導出し、ニューラルネットワーク入力の特徴としてフレームレットを選択する方法を提案する。
  論文  参考訳（メタデータ） (2023-09-07T07:49:43Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data [91.27527985415007]
  既存のグラフ凝縮法は、凝縮グラフ内のノードと構造の合同最適化に依存している。 我々は、大規模グラフを小さなグラフノード集合に蒸留する、SFGCと呼ばれる新しい構造自由グラフ凝縮パラダイムを提唱する。
  論文  参考訳（メタデータ） (2023-06-05T07:53:52Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphonは任意のサイズでグラフを生成する非パラメトリックモデルであり、グラフから簡単に誘導できる。 解析可能でスケーラブルなグラフ生成モデルを構築するために,textitgraphon autoencoder という新しいフレームワークを提案する。 線形グルーポン分解モデルはデコーダとして機能し、潜在表現を活用して誘導されたグルーポンを再構成する。
  論文  参考訳（メタデータ） (2021-05-29T08:11:40Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。 標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。 総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-08T19:48:19Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version [27.544219236164764]
  グラフ畳み込みネットワーク(GCN)はグラフ表現学習において広く使われている手法である。 サンプルグラフの埋め込みに基づいて異なるランダムグラフモデルを区別するGCNのパワーについて検討する。
  論文  参考訳（メタデータ） (2020-02-13T17:58:42Z)

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

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