基于量子Grover算法的MIMO-OFDM系统信号检测技术的研究 第5页
图2.3  Grover算法的图解法表示
从图2.3中可以看出，每经过一次Grover迭代，变换后的量子态矢量和原矢量相比，向 轴转过 角, 在 轴上的投影，即目标态的概率幅逐渐变大。
2.2.2 Grover算法的迭代次数及模拟实现
设 与 轴的初始角度 ，经 次迭代后，可得到如下的表达式。
系统终态表示为：   (2.2.8)                         
现在对寄存器进行测量，以 分量前的系数的平方作为概率输出目标解，获得正确解得几率为： (2.2.9)
从上式可以看出，由于目标态概率幅随迭代次数 的增加呈周期性变化，所以并不是说迭代次数越多，现在设：若 的系数等于0表示搜索失败的概率为0，而搜索得到正确解的概率为1，效果最佳。我们可以通过 和 的关系得到获得正确解所需的最小迭代次数。
文献[19]证明了最佳的迭代步数为：          (2.2.10)  
其中 floor 是朝负无穷大方向取整。
当 时，可以得到最佳迭代次数为：                    (2.2.11)
现在设搜索目标解的个数 ，量子比特位数为 ，搜索数据库空间大小 ，对式(2.2.11)结果取整，即可得到最佳迭代次数 ，而且其最佳迭代次数与 属于同一数量级，即计算复杂度满足 关系。
图2.4   Grover搜索最佳迭代次数与量子比特位数的关系
2.2.3 Grover算法存在的问题分析
Grover算法能够有效地对数据库进行搜索。但是它存在不足之处，在某些情况下Grover算法是无效的[20]。仍假设m为目标解的个数，N为数据库搜索空间的大小。
(1) 根据式(2.2.9)中 和 的关系，可以看到，当 时， ，无论迭代次数为多少， ，迭代与不迭代而直接测量的效果一样，因此此时算法是无效的。
(2) 当在 时，为保证算法有较大成功概率需要的迭代次数不再满足 关系，使得迭代次数有时非常大，导致整个算法的计算复杂度明显增大。
根据式 求出当迭代次数为1，可以求出此时搜索成功的概率与搜索失败的概率如下：    (2.2.12)
它们的仿真结果如图2.5所示，其中横轴为 ，纵轴为测量所得到的概率。
 图2.5   Grover搜索迭代一次后的概率变化
从图2.5中可以看出，Grover 搜索算法如果迭代一次，在 时，搜索成功的概率不断下降，而且在 时，搜索失败的概率大于搜索成功的概率。为了保证算法有较大的搜索成功概率，必须进行多次迭代。此时Grover算法的迭代次数不再满足 关系，而呈现不规则的变化。这时候为了以较大的概率获得正确解而迭代次数有时候非常大，使得整个算法的开销很大。
针对以上Grover算法的缺点，以下提出一种改进的Grover算法。
2.3 Grover算法的改进
2.3.1 算法的改进思路 
针对目前Grover算法不能区分各个搜索子目标的重要程度，以及随着目标数增多，搜索几率迅速下降直至算法失效的问题，提出一种改进后的算法，可有效地解决以上问题。
假设m为目标解的个数，N为数据库搜索空间的大小。
设 为目标态， 为非目标态，初始态置为零，令U为n维的Hadamard门，得到的叠加态可表述为
                (2.3.1)      其中    ，根据文献[21-22]，Grover算法中的两个相移算子可推广为 (2.3.2)
因此，G可描述为：又因为

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]  ... 下一页  >>