朱皖宁,陈汉武

(1.金陵科技学院软件工程学院,江苏南京 211199；2.东南大学计算机科学与工程学院,江苏南京210096;3.东南大学计算机网络和信息集成教育部重点实验室,江苏南京210096)

迭代次数自适应的Grover算法

朱皖宁1,2,陈汉武2,3

(1.金陵科技学院软件工程学院,江苏南京 211199；2.东南大学计算机科学与工程学院,江苏南京210096;3.东南大学计算机网络和信息集成教育部重点实验室,江苏南京210096)

本文提出了利用相位门自动控制Grover搜索算法迭代次数的算法.Grover搜索算法最终得到目标分量的概率非常依赖于酉算子迭代的次数.迭代次数的计算依赖于目标分量的数量.因此当目标分量数未知时,该方法无法以高概率测量到目标分量.在以往的解决方案中需要较高的Oracle查询复杂度才能以一定概率得到目标分量的数量.本文提出了一种通过判断叠加态相位正负性,可自动控制Grover搜索算法迭代次数的方法.只需要添加一个判断相位的门电路,仅增加一次Oracle查询次数就可以精确的在最优迭代次数时停止Grover搜索算法,在搜索空间较小时可比原算法有更大的概率得到目标分量.

Grover搜索算法；相位正负性；自动控制

1 引言

本文提出了一种基于判定X基下(|±〉={|0〉±|1〉}) 特定分量相位的正负性的新Grover算法.新算法只需要多一个可逆门和一次Oracle调用,就可以在目标分量未知时仍然可以以最高的概率测量出目标分量.

2 准备知识

Grover搜索算法是由一组酉算子的迭代运算组成.可以简单的由下图表示[9]:

当n个量……