論文の概要: Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk
- arxiv url: http://arxiv.org/abs/2112.03744v1
- Date: Tue, 7 Dec 2021 15:00:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-05 07:50:05.866810
- Title: Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk
- Title（参考訳）: 離散時間量子ウォークによるジョンソングラフの空間探索
- Authors: Hajime Tanaka, Mohamed Sabri, Renato Portugal
- Abstract要約: 本稿では、ジョンソングラフ上の空間探索問題に量子ウォークモデルを用いて対処する。
すべての固定径に対して、成功確率は、$pisqrt N/(2sqrt 2)$ steps を取った後に1/2$である。
すべての固定径に対して、成功確率は$pisqrt N/ (2sqrt)$ ステップを踏んだ後に1/2$であることを示した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The spatial search problem aims to find a marked vertex of a finite graph
using a dynamic with two constraints: (1) The walker has no compass and (2) the
walker can check whether a vertex is marked only after reaching it. This
problem is a generalization of unsorted database search and has many
applications to algorithms. Classical algorithms that solve the spatial search
problem are based on random walks and the computational complexity is
determined by the hitting time. On the other hand, quantum algorithms are based
on quantum walks and the computational complexity is determined not only by the
number of steps to reach a marked vertex, but also by the success probability,
since we need to perform a measurement at the end of the algorithm to determine
the walker's position. In this work, we address the spatial search problem on
Johnson graphs using the coined quantum walk model. Since Johnson graphs are
vertex- and distance-transitive, we have found an invariant subspace of the
Hilbert space, which aids in the calculation of the computational complexity.
We have shown that, for every fixed diameter, the asymptotic success
probability is $1/2$ after taking $\pi\sqrt N/(2\sqrt 2)$ steps, where $N$ is
the number of vertices of the Johnson graph.
- Abstract（参考訳）: 空間探索問題は,(1)歩行者がコンパスを持たず,(2)歩行者が到達後のみ頂点がマークされているかどうかを確認できるという2つの制約を持つ力学を用いて,有限グラフのマーク付き頂点を見つけることを目的としている。
この問題は、非分類データベース探索の一般化であり、アルゴリズムに多くの応用がある。
空間探索問題を解く古典的なアルゴリズムはランダムウォークに基づいており、計算複雑性は打上げ時間によって決定される。
一方、量子アルゴリズムは量子ウォークに基づいており、計算複雑性は、マークされた頂点に到達するためのステップの数だけでなく、ウォーカーの位置を決定するためにアルゴリズムの最後に測定を行う必要があるため、成功確率によっても決定される。
本研究では,ジョンソングラフ上の空間探索問題を,量子ウォークモデルを用いて解決する。
ジョンソングラフは頂点と距離推移性を持つので、ヒルベルト空間の不変部分空間を発見し、計算複雑性の計算に役立てる。
任意の固定直径に対して、漸近的成功確率は$\pi\sqrt n/(2\sqrt 2)$ステップをとれば1/2$であり、ここで$n$はジョンソングラフの頂点数である。
関連論文リスト
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Universal approach to deterministic spatial search via alternating
quantum walks [2.940962519388297]
本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。
我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
論文 参考訳（メタデータ） (2023-07-30T05:14:19Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳（メタデータ） (2021-12-23T17:57:49Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
論文 参考訳（メタデータ） (2021-11-17T10:04:44Z) - Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
連続時間量子ウォークによるジョンソングラフ上の空間探索は、固定径毎に1ドル程度の成功確率を持つ下界の$pisqrtN/2$を達成することを示す。
この証明は数学的に厳密であり、他のグラフクラスにも利用できる。
論文 参考訳（メタデータ） (2021-08-04T12:16:24Z) - 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) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳（メタデータ） (2020-05-13T14:53:36Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。