论文标题
通过自动步行与Selfloop进行空间搜索
Spatial Search via Memoryless Walk with Selfloop
论文作者
论文摘要
无内存量子步行的定义特征是它们在图形的顶点空间上操作，因此可用于生成具有最小内存的搜索算法。我们提出了一个无记忆的步行，可以在二维网格上找到独特的标记顶点。我们的步行是基于Falk提出的构造，该建筑用$ 2 \ times 2 $的正方形将网格带到了网格中。我们的步行使用最小内存，$ o（\ sqrt {n \ log n}）$ walk Operator的应用程序，并以消失的错误概率输出标记的顶点。为了实现这一目标，我们将自循环应用于标记的顶点 - 我们从插值步行中适应的技术。我们证明，通过明确选择自圈重量，这迫使行走渐近地进入一个旋转空间。我们表征了这个空间，结果表明我们的无内存步行会产生标记的顶点，而成功的概率渐近地接近一个。
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.
