論文の概要: Multimarked Spatial Search by Continuous-Time Quantum Walk
- arxiv url: http://arxiv.org/abs/2203.14384v3
- Date: Wed, 17 Jan 2024 14:45:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 22:27:19.374764
- Title: Multimarked Spatial Search by Continuous-Time Quantum Walk
- Title（参考訳）: 連続時間量子ウォークによる多点空間探索
- Authors: Pedro H. G. Lug\~ao, Renato Portugal, Mohamed Sabri, Hajime Tanaka
- Abstract要約: 任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum-walk-based spatial search problem aims to find a marked vertex
using a quantum walk on a graph with marked vertices. We describe a framework
for determining the computational complexity of spatial search by
continuous-time quantum walk on arbitrary graphs by providing a recipe for
finding the optimal running time and the success probability of the algorithm.
The quantum walk is driven by a Hamiltonian derived from the adjacency matrix
of the graph modified by the presence of the marked vertices. The success of
our framework depends on the knowledge of the eigenvalues and eigenvectors of
the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained
from the roots of the determinant of a real symmetric matrix $M$, the
dimensions of which depend on the number of marked vertices. The eigenvectors
are determined from a basis of the kernel of $M$. We show each step of the
framework by solving the spatial searching problem on the Johnson graphs with a
fixed diameter and with two marked vertices. Our calculations show that the
optimal running time is $O(\sqrt{N})$ with an asymptotic probability of
$1+o(1)$, where $N$ is the number of vertices.
- Abstract（参考訳）: 量子ウォークに基づく空間探索問題は、マークされた頂点を持つグラフ上の量子ウォークを用いてマークされた頂点を見つけることを目的としている。
本稿では,任意のグラフ上での連続時間量子ウォークによる空間探索の計算量を決定するためのフレームワークについて,最適な実行時間とアルゴリズムの成功確率を求めるためのレシピを提供する。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトニアンによって駆動される。
我々のフレームワークの成功は、隣接行列の固有値と固有ベクトルの知識に依存する。
その後、ハミルトニアンのスペクトルは実対称行列の行列式 $m$ の根から得られ、その次元はマークされた頂点の数に依存する。
固有ベクトルは、カーネル $m$ に基づいて決定される。
ジョンソングラフ上の空間探索問題を固定された直径と2つのマークされた頂点で解くことにより,フレームワークの各ステップを示す。
我々の計算では、最適な実行時間は 1+o(1)$ の漸近確率を持つ $o(\sqrt{n})$ であり、ここで $n$ は頂点の数である。
関連論文リスト
- Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
私たちは、歩行者が頂点から端までホップできる連続時間量子ウォークのバージョンを定義します。
両部グラフ上の空間探索アルゴリズムをハミルトン版の修正により解析する。
論文 参考訳（メタデータ） (2022-06-07T15:10:18Z) - A framework for optimal quantum spatial search using alternating
phase-walks [0.0]
我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。
様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
論文 参考訳（メタデータ） (2021-09-29T11:16:52Z) - The average search probabilities of discrete-time quantum walks [0.0]
まず、正則グラフに対して、遷移行列のスペクトルは拡張グラフの重み付き隣接行列によって決定されることを示す。
次に、距離正則グラフ上での平均探索確率を検討し、その部分グラフの隣接行列の式を求める。
特に、(1) 完全グラフの族、または (2) 強い正則グラフ、または (3) 距離正則グラフの固定パラメータ $d$, 可変値 $k$, 可変サイズ $n$ に対して、平均探索確率は、値が無限に近づくにつれて 1/4$ に近づく。
論文 参考訳（メタデータ） (2021-08-22T18:53:22Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - 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) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Quantum walk-based search algorithms with multiple marked vertices [0.0]
量子ウォークは量子アルゴリズムを開発するための強力なツールである。
我々は、Szegedyの量子ウォークに基づく従来の解析手法を拡張した。
2次元格子とハイパーキューブ上の量子ウォークに基づく2つの例は、我々の方法の詳細を示している。
論文 参考訳（メタデータ） (2021-03-23T22:57:07Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳（メタデータ） (2020-05-13T14:53:36Z) - Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
量子ウォーク(quantum walk)は、グラフ上の離散時間(離散時間)の量子ウォークである。
完全グラフ、離散トーラス、サイクル、正規完全二部グラフの空間探索を改善することができる。
この仮説を支持する数値シミュレーションをいくつか提示する。
論文 参考訳（メタデータ） (2020-02-26T00:10:38Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。