論文の概要: Of Shadows and Gaps in Spatial Search
- arxiv url: http://arxiv.org/abs/2204.04355v2
- Date: Tue, 30 Aug 2022 23:05:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 18:54:41.717553
- Title: Of Shadows and Gaps in Spatial Search
- Title（参考訳）: 空間探索における影とギャップ
- Authors: Ada Chan, Chris Godsil, Christino Tamon, Weichen Xie
- Abstract要約: 我々は、ハミンググラフやグラスマングラフのような距離正則グラフの族が最適空間探索を持つことを示す。
また、一定の忠実度を持つ空間探索の時間的下界も示し、これは完全忠実度に対するFarhiとGutmannによる境界を延長する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spatial search occurs in a connected graph if a continuous-time quantum walk
on the adjacency matrix of the graph, suitably scaled, plus a rank-one
perturbation induced by any vertex will unitarily map the principal eigenvector
of the graph to the characteristic vector of the vertex. This phenomenon is a
natural continuous-time analogue of Grover search. The spatial search is said
to be optimal if it occurs with constant fidelity and in time inversely
proportional to the shadow of the target vertex on the principal eigenvector.
Extending a result of Chakraborty et al. (Physical Review A, 102:032214, 2020),
we prove a simpler characterization of optimal spatial search. Based on this
characterization, we observe that some families of distance-regular graphs,
such as Hamming and Grassmann graphs, have optimal spatial search. We also show
a matching lower bound on time for spatial search with constant fidelity, which
extends a bound due to Farhi and Gutmann for perfect fidelity. Our elementary
proofs employ standard tools, such as Weyl inequalities and Cauchy determinant
formula.
- Abstract（参考訳）: 空間探索は、グラフの隣接行列上の連続時間量子ウォークが適切にスケールされ、任意の頂点によって引き起こされるランク1の摂動が、グラフの主固有ベクトルを頂点の標数ベクトルに一元的に写像するとき、連結グラフで発生する。
この現象はグローバー探索の自然な連続時間類似である。
空間探索は、一定の忠実性を持ち、時間内に主固有ベクトル上の目標頂点の影に反比例する場合に最適であると言われる。
Chakraborty et al. (Physical Review A, 102:032214, 2020) の結果を拡張し、最適な空間探索の簡易な特徴を証明した。
この特徴に基づいて、ハミンググラフやグラスマングラフのような距離正則グラフの族が最適空間探索を持つことを観察する。
また、一定の忠実度を持つ空間探索の時間的下界も示し、これは完全忠実度に対するFarhiとGutmannによる境界を延長する。
我々の初等証明は、ワイル不等式やコーシー行列式のような標準ツールを用いる。
関連論文リスト
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。
量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。
このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
論文 参考訳（メタデータ） (2024-07-01T06:09:19Z) - Graph Generation via Spectral Diffusion [51.60814773299899]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。
具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。
我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
論文 参考訳（メタデータ） (2024-02-29T09:26:46Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。
我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。
グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
論文 参考訳（メタデータ） (2023-11-29T12:48:33Z) - No Infinite Tail Beats Optimal Spatial Search [0.0]
無限に長い経路(または尾)が存在する場合でも、空間探索は完全なグラフで最適であることを示す。
検索アルゴリズムは、尾部が存在するかどうか、それに付随しているかどうかを知る必要がなくなる。
論文 参考訳（メタデータ） (2023-01-18T01:25:12Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - 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) - Deterministic spatial search using alternating quantum walks [0.0]
最適な量子ウォーク時間と頂点位相シフトの組に対して、構造化空間探索のための決定論的アルゴリズムが確立されていることを証明した。
これにより、同じグラフのクラスにおける元の空間探索アルゴリズムを改善し、50%の確率しか増幅できないことを示す。
この新たなフレームワークは、グラフ構造の他のファミリーに対する決定論的空間探索に容易に拡張できると期待されている。
論文 参考訳（メタデータ） (2021-04-08T14:32:48Z) - Robustness of Community Detection to Random Geometric Perturbations [16.575947847660778]
我々は、頂点間の接続が、潜在(かつ観測されていない)ランダムな幾何グラフによって摂動されるブロックモデルを考える。
目的は、スペクトル法がランダムグラフの存在(あるいはそうでない)に非依存であっても、この種のノイズに対して堅牢であることを証明することである。
論文 参考訳（メタデータ） (2020-11-09T10:15:40Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。