基于量子漫步的图形匹配算法进展与展望  

Development and Prospect of Graph Matching Algorithms Using Quantum Walk

作　　者：强晓刚[1] 吴俊杰[1] 周海芳[2] 

机构地区：[1]并行与分布处理国家重点实验室(国防科学技术大学),长沙410073 [2]国防科学技术大学计算机学院计算机科学与技术系,长沙410073

出　　处：《计算机研究与发展》2012年第S1期292-298,共7页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60921062;61003082)

摘　　要：图形匹配是图形研究中的重要问题,目前的经典算法受限于存储资源和计算复杂度,未能提供有效的解决方法.基于量子效应,将图形信息存储于量子比特,不仅能够极大减少存储资源的消耗,而且对量子比特进行操作可实现对存储信息的并行计算,从而为有效解决图形匹配问题提供了新的可能.量子漫步作为量子计算中的重要模型,是分析研究图形问题的有效工具.总结了量子计算的特点,介绍了量子漫步的2种模型并对二者进行了比较.然后对目前已有的基于量子漫步的图形匹配算法进行了介绍,对其算法思想、计算过程和优缺点进行了描述,同时还提出了相应的改进思路.在总结分析目前研究存在问题的基础上,探讨了今后的研究方向.图形匹配是图形研究中的重要问题,目前的经典算法受限于存储资源和计算复杂度,未能提供有效的解决方法.基于量子效应,将图形信息存储于量子比特,不仅能够极大减少存储资源的消耗,而且对量子比特进行操作可实现对存储信息的并行计算,从而为有效解决图形匹配问题提供了新的可能.量子漫步作为量子计算中的重要模型,是分析研究图形问题的有效工具.总结了量子计算的特点,介绍了量子漫步的2种模型并对二者进行了比较.然后对目前已有的基于量子漫步的图形匹配算法进行了介绍,对其算法思想、计算过程和优缺点进行了描述,同时还提出了相应的改进思路.在总结分析目前研究存在问题的基础上,探讨了今后的研究方向.

关 键 词：量子计算 图形匹配 量子漫步 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]