Finding paths with quantum walks or quantum walking through a maze
Finding paths with quantum walks or quantum walking through a maze
复制标题
通过量子行走或量子行走穿过迷宫寻找路径
DOI：
10.1103/physreva.96.032323
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Daniel Koch
中科院分区：
文献类型：
--
作者：
Daniel Reitzner;M. Hillery;Daniel Koch
我们表明，可以利用量子行走找到从一个标记顶点到另一个标记顶点的路径。在由$M$个星型结构连接成链的特定情形中，能够在$O(M\sqrt{N})$步内找到从第一个星型结构到最后一个星型结构的路径，其中$N$是每个星型结构的轮辐数量。首先，我们给出一个分析结果，表明从一个相位调制的高度叠加初始态出发，可以在$O(M\sqrt{N}\log M)$步内找到路径。接下来，我们通过证明当从最后已知位置出发，并在$O(\sqrt{N})$步内搜索下一个连接从而使整体效率达到$O(M\sqrt{N})$时，路径的恢复也可以通过一系列连续搜索来实现，进而提高了这种效率。对于这个结果，我们使用了针对长度为链两倍的星型环所获得的解析解。
We show that it is possible to use a quantum walk to find a path from one marked vertex to another. In the specific case of $M$ stars connected in a chain, one can find the path from the first star to the last one in $O(M\sqrt{N})$ steps, where $N$ is the number of spokes of each star. First we provide an analytical result showing that by starting in a phase-modulated highly superposed initial state we can find the path in $O(M\sqrt{N}\log M)$ steps. Next, we improve this efficiency by showing that the recovery of the path can also be performed by a series of successive searches when we start at the last known position and search for the next connection in $O(\sqrt{N})$ steps leading to the overall efficiency of $O(M\sqrt{N})$. For this result we use the analytical solution that can be obtained for a ring of stars of double the length of the chain.