論文の概要: Exponential speedups for quantum walks in random hierarchical graphs
- arxiv url: http://arxiv.org/abs/2307.15062v1
- Date: Thu, 27 Jul 2023 17:59:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-28 13:22:52.572434
- Title: Exponential speedups for quantum walks in random hierarchical graphs
- Title（参考訳）: ランダム階層グラフにおける量子ウォークの指数的高速化
- Authors: Shankar Balasubramanian, Tongyang Li, Aram Harrow
- Abstract要約: 量子ウォークを階層グラフのクラスに一般化する方法を示す。
これらのグラフ上の量子ウォークのヒット時間は、特定の乱れた強結合ハミルトニアンにおけるゼロモードの局在特性に関係している。
- 参考スコア（独自算出の注目度）: 6.896797484250303
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There are few known exponential speedups for quantum algorithms and these
tend to fall into even fewer families. One speedup that has mostly resisted
generalization is the use of quantum walks to traverse the welded-tree graph,
due to Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman. We show how to
generalize this to a large class of hierarchical graphs in which the vertices
are grouped into ``supervertices'' which are arranged according to a
$d$-dimensional lattice. Supervertices can have different sizes, and edges
between supervertices correspond to random connections between their
constituent vertices.
The hitting times of quantum walks on these graphs are related to the
localization properties of zero modes in certain disordered tight binding
Hamiltonians. The speedups range from superpolynomial to exponential, depending
on the underlying dimension and the random graph model. We also provide
concrete realizations of these hierarchical graphs, and introduce a general
method for constructing graphs with efficient quantum traversal times using
graph sparsification.
- Abstract（参考訳）: 量子アルゴリズムの指数的スピードアップは知られていないが、これらはさらに少ないファミリーに分類される傾向がある。
一般化に抵抗するスピードアップの1つは、Childs, Cleve, Deotto, Farhi, Gutmann, Spielman が溶接木グラフを横切るために量子ウォークを使うことである。
これを階層グラフの大規模なクラスに一般化する方法を示し、そこで頂点は$d$次元格子に従って配置される `supervertices' にグループ化される。
スーパーバーチスは異なるサイズを持ち、スーパーバーチス間のエッジは構成頂点間のランダム接続に対応する。
これらのグラフ上の量子ウォークのヒット時間は、特定の乱れた強結合ハミルトニアンにおけるゼロモードの局在特性と関連している。
スピードアップは、下層の次元とランダムグラフモデルによって、スーパーポリノミカルから指数関数まで様々である。
また,これらの階層グラフを具体的に実現し,グラフスカラー化を用いた効率的な量子トラバース時間を用いたグラフ構築法を提案する。
関連論文リスト
- Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs [5.173438526554426]
隣接リストのオラクルによるパスフィンディング問題に対して指数的量子古典的分離を可能にするグラフのクラスを見つける。
通常のヒマワリグラフに$s$-$t$の経路を求めるのに有効な量子アルゴリズムを提供するが、古典的アルゴリズムは指数関数的な時間を要する。
論文 参考訳（メタデータ） (2024-07-19T15:21:13Z) - Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。
同じ手法は他の1次元階層グラフにも適用できる。
論文 参考訳（メタデータ） (2024-04-30T11:45:49Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - A convergence time of Grover walk on regular graph to stationary state [0.0]
外部との相互作用を持つ有限グラフ上の量子ウォークモデルを考える。
正規グラフの高次化は、この量子ウォークモデルの収束速度を遅くすることを示す。
論文 参考訳（メタデータ） (2022-10-16T02:57:33Z) - Application of graph theory in quantum computer science [0.0]
連続時間量子ウォークモデルが非自明なグラフ構造に対して強力であることを示す。
CTQWで定義された量子空間探索は、様々な無向グラフでうまく機能することが証明されている。
この側面のスコープでは、複雑なグラフ構造に対しても量子スピードアップが観測されるかどうかを分析する。
論文 参考訳（メタデータ） (2021-09-27T12:07:25Z) - Search by Lackadaisical Quantum Walk with Symmetry Breaking [0.0]
量子ウォーク(quantum walk)は、離散時間で作られた量子ウォーク(quantum walk)の遅延バージョンである。
様々なグラフの空間探索を高速化するために使用されている。
論文 参考訳（メタデータ） (2021-08-31T14:08:40Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-06-19T13:09:44Z) - Fast Graph Attention Networks Using Effective Resistance Based Graph
Sparsification [70.50751397870972]
FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。
我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
論文 参考訳（メタデータ） (2020-06-15T22:07:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。