Grover量子搜索算法改进 (2).ppt

文档介绍：Grover 量子搜索算法的改进
2018/10/10
之
陶兴亮、王乐
使用局部扩散算子的量子搜索算法
2003年,英国伯明翰大学Younes提出了一种使用局部扩散算子的搜索算法,该算法中算子的均值反转操作仅在系统的一个局部子空间上执行。理论推导和实验证明,该算法比基本Grover算法具有更优良的性能,尤其适用于多目标搜索。对于在N个元素中寻找M个目标的搜索,%。
一步迭代搜索
对于拥有个元素的无序数据搜索,一步迭代搜索的实施过程可分为4步,如下图所示。
….
……
N量子比特
1 qubit
工作空间
测量
具体步骤如下:
(1) 准备存储器。准备一个所有量子位处于|0>态的n+1位作为Oracle算子的工作空间。此时系统状态为
(2)寄存器初始化。对于前n位量子位施加H门变换,将系统状态变为个状态的均匀叠加态,即
(3)应用Oracle识别搜索问题的解,并将识别结果存储在附加量子比特中,即
(4)局部扩散。首先定义一个局部扩散算子Y,将其用于n+1位量子比特系统中,该算子可描述为
其中向量|0>的长度为
下面考虑将Y应用于具有P个基本状态的量子系统
的情况。为便于叙述,该量子系统可以重写为
其中当k为偶数时,当k为奇数时。应用Y后该量子系统变为
其中是子空间的幅度均值。上述结果表明,应用局部扩散算子Y的结果只是在子空间上执行均值翻转,而对于子空间,仅仅只是改变幅度的符号。
记为所有搜索问题的解集, 为所有非解的集合,由d式描述的系统状态可以描述为
将Y作用于后,系统状态更新为
记均值为,经计算上式各系数为:
(5) 测量。经过一步迭代搜索之后,搜索的成功概率为
算法原理
当Oracle算子和局部扩算算子Y作用于系统状态时,就构成了迭代算法。如前所述,系统在一次迭代之后的状态如e式,经过二次迭代后,系统更新情况如下:
应用Oracle算子后,将具有概率幅的目标态概率幅交换后,系统可描述为
应用局部扩散算子Y作用后系统状态变为
记,经过计算上式中各系数分别为
同理,三次迭代后系统状态变为