论文标题
随机和量子步行的非结构化搜索
Unstructured Search by Random and Quantum Walk
论文作者
论文摘要
在$ n $元素的未排序列表中找到条目的任务，著名的是$ o（n）$ Queries to Oracle的古典计算机和$ o（\ sqrt {n}）$ Queries $ Queries使用Grover的算法查询量子计算机。通过查询Oracle来搜索完整的图形或全面网络以搜索明显的顶点，这与搜索完整的图形或全网络相对应。在本教程中，我们得出了如何以彻底和教学的方式解决这个问题，从而为如何使用随机和量子步行来搜索空间区域，从而提供了离散和连续的（经典）随机步行和量子步行。一些结果已经知道，但是许多结果是新的。对于大$ n $，随机步行汇合到相同的演变，都需要$ n \ ln（1/ε）$达到$1-ε$的成功概率。相比之下，离散的量子步行偶然地采用$π\ sqrt {n}/2 \ sqrt {2} $ timeSteps以达到$ 1/2 $的成功概率，而连续的量子步行步行则需要$π\ sqrt {n} n}/2 $ $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $。
The task of finding an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$ queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large $N$, the random walks converge to the same evolution, both taking $N \ln(1/ε)$ time to reach a success probability of $1-ε$. In contrast, the discrete-time quantum walk asymptotically takes $π\sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$, while the continuous-time quantum walk takes $π\sqrt{N}/2$ time to reach a success probability of $1$.
