李 萌 尚 云

1(中国科学院数学与系统科学研究院 北京 100190) 2(中国科学院大学数学科学学院 北京 100049) 3(中国科学院数学与系统科学研究院国家数学与交叉科学中心 北京 100190) 4(中国科学院数学与系统科学研究院管理决策与信息系统重点实验室 北京 100190)

量子游走是经典随机游走在量子世界的对应物，它描述了微观世界中粒子的随机演化过程.经典随机游走本身应用十分广泛，比如k-SAT问题[1]、图像分割问题[2]、图匹配算法[3-4]等.量子游走也有广泛的用途：实现通用量子计算[5-8]；完成量子通讯协议[9-11]；制备纠缠量子态[12]等.另外，由于量子纠缠、量子干涉和量子非定域性，量子游走可以更快地搜索目标标记点，因此量子游走可以用来设计量子算法，像搜索标记点问题[13-16]、元素区分问题[17]、搜索三角形问题[18]等.当前基于量子游走的量子模拟或展示各种量子游走模型自身性质的实验已经在许多不同的物理系统上进行了实施，比如光子[19]、离子阱[20]、超导处理器[21]等.量子游走包含离散时间量子游走[22]和连续时间量子游走[23]，这里我们主要研究离散时间量子游走.

量子游走可以定义在任意给定的图上，其中一维圆是一种最为基础且常见的图，它可以作为实现大规模量子网络的一个基本模块.对于圆上的量子游走，许多学者也已经进行了广泛研究[24-26].

量子相干起源于量子叠加原理，它不仅可以描述量子信息处理的状态演变过程，而且可以反映和解释量子力学中的许多关……