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

Studies of DTQW search algorithm in undirected graph

作　　者：濮荣强 黄玮[1] 居水荣[1] PU Rong-qiang;HUANG Wei;JU Shui-rong(School of Microelectronics,Jiangsu Vocational College of Information Technology,Wuxi 214153,China)

机构地区：[1]江苏信息职业技术学院微电子学院,江苏无锡214153

出　　处：《广州大学学报(自然科学版)》2025年第1期50-55,共6页Journal of Guangzhou University:Natural Science Edition

基　　金：江苏省高校优秀科技创新团队--高频集成电路开发及应用资助项目(苏教科(2021)1号)。

摘　　要：量子行走得益于概率幅的叠加特性,可同时出现在多条路径中,使其能以平方式乃至指数级别的速度加速扩散所携带的量子信息。文章基于无向图G=(V,E)结构,从离散时间量子随机行走(Discrete Time Quantum Walk,DTQW)搜索算法特性出发,运用幺正变换的硬币算符与迁移算符,构建了DTQW搜索算法步骤框图,在此基础上,应用SKW搜索算法对4节点无向图中的标记节点态进行搜索,通过态塌缩的观测,实现以1/4概率化读取出目标节点。研究结果表明,当有n个足够大的量子系统,并保持彼此之间的强纠缠性时,量子随机行走可以过渡到经典随机行走。文章还详细讨论了DTQW搜索算法实现左右同移的二次加速搜索机制。Quantum walks benefit from the superposition property of probability amplitudes,allowing them to appear on multiple paths simultaneously,thereby achieving quadratic or even exponential acceleration in the diffusion of quantum information.This study focuses on the discrete-time quantum walk(DTQW)search algorithm within the framework of an undirected graph G=(V,E).By employing unitary transformations of coin and shift operators,a stepwise framework for the DTQW search algorithm is constructed.The SKW search algorithm of DTQW is specifically applied to searching for the marked node states in a 4-node undirected graph.Through state collapse observation,the target node is retrieved probabilistically with a success rate of 1/4.Results indicate that when n sufficiently large quantum systems maintain strong entanglement,quantum walks can transition to classical random walks.The paper further elaborates on the quadratic speedup mechanism of the DTQW search algorithm under bidirectional migration conditions.

关 键 词：量子信息 离散型量子随机行走 无向图 量子算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]