Fugu-MT 論文翻訳(概要): Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism

論文の概要: Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism

arxiv url: http://arxiv.org/abs/2609.20678v1
Date: Thu, 17 Sep 2026 16:49:26 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-20 08:55:54.379746
Title: Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism
Title（参考訳）: 量子グラフ準同型の関連スキームと不決定性におけるシュライバー・デルサーテ剛性
Abstract要約: 古典的距離関係スキームから導かれるグラフの族によってパラメタ化される量子準同型問題の再完全性を証明する。量子多型を非コンテクスト性(non-contextuality of quantum polymorphisms)とするスペクトル法を開発した。
参考スコア（独自算出の注目度）: 2.4510222356323004
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, $q$-Kneser graphs, and the complements of Johnson, Grassmann, and Hamming graphs. Our proof develops a spectral method for establishing non-contextuality of quantum polymorphisms. It combines an equality analysis of Roberson's bound on the projective packing number in terms of Schrijver's theta with a structural argument inspired by Erdős-Ko-Rado theory.
Abstract（参考訳）: 古典的距離関係スキームから導かれるグラフの族によってパラメタ化される量子準同型問題の再完全性を証明する。例えば、Kneser graphs、$q$-Kneser graphs、Johnson、Grassmann、Hamming graphsなどがある。量子多型を非コンテクスト性(non-contextuality of quantum polymorphisms)とするスペクトル法を開発した。これは、シュライバーのゼータという観点からの射影パッキング数上のロバーソンの境界の等式解析と、エルデシュ=コ=ラド理論に着想を得た構造的議論を結びつける。

関連論文リスト

Cycle-Structure Generating Functions for Special Breakpoint Graphs [0.0]
ブレークポイントグラフは、その交互周期がゲノム間の関係をコードする比較ゲノム学に由来する。本研究では、置換に関連する3色のブレークポイントグラフの制約クラスについて検討し、2つの極端族に対してサイクル修正された生成関数を開発する。結果は、レニイエントロピー展開に入るリードモーメントと定階モーメントを決定づけ、射影平面の寄与は有限の大きさの定数補正を与える。
論文参考訳（メタデータ） (2026-08-31T13:29:37Z)
Graph automorphisms to obtain Clifford symmetries in open and closed qudit models [33.81183023775755]
一般キューディシステム上でクリフォード対称性を得るアルゴリズムを提供する。クリフォード対称性のグラフ自己同型表現は開量子系に拡張可能であることを示す。
論文参考訳（メタデータ） (2026-05-28T18:00:10Z)
Entanglement of multi-qubit quantum graph states and studies structural properties of tripartite graphs with quantum programming [0.0]
重み付き三部グラフを表す多ビット交絡量子状態を構築する方法を提案する。任意の三部グラフ構造に対応する多ビット状態に対する絡み合い距離の式を得る。
論文参考訳（メタデータ） (2026-04-30T13:18:04Z)
A Theory of Random Graph Shift in Truncated-Spectrum vRKHS [26.195791008324495]
本稿では,ランダムグラフ生成レンズによる領域シフトの下でのグラフ分類の理論を開発する。我々は、同じランダムグラフモデル(RGM)を共有するクラス内グラフと、RGM成分の変化によって引き起こされる領域シフトについて考察する。
論文参考訳（メタデータ） (2026-02-27T10:19:57Z)
Flock: A Knowledge Graph Foundation Model via Learning on Random Walks [26.568227939080703]
知識グラフ(KG)におけるゼロショットリンク予測の問題について検討する。ランダムウォークを反復的にサンプリングし、記録プロトコルを介してシーケンスにエンコードし、それらをシーケンスモデルで埋め込み、学習プーリングを通じてノードと関係の表現を集約するKGFMであるFlockを提案する。 Flockは、現在のKGFMが失敗する新たな診断データセットPetalsを完璧に解決し、さまざまなドメインから54KGのエンティティおよびリレーショナル予測タスクにおける最先端のパフォーマンスを達成する。
論文参考訳（メタデータ） (2025-10-01T23:09:46Z)
The Generalized Skew Spectrum of Graphs [42.70026220176376]
我々は、同型不変でよりリッチなグラフ構造を埋め込むことのできる新しいグラフ不変量のクラスを導入する。一般化保存をこの族に適用することにより、スキュースペクトルの表現性を同じ計算コストで改善する。
論文参考訳（メタデータ） (2025-05-29T16:18:01Z)
Families of isospectral and isoscattering quantum graphs [0.0]
胚グラフの概念とM-函数形式は、アイソスペクトルおよびアイソ散乱グラフの大きな族を構成するために用いられる。導入された形式主義は、散逸したグラフにも拡張可能であることを実証する。
論文参考訳（メタデータ） (2025-05-22T12:54:52Z)
Knowledge Graph Reasoning with Relational Directed Graph [40.555874504438506]
文学における関係経路に基づく手法は、強く、解釈可能で、帰納的推論能力を示す。重なり合う関係経路からなる関係有向グラフ(r-digraph)を新たに導入する。本稿では,グラフニューラルネットワークの変種であるRED-GNNを提案し,GNNの変種を用いてRelational Digraphを学習する。
論文参考訳（メタデータ） (2021-08-13T03:27:01Z)
A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文参考訳（メタデータ） (2021-02-16T08:36:19Z)
Quantum mechanics of bipartite ribbon graphs: Integrality, Lattices and Kronecker coefficients [0.0]
ヒルベルト空間上の可解量子力学系を、固定数のエッジを持つ二部格子リボングラフで定義する。ヤング図形の3重のクロネッカー係数の平方は、リボングラフの格子内の部分格子の次元と等しいことが示されている。量子超越性とその計算複雑性理論への応用を探求する手段として、これらの量子系の仮想量子実現・シミュレーションのための非消滅的クロネッカー係数を検出する実験を概説する。
論文参考訳（メタデータ） (2020-10-08T15:18:46Z)

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