論文の概要: Sensitivity of quantum walk to phase reversal and geometric
perturbations: an exploration in complete graphs
- arxiv url: http://arxiv.org/abs/2402.08243v1
- Date: Tue, 13 Feb 2024 06:17:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 16:16:06.761904
- Title: Sensitivity of quantum walk to phase reversal and geometric
perturbations: an exploration in complete graphs
- Title（参考訳）: 位相反転と幾何学的摂動に対する量子ウォークの感度:完全グラフの探索
- Authors: Taisuke Hosaka, Renato Portugal, Etsuo Segawa
- Abstract要約: 主連結グラフ $G$ と二次連結グラフ $G'$ の統合から生じるグラフ構造上の量子ウォークのダイナミクスを解析する。
この幾何学的摂動が量子ウォークに基づく探索アルゴリズムの成功確率に与える影響について検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In this paper, we analyze the dynamics of quantum walks on a graph structure
resulting from the integration of a main connected graph $G$ and a secondary
connected graph $G'$. This composite graph is formed by a disjoint union of $G$
and $G'$, followed by the contraction of a selected pair of vertices creating a
cut vertex $v^*$ and leading to a unique form of geometric perturbation. Our
study focuses on instances where $G$ is a complete graph $K_N$ and $G'$ is a
star graph $S_m$. The core of our analysis lies in exploring the impact of this
geometric perturbation on the success probability of quantum walk-based search
algorithms, particularly in an oracle-free context. Despite initial findings
suggesting a low probability of locating the perturbed vertex $v^*$, we
demonstrate that introducing a phase reversal to the system significantly
enhances the success rate. Our results reveal that with an optimal running time
and specific parameter conditions, the success probability can be substantially
increased. The paper is structured to first define the theoretical framework,
followed by the presentation of our main results, detailed proofs, and
concluding with a summary of our findings and potential future research
directions.
- Abstract（参考訳）: 本稿では,主連結グラフ $g$ と二次連結グラフ $g'$ の統合によるグラフ構造上の量子ウォークのダイナミクスを分析する。
この合成グラフは、g$ と $g'$ の合同和によって形成され、次に選択された一対の頂点が切断された頂点 $v^*$ を生成し、幾何学的摂動の一意的な形式へと導く。
我々の研究は、$G$ が完全グラフ $K_N$ であり、$G'$ がスターグラフ $S_m$ であるような場合に焦点を当てる。
我々の分析の核心は、量子ウォークに基づく探索アルゴリズムの成功確率、特にオラクルのない文脈におけるこの幾何学的摂動の影響を探ることにある。
初回所見では摂動頂点が$v^*$と低い可能性が示唆されたが, システムに位相反転を導入することで成功率を大幅に向上させることを示した。
その結果、最適実行時間と特定のパラメータ条件により、成功確率が大幅に増加することが判明した。
論文は,まず理論的枠組みを定義し,続いて本研究の主な成果の提示,詳細な証明を行い,その結果と今後の研究方向性をまとめてまとめる。
関連論文リスト
- Generalization of Geometric Graph Neural Networks [84.01980526069075]
幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。
我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。
最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
論文 参考訳（メタデータ） (2024-09-08T18:55:57Z) - Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
大規模なランダムクロネッカーグラフの隣接性は分解可能であることを示す。
本稿では,鍵グラフパラメータを推論するデノワーズ・アンド・ソルブの手法を提案する。
論文 参考訳（メタデータ） (2023-06-14T13:09:38Z) - Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。
幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。
次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
論文 参考訳（メタデータ） (2023-05-05T14:04:52Z) - Hierarchical cycle-tree packing model for $K$-core attack problem [0.0]
ここでは、この挑戦的な最適化問題に対して、階層的なサイクルツリーパッキングモデルを導入している。
統計物理学のレプリカ対称キャビティ法を用いて,このモデルを解析する。
関連する階層的サイクルツリー誘導攻撃(tt hCTGA)は、通常のランダムグラフに対するほぼ最適な攻撃解を構築することができる。
論文 参考訳（メタデータ） (2023-03-02T06:47:33Z) - Matching Correlated Inhomogeneous Random Graphs using the $k$-core
Estimator [5.685589351789462]
我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。
相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
論文 参考訳（メタデータ） (2023-02-10T18:21:35Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based
Vertex Embeddings [0.7366405857677227]
ランダムウォークに基づく埋め込み手法の理論解析を行う。
いくつかの弱い仮定の下では、コーポラはランダムウォークの個数の極限$N to infty$と、ランダムウォークの2つの極限$N$と各ランダムウォークの長さ$Ltoinfty$の両方に収束する。
論文 参考訳（メタデータ） (2021-07-21T11:23:04Z) - Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。
p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。
sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
論文 参考訳（メタデータ） (2021-01-29T21:49:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。