Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (15): 43-48.

Previous Articles     Next Articles

Analysis of hitting time for open quantum walk

LIN Yunguo, CAI Shuiying   

  1. College of Computer and Information Sciences, Fujian Agriculture and Forestry University, Fuzhou 350002, China
  • Online:2016-08-01 Published:2016-08-12

开放量子行走的击中时分析

林运国,蔡水英   

  1. 福建农林大学 计算机与信息学院,福州 350002

Abstract: As a basic tool of quantum searching algorithms, quantum walk is an important reseach subject. Meanwhile, hitting time is a standard which measures a speed about quantum walk reaching some target vertex. It has been widely used to study quantum algorithms. In an open quantum environment, four definitions of hitting time are introduced for open quantum walk:single hitting time, parallel hitting time, average hitting time and limit hitting time. These four hitting times are distinguished. The related facts show that the first two are used to describe a case of locally reaching the target vertex while the latter two are used to describe a case of reaching the target vertex from an overall and limitation situation. For homogenous open quantum walk, non-homogenous open quantum walk and nested open quantum walk, their calculations of four hitting times are respectively given.

Key words: quantum algorithm, quantum walk, open quantum system, hitting time

摘要: 作为量子搜索算法研究的一个基本工具,量子行走是一个重要研究课题。同时,击中时是衡量量子行走到达某一目标顶点速度的标准,对量子算法研究具有广泛的应用。在开放量子环境下,给出开放量子行走的四种击中时定义:单次击中时、并行击中时、平均击中时和极限击中时。区分四种击中时,说明前两种用于刻画开放量子行走局部到达目标顶点,而后两种从全局和极限角度分析目标顶点到达情况。针对同质开放量子行走、异质开放量子行走和嵌套开放量子行走,分别给出四种击中时具体计算。

关键词: 量子算法, 量子行走, 开放量子系统, 击中时