論文の概要: W-state graphs: Structure and Algorithms

• arxiv url: http://arxiv.org/abs/2605.04855v1
• Date: Wed, 06 May 2026 12:52:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-07 18:41:07.818222
• Title: W-state graphs: Structure and Algorithms
• Title（参考訳）: W状態グラフ:構造とアルゴリズム
• Abstract要約: 量子フォトニクス実験のグラフ理論的表現から生じるエッジカラーグラフのクラスについて検討する。 W-state graphs: 半辺2-colouringを備えたマッチング付きグラフを紹介する。 我々の結果は、古典的なマッチング理論の中にW状態グラフをしっかりと配置し、理想化されたW状態を実現することができる構造を正確に記述する。
• 参考スコア（独自算出の注目度）: 1.1763194962402104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away physical amplitudes and phases, we introduce W-state graphs: matching-covered graphs equipped with a half-edge 2-colouring such that every perfect matching contains exactly one bichromatic edge and every vertex is incident with a red half-edge. Our main contribution is a complete structural characterization of W-state graphs. We show that a graph is a W-state graph if and only if each of its 3-connected components is a W-cone, a simple and rigid building block defined by a universal vertex and a factor-critical base. This characterization implies that no W-state graph is simple and yields a recognition algorithm running as fast as verifying whether a graph is matching-covered. We also show that the natural generalization to Dicke states encounters a complexity barrier: verifying one of the two Dicke state conditions is itself coNP-complete, resolving an open problem of Vardi and Zhang [IJCAI 2023]. Our results place W-state graphs firmly within classical matching theory and precisely delineate the combinatorial structures capable of realizing idealized W-states in the experiment-graph framework.
• Abstract（参考訳）: マルチパーティライトW状態を生成する量子フォトニクス実験のグラフ理論的表現から生じるエッジカラーグラフのクラスについて検討する。 物理振幅と位相を抽象化し、W状態グラフを導入する: 半エッジ2色付きマッチング被覆グラフは、全ての完全マッチングがちょうど1つの双色エッジを含み、全ての頂点は赤半エッジで入射する。 我々の主な貢献は、W状態グラフの完全な構造的特徴付けである。 グラフが W-状態グラフであることと、その3つの連結成分のそれぞれが W-錐、普遍頂点と因子クリティカル基底によって定義される単純で固い構成要素であることは同値である。 この特徴は、W状態グラフは単純ではなく、グラフがマッチング被覆されているかどうかの検証と同じくらい高速に実行される認識アルゴリズムが得られることを示唆している。 また、ディック状態への自然な一般化は複雑さの障壁に直面することを示し、2つのディック状態条件のうちの1つを検証することは、それ自体coNP完全であり、Vardi と Zhang [IJCAI 2023] の開問題を解決している。 この結果は古典的マッチング理論の中にW状態グラフをしっかりと配置し、実験グラフフレームワークで理想化されたW状態を実現することができる組合せ構造を正確に記述する。

関連論文リスト

• DiPhon: Diffusion on Graphons for Scalable Graph Generation [100.75398811422308]
  拡散モデルはグラフ生成の主要なパラダイムであり、分子設計のような領域に顕著な影響を与えている。 有限グラフ上のこれらのダイナミクスを模倣する離散化グラフレベルプロセスであるDiPhonを提案する。 我々は、DiPhonが連続グラノン過程によって引き起こされる限界分布の第一モーメントと正確に一致することを証明し、第二モーメントを閉形式差まで近似する。
  論文  参考訳（メタデータ） (2026-07-08T10:15:17Z)
• Symmetric and Antisymmetric Quantum States from Graph Structure and Orientation [0.0]
  グラフ状態が粒子置換の下で完全に対称であることは、基礎となるグラフが完備である場合に限る。 任意の向きが与えられた完全有向グラフは、奇数の四重項が完全に非対称な多粒子状態を生成することを示す。
  論文  参考訳（メタデータ） (2026-01-27T18:12:52Z)
• Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs [13.60873698530933]
  可換性構造を符号化するグラフ、すなわちフラストレーショングラフによって、グラフ理論と量子情報の間の自然なインターフェースを提供する。 このクラスを$hbar$-perfectと呼び、完全グラフと$hbar-perfectグラフのクラスを拡張します。 絡み合い検出のための効率的なスキーム,シャドウトモグラフィーの複雑さへの接続,厳密な不確実性関係,地中エネルギーの低い計算のための構成を見いだす。
  論文  参考訳（メタデータ） (2025-11-17T16:05:28Z)
• Real state transfer on edge perturbed graphs with generalized clusters [0.0]
  一般化クラスタを含むエッジ摂動グラフにおける実状態移動の存在について検討する。 中心的な観察は、特定の量子状態の進化は、基礎となるグラフの局所構造にのみ依存するということである。
  論文  参考訳（メタデータ） (2025-05-12T18:26:59Z)
• Distinguishing Graph States by the Properties of Their Marginals [0.0]
  局所ユニタリ(LU)下におけるグラフ状態の同値関係について検討する。 これらの不変量は、最大8キュービットまでの全てのグラフ状態の絡み合いクラスを一意に識別することを示す。 我々は、大きなグラフをより小さなグラフに凝縮することで機能するグラフ状態の局所クリフォード(LC)同値性をテストするツールを一般化する。
  論文  参考訳（メタデータ） (2024-06-14T12:03:10Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
  論文  参考訳（メタデータ） (2024-06-04T05:30:16Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。 我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。 我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
  論文  参考訳（メタデータ） (2022-05-30T13:20:26Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。 GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
  論文  参考訳（メタデータ） (2022-05-07T04:11:23Z)
• Residual2Vec: Debiasing graph embedding with random graphs [1.9280643035418397]
  本稿では,グラフの様々な構造バイアスをランダムグラフを用いてデバイアスするグラフ埋め込み法であるRess2vecを提案する。 この偏りがリンク予測やクラスタリング性能を改善するだけでなく、グラフ埋め込みにおける健全な構造特性を明示的にモデル化できることを実証する。
  論文  参考訳（メタデータ） (2021-10-14T18:24:11Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  ローカルノードの類似性と接続性、グローバル構造をトレードオフする教師なしグラフ埋め込みを導入する。 埋め込みは一般化されたグラフ Laplacian に基づいており、固有ベクトルは1つの表現においてネットワーク構造と近傍近傍の両方をコンパクトにキャプチャする。
  論文  参考訳（メタデータ） (2020-09-30T04:59:10Z)
• 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)
• Bridging Knowledge Graphs to Generate Scene Graphs [49.69377653925448]
  本稿では,2つのグラフ間の情報伝達を反復的に行う新しいグラフベースニューラルネットワークを提案する。 我々のグラフブリッジネットワークであるGB-Netは、エッジとノードを連続的に推論し、相互接続されたシーンとコモンセンスグラフのリッチでヘテロジニアスな構造を同時に活用し、洗練する。
  論文  参考訳（メタデータ） (2020-01-07T23:35:52Z)

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

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