基于量子Grover算法的MIMO-OFDM系统信号检测技术的研究 第4页
则产生了 个量子基态 （i = 0,1,2, … ,  ）的叠加，输出的是等概率的每个基矢量的和。
2.1.3 量子并行计算
在量子计算机中,处于叠加态的n位量子寄存器可同时存储从0到2n - 1的所有2n个数，它们各以一定的概率同时存在。这样，作用于量子寄存器上的任意变换都是同时对所有2n个数进行操作，相当于对叠加态 中的每一个量子基态 同时进行计算，得到的计算结果是一个新的叠加态，并保存在n位量子寄存器中，这就是量子并行（Quantum Parallelism）。因而量子计算机的一次运算可产生 个运算结果，相当于经典电子计算机 次操作，或者同时使用 个处理器的并行操作。量子并行性是许多量子算法的一个基本特征，简言之，量子并行特性使量子计算机可以同时计算函数 在许多不同的 处的值。本节将阐述量子并行特性的原理。
设 是具有一比特定义域和值域的函数，在量子计算机上，计算该函数的一个简便方法是，考虑初态为 的双量子比特的量子计算机，通过适当的逻辑门序列可以把这个状态变换为 ，这里 表示模2加，第一个寄存器称为数据寄存器，第二个称为目标寄存器，映射   叫 ，容易证明它是酉的。若 ，则第二个量子比特的最终状态就是 值。
把 加到计算机以外的一个输入，数据寄存器中是叠加态 ，这可由Hadamard门作用到 上得到，于是应用 得到状态：
      (2.1.13)
不同的项同时包含 和 ，看起来似乎同时对 的两个值计算了 ，与经典的并行不同，那里多重 电路同时运行，而这里利用量子计算机处于不同状态的叠加态的能力，使得单个 线路用来同时计算多个 的函数值。
利用Hadamard门变换，该过程可以推广到任意数目的量子比特上的函数，这个变换就变为n个Hadamard门同时作用在n个量子比特上。可以采用下述方法进行 比特输入x和单比特输出 函数的量子并行计算，制备 量子比特的状态 ，对前 位应用Hadamard变换，并连接实现 的量子线路。这就产生状态： (2.1.14)
在某种意义上，表面上似乎只进行一次 计算，量子并行性却使 的所有可能值同时被计算出来，提高了运算效率。
2.2 Grover搜索算法
1996年，美国科学家Grover提出了未加整理数据库的量子搜索算法。依靠量子并行计算的优势，在遍历搜索问题中运用该算法可以大大减少搜索成功的运算次数。证明量子计算机求解遍历搜寻问题的时间复杂度为 （N为数据库记录数），比经典电子计算机有 的加速。经过多年的改进，Grover量子搜索算法逐步完善，目前已经形成一个比较完整的搜索算法体系，能够适应各种不同的搜索需求。
2.2.1 Grover算法描述及几何可视化
对于一个包含 个元素的数据库，搜索问题的一个特例可以方便地表述为一个输入x的函数f，x是从0到N-1的整数，f的定义是：若x是搜索问题的一个解 ，而如果x不是搜索问题的解，则 。根据数据库中解的个数，将有一个或多个x返回函数值 。
算法从计算机的初态 开始，用Hadamard变换使计算机处于均衡叠加态
量子搜索算法由反复应用记作G的称为Grover迭代(Grover iteration)。Grover迭代的量子线路如图2.2所示，分成四步：
图2.2Grover迭代G的线路
（1） 应用oracle算子O，计算规则如下：
                             (2.2.2)
（2）在oracle算子O之后运用一个n维的Hadamard门。
（3）紧随其后的是一个受控相位门，在计算机上执行条件相移，使得 以外的每个每个计算基态获得 的相位移动。该相移的酉算子为：
                                                  (2.2.3)
（4）最后的算子依然是一个n维的Hadamard门。
注意以上第2，3，4步结合的效果为：
其中 是式(2.2.1)中的均衡叠加态，于是整个Grover迭代G可以写成：
                                 (2.2.5)
Grover迭代还能做什么？Grover迭代可视为在由开始向量 和搜索问题解组成的均匀叠加态张成的二维空间中的一个旋转，我们下面引入Grover算法的几何法表示[18]：
假设在 个无序元素 集合中，有 个目标解。简单起见，对系统初态的各量子基态进行合并，符合条件的目标基态合并为 ，不符合条件的非目标基态合并为 ，定义归一化状态：
以 和 为坐标轴构成一个二维平面。由于量子系统的变换过程中概率幅都是实数，所以量子系统的变换可以简化为在上述二维欧氏空间的变换。系统的初态重新表示为：其中： 。
对系统初态进行Grover 迭代，每次迭代由两次变换组成， 。 为选择性旋转变换矩阵，将目标基态概率幅取反,为了标注目标基态。 满足 。 为概率幅变换矩阵，将目标基态概率幅放大。用几何法来描述一次Grover迭代过程，矩阵 的作用由于使 中 分量的振幅取反， 以 为轴旋转 角； 使得 以 为对称轴反向旋转 角, 使得变换后的矢量在 轴上的投影即目标基态的概率幅变大。如图2.3所示。

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