离散时间量子随机行走搜索算法在无向图上的应用

摘要

量子行走得益于概率幅的叠加特性，可同时出现在多条路径中，使其能以平方式乃至指数级别的速度加速扩散所携带的量子信息。文章基于无向图G=(V,E)结构，从离散时间量子随机行走(Discrete Time Quantum Walk, DTQW)搜索算法特性出发，运用幺正变换的硬币算符与迁移算符，构建了DTQW搜索算法步骤框图，在此基础上，应用SKW搜索算法对4节点无向图中的标记节点态进行搜索，通过态塌缩的观测，实现以1/4概率化读取出目标节点。研究结果表明，当有n个足够大的量子系统，并保持彼此之间的强纠缠性时，量子随机行走可以过渡到经典随机行走。文章还详细讨论了DTQW搜索算法实现左右同移的二次加速搜索机制。

关键词

量子信息 / 离散型量子随机行走 / 无向图 / 量子算法