Framework for discrete-time quantum walks and a symmetric walk on a binary tree
Framework for discrete-time quantum walks and a symmetric walk on a binary tree
复制标题
离散时间量子行走和二叉树上对称行走的框架
DOI：
10.1103/physreva.84.032311
复制
发表时间：
2011
影响因子：
2.9
通讯作者：
Yevgeniy Kovchegov
中科院分区：
文献类型：
--
作者：
Z. Dimcovic;Dan Rockwell;Ian Milligan;R. Burton;Thinh Nguyen;Yevgeniy Kovchegov
我们提出了一个离散时间量子漫步的框架，其动机是经典的带记忆的随机漫步。我们给出了经典的带记忆2行走的具体表示，这是基于这一表示的。该框架不需要硬币空间，除了一元性外，对进化算子没有任何约束，是其他方法的统一。作为例子，我们在半无限二叉树上构造了对称的离散时间量子游动。计算了作为时间和树中初始水平n的函数的根部振幅的母函数，得到了振幅的渐近和完整的数值解。与二叉树上经典对称随机游动的宽峰分布的指数衰减尾部相反，它显示出一个尖锐的干扰峰和一个幂函数尾部。概率峰值比经典行走的概率峰值大几个数量级(已经在小n处)。量子漫步显示出在n中的多项式算法加速比经典漫步，基于数据的强烈趋势，我们猜测其量级为2/3。
We formulate a framework for discrete-time quantum walks, motivated by classical random walks with memory. We present a specific representation of the classical walk with memory 2, on which this is based. The framework has no need for coin spaces, it imposes no constraints on the evolution operator other than unitarity, and is unifying of other approaches. As an example we construct a symmetric discrete-time quantum walk on the semi-infinite binary tree. The generating function of the amplitude at the root is computed in closed form, as a function of time and the initial level n in the tree, and we find the asymptotic and a full numerical solution for the amplitude. It exhibits a sharp interference peak and a power-law tail, as opposed to the exponentially decaying tail of a broadly peaked distribution of the classical symmetric random walk on a binary tree. The probability peak is orders of magnitude larger than it is for the classical walk (already at small n). The quantum walk shows a polynomial algorithmic speedup in n over the classical walk, which we conjecture to be of the order 2/3, based on strong trends in data.