論文の概要: Search by Lackadaisical Quantum Walk with Symmetry Breaking
- arxiv url: http://arxiv.org/abs/2108.13856v3
- Date: Mon, 29 Nov 2021 15:08:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-16 16:10:13.600328
- Title: Search by Lackadaisical Quantum Walk with Symmetry Breaking
- Title(参考訳): 対称性の破れを伴う欠如量子ウォークによる探索
- Authors: Jacob Rapoza, Thomas G. Wong
- Abstract要約: 量子ウォーク(quantum walk)は、離散時間で作られた量子ウォーク(quantum walk)の遅延バージョンである。
様々なグラフの空間探索を高速化するために使用されている。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The lackadaisical quantum walk is a lazy version of a discrete-time, coined
quantum walk, where each vertex has a weighted self-loop that permits the
walker to stay put. They have been used to speed up spatial search on a variety
of graphs, including periodic lattices, strongly regular graphs, Johnson
graphs, and the hypercube. In these prior works, the weights of the self-loops
preserved the symmetries of the graphs. In this paper, we show that the
self-loops can break all the symmetries of vertex-transitive graphs while
providing the same computational speedups. Only the weight of the self-loop at
the marked vertex matters, and the remaining self-loop weights can be chosen
randomly, as long as they are small compared to the degree of the graph.
- Abstract(参考訳): 量子ウォーク(quantum walk)は、離散時間で作られた量子ウォークの遅延版で、各頂点には、歩行者を維持するための重み付き自己ループがある。
それらは、周期格子、強い正則グラフ、ジョンソングラフ、ハイパーキューブを含む様々なグラフの空間探索を高速化するために使われてきた。
これらの先行研究において、自己ループの重みはグラフの対称性を保った。
本稿では,自己ループが頂点遷移グラフのすべての対称性を破り,計算速度が同じであることを示す。
マークされた頂点における自己ループの重みのみが問題であり、残りの自己ループ重みはグラフの次数に比べて小さい限りランダムに選択できる。
関連論文リスト
- Exponential speedups for quantum walks in random hierarchical graphs [6.896797484250303]
量子ウォークを階層グラフのクラスに一般化する方法を示す。
これらのグラフ上の量子ウォークのヒット時間は、特定の乱れた強結合ハミルトニアンにおけるゼロモードの局在特性に関係している。
論文 参考訳(メタデータ) (2023-07-27T17:59:58Z) - Limits, approximation and size transferability for GNNs on sparse graphs
via graphops [44.02161831977037]
我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。
我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
論文 参考訳(メタデータ) (2023-06-07T15:04:58Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳(メタデータ) (2021-12-08T08:23:37Z) - Application of graph theory in quantum computer science [0.0]
連続時間量子ウォークモデルが非自明なグラフ構造に対して強力であることを示す。
CTQWで定義された量子空間探索は、様々な無向グラフでうまく機能することが証明されている。
この側面のスコープでは、複雑なグラフ構造に対しても量子スピードアップが観測されるかどうかを分析する。
論文 参考訳(メタデータ) (2021-09-27T12:07:25Z) - Equivalent Laplacian and Adjacency Quantum Walks on Irregular Graphs [0.0]
連続時間量子ウォーク(英: continuous-time quantum walk)は、離散空間におけるシュル・オーディンガー方程式によって進化する粒子である。
しかし、いくつかの物理系では、ハミルトニアンは代わりに隣接行列に比例する。
論文 参考訳(メタデータ) (2021-07-12T16:59:06Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - Space-Time Correspondence as a Contrastive Random Walk [47.40711876423659]
我々は,ビデオから構築した時空間グラフにおけるリンクの予測として対応をキャストした。
ペアの類似性がランダムウォークの遷移確率を定義する表現を学習する。
我々は、エッジドロップアウトと呼ばれる手法と、テスト時の自己教師付き適応が、オブジェクト中心の対応の転送をさらに改善することを示した。
論文 参考訳(メタデータ) (2020-06-25T17:56:05Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳(メタデータ) (2020-05-13T14:53:36Z) - Analysis of Lackadaisical Quantum Walks [0.0]
不連続な量子ウォークは、それぞれに自己ループを加えて得られる遅延ランダムウォークの量子アナログである。
我々は、欠如した量子ウォークがユニークなマークを見つけることができることを解析的に証明した。
一定の成功の確率を持つ、通常の局所的な弧-推移グラフの脊椎動物
打つ時間より2倍速い
論文 参考訳(メタデータ) (2020-02-26T00:40:25Z) - Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
量子ウォーク(quantum walk)は、グラフ上の離散時間(離散時間)の量子ウォークである。
完全グラフ、離散トーラス、サイクル、正規完全二部グラフの空間探索を改善することができる。
この仮説を支持する数値シミュレーションをいくつか提示する。
論文 参考訳(メタデータ) (2020-02-26T00:10:38Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。