論文の概要: Single Link Removal Perturbation in Szegedy Quantum Walk: from Graph Completeness Testing to Integrity Monitoring

• arxiv url: http://arxiv.org/abs/2607.19129v1
• Date: Tue, 21 Jul 2026 14:19:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-22 19:05:05.452491
• Title: Single Link Removal Perturbation in Szegedy Quantum Walk: from Graph Completeness Testing to Integrity Monitoring
• Title（参考訳）: ゼゲディ量子ウォークにおける単一リンク除去摂動:グラフ完全性試験から積分モニタリングまで
• Abstract要約: 興味の異常は、単一の通信リンクが消滅することである。 一つの無マークエッジの除去が関連するスペクトル量を通してどのように伝播するかを定量化する。 結果は、量子ウォークに基づくトポロジー整合性監視の理論的基礎と基本的なスケーリング限界の両方を提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a rigorous perturbative analysis of the Szegedy quantum walk search algorithm on the complete graph with marked nodes, when a specific anomaly is present in the graph. This is motivated by the problem of monitoring the integrity of dense trusted communication networks with a quantum-assisted procedure. The topology of these networks is modeled as a complete graph, and the anomaly of interest is the disappearance of a single communication link which represents the minimal and spectrally hardest structural defect to detect. Building on the graph-completeness testing algorithm framework, we quantify how the removal of a single unmarked-unmarked edge propagates through the relevant spectral quantities of the Szegedy quantum walk. Denoting by $n$ the total number of nodes of the graph and by $m$ the number of marked nodes, we prove that the perturbation to the transition matrix has spectral norm $Θ(1/n)$, and that the gap eigenvalue undergoes a strictly negative first-order shift for every $n$ and every number of marked nodes $m$, providing a formal proof of a conjecture from our completeness testing algorithm work; in the regime $m = Θ(n)$ relevant for the search algorithm, this shift has magnitude $Θ(1/n^2)$. The corresponding eigenphase shift satisfies $Δθ_\star = Θ(1/n^2)$ in the same regime. We establish that the rotation angle of the effective subspace under this perturbation is $O(1/n)$ for $m = Θ(n)$. Finally, we bound the change in success probability to $O(1/\sqrt{n})$ in this same regime of marked nodes, and show that this bound is dominated by the geometric misalignment of the effective subspace rather than by the spectral shift of the eigenphase. These results provide both the theoretical foundations and the fundamental scaling limits of quantum walk-based topology integrity monitoring under minimal structural perturbations.
• Abstract（参考訳）: 本稿では,Szegedy量子ウォーク探索アルゴリズムの厳密な摂動解析を行う。 これは、高密度信頼通信ネットワークの完全性を量子アシスト方式で監視する問題によって動機付けられている。 これらのネットワークのトポロジは完全なグラフとしてモデル化され、興味のある異常は、検出する最小かつスペクトル的に最も難しい構造欠陥を表す単一の通信リンクの消失である。 グラフ完全性試験アルゴリズムの枠組みに基づいて,Szegedy量子ウォークの関連するスペクトル量を通じて,1つの無マークエッジの除去がどのように伝播するかを定量化する。 グラフのノードの総数$n$とマークされたノードの数$m$によって、遷移行列への摂動はスペクトルノルム$((1/n)$を持ち、ギャップ固有値は、すべての$n$とマークされたノードの全ての数$m$に対して厳密に負の1次シフトを行い、我々の完全性テストアルゴリズムの予想の正式な証明を提供する。 対応する固有位相シフトは、同じ状態において$Δθ_\star = シュ(1/n^2)$を満たす。 この摂動の下での有効部分空間の回転角が$O(1/n)$ for $m = ...(n)$であることを確立する。 最後に、このマークされたノードの同じ状態において、成功確率の変化を$O(1/\sqrt{n})$に束縛し、この境界が固有位相のスペクトルシフトよりも実効部分空間の幾何学的不整合に支配されていることを示す。 これらの結果は、最小構造摂動下での量子ウォークに基づく位相整合性監視の理論的基礎と基本的なスケーリング限界の両方を提供する。

関連論文リスト

• Dimension-Free Polylogarithmic Quantum Shadow Tomography from Sequential Pretty-Good Measurements [42.01011095596403]
  サンプル複雑性を伴うシャドートモグラフィーの量子プロトコルを提案する。 提案手法はまず,一般的なシャドウ・トモグラフィー問題を有限アンサンブル推定問題に還元する。 得られた推定誤差の洗練されたテール解析により、すべての観測可能量に対する同時精度保証が得られる。
  論文  参考訳（メタデータ） (2026-08-06T17:51:13Z)
• Typical Output States of Monitored Random Clifford Circuits: A Graph-Theoretic Approach [9.397862194793996]
  本稿では,監視されたランダムクリフォード回路の典型的な出力状態への直接アクセスを可能にするグラフ状態ベースのフレームワークを開発する。 まず、大きな$N$の極限において、ランダム安定化状態のグラフ表現がアーズ-レーニランダムグラフアンサンブル$G(N,1/2)$に収束することを示す。 体積法相における1次元(1D)回路の監視のために、出力状態グラフに$G(N_mathrmsub,1/2)$という形の創発的な高密度部分グラフを明らかにする。
  論文  参考訳（メタデータ） (2026-08-04T04:19:07Z)
• The Marginal Problem for Density Operators [0.30079490585515334]
  局所還元密度作用素が所定のマルコフ構造を持つ大域量子状態に組み立てられるかを検討する。 この障害がトレース条件によって正確に捕捉されていることを証明します。 3量子ビットのパウリの例は、量子障害物が実であることを示している。
  論文  参考訳（メタデータ） (2026-05-19T07:06:54Z)
• On the Spectral theory of Isogeny Graphs and Quantum Sampling of Hard Supersingular Elliptic curves [0.0]
  確率の高いランダムなハード超特異楕円曲線をサンプリングする最初の証明可能な量子時間アルゴリズムを提案する。 我々のアルゴリズムはハッシュ関数や他の暗号プリミティブをセキュアにインスタンス化する。
  論文  参考訳（メタデータ） (2026-02-02T16:04:54Z)
• Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models [47.23316001059971]
  メッセージパッシングニューラルネットワーク(MPNN)は、グラフ基盤モデルのブロックを構築している。 MPNNは過密と過密に悩まされている。 ローカル構造に基づくメッセージパッシングを調整するためのtextbflocalアプローチを提案する。
  論文  参考訳（メタデータ） (2025-10-20T11:41:45Z)
• Quantum phase discrimination with applications to quantum search on graphs [0.0]
  本稿では,この課題に対して量子位相判別(QPD)という量子アルゴリズムを提案する。 QPDを用いることで、Li と Zur が提案するパスフィニングアルゴリズムのクエリ複雑性を低減できる。 グラフ上の量子探索に2つの応用を提案する。
  論文  参考訳（メタデータ） (2025-04-21T16:06:43Z)
• Asymptotic robustness of entanglement in noisy quantum networks and graph connectivity [46.44827993583994]
  リンクが騒々しい場合には,ネットワークのグローバルな絡み合い特性に関して,大きく異なる2つの挙動が生じることを示す。 特定の構成では、ノイズレベルが一定の閾値以下であれば、ネットワークは真のマルチパーティ・エンタングルメント(GME)を表示するが、他のGMEは、固定された非ゼロレベルのノイズに対してシステムサイズが十分大きい場合、洗い流される。
  論文  参考訳（メタデータ） (2024-11-19T15:01:50Z)
• Sensitivity of quantum walk to phase reversal and geometric perturbations: an exploration in complete graphs [0.0]
  主連結グラフ $G$ と二次連結グラフ $G'$ の統合から生じるグラフ構造上の量子ウォークのダイナミクスを解析する。 この幾何学的摂動が量子ウォークに基づく探索アルゴリズムの成功確率に与える影響について検討する。
  論文  参考訳（メタデータ） (2024-02-13T06:17:07Z)
• Understanding Heterophily for Graph Neural Networks [42.640057865981156]
  グラフニューラルネットワーク(GNN)における異方性パターンの影響に関する理論的理解について述べる。 分離性ゲインは、$l$の近隣分布の正規化距離によって決定されることを示す。 合成データと実世界のデータの両方の実験により、我々の理論の有効性が検証された。
  論文  参考訳（メタデータ） (2024-01-17T11:01:28Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  グラフ信号定常性の概念に依存するオフライン手法を提案する。 我々の検出器は、漸近的でない不等式オラクルの証拠を伴っている。
  論文  参考訳（メタデータ） (2020-06-18T15:51:38Z)
• S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs [16.96562173221624]
  有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。 特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。 崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
  論文  参考訳（メタデータ） (2020-05-15T21:14:22Z)

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

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