量子行走搜索算法中硬币算子作用分析

为研究基于不同标记硬币算子的搜索算法的性能,分别使用负的恒等算子I、Grover扩散算子D和量子Fourier变换算子F作为标记算子构造基于算子-I、-D和-F的搜索算法(SAI、SAD和SAF),采用数值仿真研究其在对称图和随机图上搜索多个目标时的性能,分析SAI和SAD在一步量子行走中的作用,并使用不重复量子行走研究Cayley树根节点上的状态转移情况.结果表明,SAI的成功概率曲线近似为正弦函数平方曲线,并且在稠密图上成功概率大于0.5;SAD在搜索多个不相邻目标时等价于SAI,而在搜索Johnson图和随机图上的混合顶点时成功概率曲线出现双峰;SAF搜索相邻顶点时的性能取决于目标顶点硬币空间的基中各向量的顺序.在迭代数为g的4-Cayley树上实现了根节点状态在2g步的周期性转移.

基于Grover硬币算子的量子行走在商图上的演化算子

商图是利用图的对称性分析量子行走算法的一种重要数学工具.量子行走在商图上的演化算子由移位算子和硬币算子构成.本文以构造的方式给出了Grover硬币算子在超立方体的商图上对应的矩阵形式,并给出了其正确性证明.由于商图上的移位算子可由原图上的移位算子直接导出,从而确定了使用Grover算子作为硬币的量子行走在商图上的演化算子.