论文标题
三角形和蜂窝2D网格上的量子量子散步
Lackadaisical quantum walks on triangular and honeycomb 2D grids
论文作者
论文摘要
在典型模型中，一个离散的时间固定量子步行搜索的运行时间为$ O（\ sqrt {n} \ log {n}）$，用于2D矩形，三角形和蜂窝网格。众所周知，对于2D矩形网格，可以使用几种不同的技术将运行时间提高到$ O（\ sqrt {n \ log {n}}）$。这样的技术之一是为每个顶点添加一个重量$ 4/n $的自循环（即使步行不足）。 在本文中，我们采用缺乏的方法来对三角形和蜂窝2D网格进行量子步行搜索。我们表明，对于两种类型的网格，分别为三角形和蜂窝网格的添加重量$ 6/n $和$ 3/n $的自循环，导致$ O（\ sqrt {n \ log {n}}）$运行时间。
In the typical model, a discrete-time coined quantum walk search has the same running time of $O(\sqrt{N} \log{N})$ for 2D rectangular, triangular and honeycomb grids. It is known that for 2D rectangular grid the running time can be improved to $O(\sqrt{N \log{N}})$ using several different techniques. One of such techniques is adding a self-loop of weight $4/N$ to each vertex (i.e. making the walk lackadaisical). In this paper we apply lackadaisical approach to quantum walk search on triangular and honeycomb 2D grids. We show that for both types of grids adding a self-loop of weight $6/N$ and $3/N$ for triangular and honeycomb grids, respectively, results in $O(\sqrt{N \log{N}})$ running time.
