注册| 登录

Grover 算法

2018-03-04

Grover 量子搜索算法由于其能够实现在未整理数据库中对满足条件的目标成功搜索,并使计算复杂度由经典搜索算法的image.png 降低为image.png,实现了数据检索的二次加速;同时,由于量子计算的并行性,使得受作用元素由经典计算的单个元素变化为全体参与运算元素,使得其从诞生之日起就在信息计算领域受到了广泛关注。1999年,Zalka 等人更是证明了 Grover 量子搜素算法为最优量子搜索算法。

 

近年来,学者们在如何优化 Grover 量子算法方面做了大量研究,取得了一些成果,比较典型的主要有以下三个方面:(1)通过改变一些步骤或是变换算子,来完成量子搜索算法的一般性改进;(2)通过改变运算算子的旋转相位,提高算法效率或者搜素成功率;(3)讨论了更一般的初始态幅值任意分布对量子搜索算法的影响,以及来解决一些诸如寻找中值、最小值或是解决冲突等特定问题。这些研究成果的提出,极大地丰富了 Grover 量子搜素算法。

 

但是,以上研究成果是建立在所有待检索元素重要性无差异基础上的。事实上,在很多情形下,目标元素间可能存在一定的重要性差别。本章基于目标重要性的差异,研究了迭代算子的构造,在此基础上提出基于固定加权系数的 Grover 搜索算法改进。进一步,提出了该方案在量子签名中的应用方案。


Grover 算法基本原理 

Grover 量子搜索算法实现在未整理的数据库中,在image.png 个数据的搜索空间中搜索符合给定条件 (image.png中的 x ) 的 image.png 个解,其基本的迭代过程如下: 

(1) 制备均匀量子比特。对寄存器 image.png的初态应用 Hadamard 变换 image.png,得到均匀几率幅叠加态:

image.png

其中,目标态是image.png;

(2) 应用 Oracle 过程,使目标态置反:

image.png

(3) 执行条件相移: 

image.png

(4) 执行步骤 (2)-(3) R 步:

image.png

式中,image.png为取距 x 最近的整实数。

(5) 测量寄存器image.png ,即可得到搜索问题的解。其中,步骤 (2) 和 (3) 作用之和是 Grover 迭代的核心,常被称为 Grover算子,即:

image.png


参考文献:

1. Zalka  C.Grover’s  quantum  searching  algorithm  is  optimal[J]  Phys.  Rev  A, 1999,60(4):2746-2751 

2. 周立志,李飞,郑宝玉.一种改进的 Grover 量子搜索算法[J].南京邮电大学学报:自然科学版,2011,32(2):27-30 

3. 马颖,“基于量子计算理论的优化算法研究”,西北工业大学博士学位论文(2014).

收藏 评论:0
没有ID?去注册 忘记密码? 已有账号,马上登陆

添加表情