論文の概要: The Quantum Walk Characteristic Polynomial Distinguishes All Strongly Regular Graphs of Prime Orde

• arxiv url: http://arxiv.org/abs/2604.01507v1
• Date: Thu, 02 Apr 2026 00:40:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.177243
• Title: The Quantum Walk Characteristic Polynomial Distinguishes All Strongly Regular Graphs of Prime Orde
• Title（参考訳）: 量子ウォーク特性のポリノミアルは、プライムオードの強い正則グラフを識別する
• Authors: Diego Roldan,
• Abstract要約: このとき、$U_G$ は$G$ の量子ウォーク演算子であり、同じ順序の強い正則グラフのクラス内の同型まで$G$ を完全に決定する。 結果として、グラフ同型は、ババイ・ババイの一般準多項式アルゴリズムに頼ることなく、量子スペクトルを用いて、このクラス内で時間的に決定可能である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Let $G$ be a strongly regular graph of prime order $p$ with connection degree $k \geq 6$. We prove that the \emph{quantum walk characteristic polynomial} $χ_q(G,λ) \coloneqq \det(λI - U_G)$, where $U_G$ is the coined quantum walk operator on $G$, completely determines $G$ up to isomorphism within the class of strongly regular graphs of the same order. The proof proceeds in three steps. First, we show that $U_G$ block-diagonalizes under the discrete Fourier transform over $\Z_p$, yielding $p$ blocks $U_G^{(j)}$ of size $k \times k$. Second, we prove an explicit formula \[ χ_q\!\bigl(U_G^{(j)}, λ\bigr) = (λ-1)^{(k-2)/2}(λ+1)^{(k-2)/2} \!\left(λ^2 - \tfrac{2\widehat{A}_G(j)}{k}\,λ+ 1\right), \] from which the Fourier coefficient $\widehat{A}_G(j)$ is recovered as the unique real part of an eigenvalue of $U_G^{(j)}$ distinct from $\pm 1$. Third, the inverse discrete Fourier transform recovers the connection set $S$ of $G$, and Turner's theorem (1967) identifies $G$ up to isomorphism. As a consequence, graph isomorphism is decidable in polynomial time within this class using the quantum walk spectrum, without resorting to the general quasi-polynomial algorithm of Babai (2016).
• Abstract（参考訳）: G$ を素数次数 $p$ の強い正則グラフとし、接続次数 $k \geq 6$ とする。 ここで、$U_G$ は$G$ の量子ウォーク作用素であり、同じ順序の強い正則グラフのクラス内の同型まで$G$ を完全に決定する。 証明は3段階で進む。 まず、$U_G$ ブロック対角化が $\Z_p$ 上の離散フーリエ変換の下で行われ、$p$ ブロック $U_G^{(j)} サイズ $k \times k$ となることを示す。 第二に、明示的な公式 \[ >_q\! \bigl(U_G^{(j)}, λ\bigr) = (λ-1)^{(k-2)/2}(λ+1)^{(k-2)/2} \! \left(λ^2 - \tfrac{2\widehat{A}_G(j)}{k}\,λ+ 1\right), \] からフーリエ係数 $\widehat{A}_G(j)$ が$U_G^{(j)}$ の固有値の唯一の実部として回収される。 第三に、逆離散フーリエ変換は接続集合 $S$ of $G$ を復元し、ターナーの定理 (1967) は同型まで$G$を識別する。 その結果、グラフ同型は、ババイ(2016)の一般準多項式アルゴリズムに頼ることなく、量子ウォークスペクトルを用いて、このクラス内の多項式時間で決定可能である。

関連論文リスト

• Tripartite information of free fermions: a universal entanglement coefficient from the sine kernel [51.56484100374058]
  自由フェルミオンの3分割情報I_3を3つの隣接する幅wに分割した2次元格子上で検討する。 g(z) は z* = 1.329 +/- 0.001: で一意な零点を持ち、k_F w z* のモードは相互情報の独占に反する。 z ln z の領域法則項と z2 の項の2つの正確なキャンセルは、I_3 の組み合わせに固有のものである。
  論文  参考訳（メタデータ） (2026-03-03T15:39:35Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。 A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。 A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
  論文  参考訳（メタデータ） (2025-09-15T14:26:11Z)
• Quantum geometric Wigner construction for $D(G)$ and braided racks [0.0]
  有限群の量子双対 D(G)=Bbb C(G)rtimes Bbb C G$ は量子コンピューティングの北エフモデルにおいて重要な役割を果たす。 我々は、そのモデルの準粒子である既知構成を、Bbb R1,3$の通常のポアンカー群に対するウィグナー構成と厳密に類似した幾何学的方法で解釈する。
  論文  参考訳（メタデータ） (2024-07-16T15:21:28Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。 境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。 治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2022-08-12T15:05:07Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。 偏光理論への我々の結果の即時適用について述べる。
  論文  参考訳（メタデータ） (2022-05-30T18:01:34Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。 これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
  論文  参考訳（メタデータ） (2021-10-11T05:07:50Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。 我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
  論文  参考訳（メタデータ） (2021-04-26T15:03:08Z)
• Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
  すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。 f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
  論文  参考訳（メタデータ） (2020-10-23T19:21:28Z)
• Emergent universality in critical quantum spin chains: entanglement Virasoro algebra [1.9336815376402714]
  エンタングルメントエントロピーとエンタングルメントスペクトルは、拡張多体系における量子エンタングルメントの特徴付けに広く用いられている。 シュミットベクトル $|v_alpharangle$ は境界 CFT のヴィラソロ代数の実現に対応する創発的普遍構造を示す。
  論文  参考訳（メタデータ） (2020-09-23T21:22:51Z)

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

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