論文の概要: Marked vertex search on disordered graphs with Rosenzweig-Porter phases
- arxiv url: http://arxiv.org/abs/2608.00224v1
- Date: Fri, 31 Jul 2026 19:14:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:24.55174
- Title: Marked vertex search on disordered graphs with Rosenzweig-Porter phases
- Title（参考訳）: Rosenzweig-Porter相をもつ乱グラフ上のマーク付き頂点探索
- Abstract要約: 量子探索アルゴリズムは、古典的なアルゴリズムよりも優れていることが知られているが、障害の存在下でのそれらの振る舞いは、ほとんど解明されていない。
可変エルゴディック,非エルゴディック拡張,局所化位相のランダムな行列アンサンブルに障害を導入する。
これらの結果は、グラフ上のランダム行列障害と連続時間量子ウォークサーチの性能の間に直接的かつ定量的なリンクを確立する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Quantum marked vertex search algorithms are known to outperform their classical counterparts, yet their behavior in the presence of disorder remains largely unexplored. Here, we address this gap by studying marked vertex search on disordered random graphs. To introduce disorder, we implement the Rosenzweig-Porter (RP) model, a random matrix ensemble with tunable ergodic, non-ergodic extended, and localized phases, on Erdős-Rényi (ER) graphs. This produces a doubly random system where ER graph connectivity randomizes which interactions exist, while RP disorder controls their strength and `on-site' potentials, providing a two-parameter framework to study quantum dynamics on disordered networks. First, we show that the characteristic Wigner-Dyson-to-Poisson spectral crossover of the RP ensemble survives under graph constraints across the sparse-to-dense range, and we derive an analytical estimate for the finite-size localization boundary that shifts systematically with the graph edge probability $p$, consistent with a resonant-hybridization argument. Thereafter, using this disordered graph ensemble, we study the marked vertex search problem and find that search performance tracks the underlying quantum phase directly. Counterintuitively, the ergodic phase, despite supporting fast transport, yields lower success probability than the localized phase, which achieves high success probability at the cost of significantly longer search times. These results establish a direct and quantitative link between random matrix disorder on graphs and the performance of continuous-time quantum walk search, and suggest that disorder, rather than being merely an obstacle, can be exploited as a tunable parameter in quantum search protocols.
- Abstract（参考訳）: 量子マーク付き頂点探索アルゴリズムは、古典的なアルゴリズムよりも優れていることが知られているが、障害の存在下でのそれらの振る舞いは、ほとんど探索されていない。
ここでは、乱数グラフ上で有意な頂点探索をすることで、このギャップに対処する。
障害を導入するために、エルゴディック、非エルゴディック拡張、局所化位相を持つランダム行列アンサンブルであるRosenzweig-Porter (RP) モデルをエルデシュ・レーニ(ER)グラフ上に実装する。
これにより、ERグラフ接続がどの相互作用が存在するかをランダム化し、RP障害がその強度と「オンサイト」ポテンシャルを制御し、乱れたネットワーク上の量子力学を研究するための2パラメータフレームワークを提供する。
第一に、RPアンサンブルのウィグナー・ダイソン・ツー・ポアソンスペクトルクロスオーバー特性がスパース・トゥ・デンス領域のグラフ制約の下で残存していることを示し、共振-ハイブリダイゼーションの議論と一致してグラフエッジ確率$p$と体系的に変化する有限サイズの局所化境界について解析的推定を導出する。
その後、この乱れたグラフアンサンブルを用いて、マークされた頂点探索問題を調べ、探索性能が基礎となる量子位相を直接追跡することを発見した。
対意的に、エルゴード相は高速輸送をサポートするが、局所化相よりも成功確率が低く、探索時間が非常に長いコストで高い成功確率が得られる。
これらの結果は、グラフ上のランダム行列障害と連続時間量子ウォークサーチの性能との間に直接的かつ定量的な関連性を確立し、障害であるだけでなく、量子サーチプロトコルのチューナブルパラメータとして利用することができることを示唆している。
関連論文リスト
- Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks [2.8427946758947304]
伝搬ステップ毎に独立なガウスノイズを注入するグラフニューラルネットワークについて検討する。
隠れ表現が幾何学的にエルゴード的なマルコフ連鎖を形成し、一意な不変確率測度を持つことを証明する。
以上の結果から,過密症と闘うメカニズムとして,持続的摂動が根本的に異なることが明らかとなった。
論文 参考訳（メタデータ） (2026-07-30T13:21:18Z) - Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
本稿では,グラフ畳み込みフィルタが生成するノイズ測定から有向ネットワークを推定する問題に対処する。
また、上記のステップを交互に交互に組み合わせて、サンプルの複雑さを向上する結合グラフフィルタとトポロジー同定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-06-25T18:25:57Z) - Solvable Random Unitary Dynamics in a Disordered Tomonaga-Luttinger Liquid [0.48342038441006796]
本稿では, ガウス前方散乱障害を伴う友長・ラッティンガー液体のフレーム電位のクローズドフォーム式を導出する。
ランダム場XXZスピン鎖を特定の微視的実現として、ハイゼンベルク強磁性点付近で最強のランダム性が得られることを示す。
我々は、アナログ量子シミュレーションプラットフォームにおいて、アルゴリズム設計に直接的な意味を持たせることなく、ギャップのない全フェーズで結果を検証した。
論文 参考訳（メタデータ） (2026-04-28T18:00:01Z) - Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
連続時間量子ウォーク(CTQW)に基づく最小頂点被覆(MVC)問題に対する新しい量子アルゴリズムを提案する。
この枠組みでは、グラフ上の量子ウォーカーのコヒーレントな伝播は、その構造特性を状態振幅に符号化する。
我々は,CTQWに基づくアルゴリズムが優れた近似比を一貫して達成し,ネットワークトポロジに関して顕著な堅牢性を示すことを示す。
論文 参考訳（メタデータ） (2025-12-02T17:04:57Z) - Learning Time-Varying Graphs from Incomplete Graph Signals [1.7430416823420511]
グラフから欠落したデータを出力する問題を解くために,効率的な交互方向乗算アルゴリズムを開発した。
提案したADMMスキームが収束し,定常点を導出することを示す。
論文 参考訳（メタデータ） (2025-10-19T11:12:13Z) - ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection [84.0718034981805]
我々はAnomaly-Denoized Autoencoders for Graph Anomaly Detection (ADA-GAD)という新しいフレームワークを導入する。
第1段階では,異常レベルを低減したグラフを生成する学習自由な異常化拡張法を設計する。
次の段階では、デコーダは元のグラフで検出するために再訓練される。
論文 参考訳（メタデータ） (2023-12-22T09:02:01Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳（メタデータ） (2020-05-13T14:53:36Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。