論文の概要: Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact

• arxiv url: http://arxiv.org/abs/2407.02530v1
• Date: Mon, 1 Jul 2024 06:09:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-04 18:43:42.962469
• Title: Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Title（参考訳）: グラフ上の量子空間探索、状態移動、一様サンプリングの統一:単純かつ正確に
• Authors: Qingwen Wang, Ying Jiang, Lvzhou Li,
• Abstract要約: 本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。 量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。 このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
• 参考スコア（独自算出の注目度）: 2.871419116565751
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This article presents a novel and succinct algorithmic framework via alternating quantum walks, unifying quantum spatial search, state transfer and uniform sampling on a large class of graphs. Using the framework, we can achieve exact uniform sampling over all vertices and perfect state transfer between any two vertices, provided that eigenvalues of Laplacian matrix of the graph are all integers. Furthermore, if the graph is vertex-transitive as well, then we can achieve deterministic quantum spatial search that finds a marked vertex with certainty. In contrast, existing quantum search algorithms generally has a certain probability of failure. Even if the graph is not vertex-transitive, such as the complete bipartite graph, we can still adjust the algorithmic framework to obtain deterministic spatial search, which thus shows the flexibility of it. Besides unifying and improving plenty of previous results, our work provides new results on more graphs. The approach is easy to use since it has a succinct formalism that depends only on the depth of the Laplacian eigenvalue set of the graph, and may shed light on the solution of more problems related to graphs.
• Abstract（参考訳）: 本稿では, 量子ウォークの交互化, 量子空間探索の統合, 状態移動, および多種類のグラフ上の一様サンプリングによる新しい, 簡潔なアルゴリズムフレームワークを提案する。 この枠組みを用いることで、グラフのラプラシアン行列の固有値がすべて整数であることを仮定して、すべての頂点に対する正確な一様サンプリングと任意の2つの頂点間の完全状態移動を達成することができる。 さらに、グラフが頂点推移性(vertex-transitive)であるなら、決定論的量子空間探索(deterministic quantum space search)を達成でき、確実にマークされた頂点を見つけることができる。 対照的に、既存の量子探索アルゴリズムは一般にある種の失敗の確率を持つ。 グラフが完全二部グラフのような頂点推移的でない場合でも、決定論的空間探索を得るためにアルゴリズムの枠組みを調整することができ、それによってその柔軟性が示される。 これまでの結果の統一と改善に加えて、私たちの研究はより多くのグラフに新たな結果をもたらしています。 このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式主義を持ち、グラフに関連するより多くの問題の解に光を当てることができるため、簡単に利用できる。

関連論文リスト

• Graph Generation via Spectral Diffusion [51.60814773299899]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。 具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。 我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。 我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
  論文  参考訳（メタデータ） (2023-07-30T05:14:19Z)
• Quantum walk based state transfer algorithms on the complete M-partite graph [0.0]
  量子ウォーク探索と状態伝達アルゴリズムについて検討し,各パーティションに$N$頂点を持つ完全$M$パーティイトグラフに着目した。 送信側と受信側が異なるパーティションにある場合、そのアルゴリズムは大きなグラフに対してユニティに近づく忠実度で成功することを示す。 しかし、送信側と受信側が同じパーティションにある場合、忠実度は正確には1つには達しない。
  論文  参考訳（メタデータ） (2022-12-01T14:52:49Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。 ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。 我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
  論文  参考訳（メタデータ） (2022-10-15T08:01:08Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• Deterministic spatial search using alternating quantum walks [0.0]
  最適な量子ウォーク時間と頂点位相シフトの組に対して、構造化空間探索のための決定論的アルゴリズムが確立されていることを証明した。 これにより、同じグラフのクラスにおける元の空間探索アルゴリズムを改善し、50%の確率しか増幅できないことを示す。 この新たなフレームワークは、グラフ構造の他のファミリーに対する決定論的空間探索に容易に拡張できると期待されている。
  論文  参考訳（メタデータ） (2021-04-08T14:32:48Z)
• Quantum walk-based search algorithms with multiple marked vertices [0.0]
  量子ウォークは量子アルゴリズムを開発するための強力なツールである。 我々は、Szegedyの量子ウォークに基づく従来の解析手法を拡張した。 2次元格子とハイパーキューブ上の量子ウォークに基づく2つの例は、我々の方法の詳細を示している。
  論文  参考訳（メタデータ） (2021-03-23T22:57:07Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
  量子ウォーク(quantum walk)は、グラフ上の離散時間(離散時間)の量子ウォークである。 完全グラフ、離散トーラス、サイクル、正規完全二部グラフの空間探索を改善することができる。 この仮説を支持する数値シミュレーションをいくつか提示する。
  論文  参考訳（メタデータ） (2020-02-26T00:10:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。