論文の概要: Spatial Search via Memoryless Walk with Selfloop
- arxiv url: http://arxiv.org/abs/2204.09076v1
- Date: Tue, 19 Apr 2022 18:04:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-16 08:48:08.143611
- Title: Spatial Search via Memoryless Walk with Selfloop
- Title(参考訳): 自己ループを用いたメモリレスウォークによる空間探索
- Authors: Peter H{\o}yer and Janet Leahy
- Abstract要約: 二次元格子上に一意にマークされた角を見つけることができるメモリレスウォークを提示する。
私たちのウォークは最小限のメモリ、$O(sqrtN log N)$ walk演算子のアプリケーションを使用し、マークされたコーナーをエラー確率を消し去ることで出力する。
我々はこの空間を特徴付け、その結果、我々の無記憶歩行が、確率的に近づいている成功と共に目立った角を生み出すことを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The defining feature of memoryless quantum walks is that they operate on the
vertex space of a graph, and therefore can be used to produce search algorithms
with minimal memory. We present a memoryless walk that can find a unique marked
vertex on a two-dimensional grid. Our walk is based on the construction
proposed by Falk, which tessellates the grid with squares of size $2 \times 2$.
Our walk uses minimal memory, $O(\sqrt{N \log N})$ applications of the walk
operator, and outputs the marked vertex with vanishing error probability. To
accomplish this, we apply a selfloop to the marked vertex - a technique we
adapt from interpolated walks. We prove that with our explicit choice of
selfloop weight, this forces the action of the walk asymptotically into a
single rotational space. We characterize this space and as a result, show that
our memoryless walk produces the marked vertex with a success probability
asymptotically approaching one.
- Abstract(参考訳): メモリレス量子ウォークの定義上の特徴は、グラフの頂点空間で動くため、最小限のメモリで探索アルゴリズムを生成することができることである。
2次元グリッド上にユニークなマークされた頂点を見つけることができるメモリレスウォークを示す。
私たちのウォークは、falkが提案した2ドル2セントの四角い格子をテッセルする構造に基づいている。
私たちのウォークは最小限のメモリ、$O(\sqrt{N \log N})$ walk演算子の応用を使い、マークされた頂点をエラー確率を消し去る。
これを達成するために、私たちはマークされた頂点(補間された歩行から適応するテクニック)に自己ループを適用する。
自己ループ重みの明示的な選択により、これは歩行の動作を漸近的に単一の回転空間に強制することを証明する。
この空間を特徴付け、その結果、私たちの無記憶歩行は、漸近的に近づいている成功確率でマークされた頂点を生成することを示す。
関連論文リスト
- Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
私たちは、歩行者が頂点から端までホップできる連続時間量子ウォークのバージョンを定義します。
両部グラフ上の空間探索アルゴリズムをハミルトン版の修正により解析する。
論文 参考訳(メタデータ) (2022-06-07T15:10:18Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳(メタデータ) (2022-03-27T20:22:17Z) - Feedback-assisted quantum search by continuous-time quantum walks [58.720142291102135]
本稿では,連続的な測定とフィードバックを補助する量子ウォークを用いて,目標ノードのサイクルグラフ上の量子探索に対処する。
特に、我々のプロトコルは、ウォーカーを所望のターゲットノードに駆動することができる。
論文 参考訳(メタデータ) (2022-01-12T16:59:53Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳(メタデータ) (2021-12-23T17:57:49Z) - Search by Lackadaisical Quantum Walk with Symmetry Breaking [0.0]
量子ウォーク(quantum walk)は、離散時間で作られた量子ウォーク(quantum walk)の遅延バージョンである。
様々なグラフの空間探索を高速化するために使用されている。
論文 参考訳(メタデータ) (2021-08-31T14:08:40Z) - 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) - ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and
Gradient Accumulation [106.04777600352743]
微分可能なアーキテクチャサーチ(DARTS)は、スーパーネット全体がメモリに格納されているため、メモリコストが大幅に低下する。
シングルパスのDARTSが登場し、各ステップでシングルパスのサブモデルのみを選択する。
メモリフレンドリーだが、計算コストも低い。
RObustifying Memory-Efficient NAS (ROME) と呼ばれる新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-11-23T06:34:07Z) - 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) - Spatial Pyramid Based Graph Reasoning for Semantic Segmentation [67.47159595239798]
セマンティックセグメンテーションタスクにグラフ畳み込みを適用し、改良されたラプラシアンを提案する。
グラフ推論は、空間ピラミッドとして構成された元の特徴空間で直接実行される。
計算とメモリのオーバーヘッドの利点で同等のパフォーマンスを実現しています。
論文 参考訳(メタデータ) (2020-03-23T12:28:07Z) - Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
量子ウォーク(quantum walk)は、グラフ上の離散時間(離散時間)の量子ウォークである。
完全グラフ、離散トーラス、サイクル、正規完全二部グラフの空間探索を改善することができる。
この仮説を支持する数値シミュレーションをいくつか提示する。
論文 参考訳(メタデータ) (2020-02-26T00:10:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。