基于自适应相位匹配量子计算的求核算法

2020-10-10谢旭明段隆振邱桃荣杨幼凤

南昌大学学报(理科版) 2020年3期

关键词：粗糙集个数算子

谢旭明，段隆振，邱桃荣*，杨幼凤

(南昌大学a.信息工程学院；b.图书馆，江西南昌 330031)

以上的改进策略均不能保证100%的成功概率。该研究提出一种自适应匹配相位角度的策略，并将改进策略应用于粗糙集的核属性求解。通过仿真实验，提出的策略能够在任意核属性占比情况下都能以100%的概率得到核属性。

1 相关研究

1.1 Grover算法

Grover算法是通过一系列的酉变换作用于等权重叠加态直至目标分量量子态的概率幅第一次到达峰值的过程。在这个过程中，目标分量量子态的概率幅被不断增大，非目标分量量子态的概率幅被不断削减。

设待搜索空间有N=2n个元素，所有分量以叠加态存放在n个量子比特中，Grover算法的简要示意图则表示为图1。

如图1所示，G算子包含Ga和Gs两个子算子。Ga算子可以使目标分量实现π的相位翻转。Gs算子随后使所有分量进行均值翻转。在规定次数内，目标分量的概率幅随着G算子的迭代而不断增大。

1.2 粗糙集核属性

1982年Pawlak[12]提出粗糙集理论用于刻画数据的不完备性和不精确性。粗糙集的核属性是粗糙集理论中最关键的概念，是各种属性约简算法的先决条件。粗糙集核属性的定义如下：

设S=(U，A，V，f)是一个粗糙集，对于任意属性子集B⊆A，IND(B)表示由B确定的二元不可区分关系。那么，对于∀a∈A，如果IND(A-{a})≠IND(A)，则称a是A的核属性。

2 自适应相位匹配Grover算法

针对现有Grover算法的局限性，提出一种自适应相位匹配量子搜索算法。改进算法的示意图如下：

如图2所示，对应于经典Grover算法，改进算法将迭代次数改为T′，将算子G改为算子G′。下面对T′和G′的确定方法进行详细分析。

2.1 改进算法的迭代次数T′

这里先分析经典Grover算法迭代次数的求解方法，然后结合改进算法的特点给出T′的取值方法。

2.1.1 经典算法的完美迭代次数

经典Grover算法的搜索过程实际可以看作是用一系列的幺正矩阵去与一个每个维度上的值都相同且模为1的N维向量相乘，最后希望得到的结果是不断提升解对应维度上的值和压缩非解维度上的值。单从线性代数的角度上看，假设不要求迭代次数为正整数，那么目标解集是一定可以以100%的概率得到的。为了研究方便，我们假设上面讲的这个迭代次数为完美迭代次数，并结合经典Grover算法，给出定义如下:

定义1设目标分量个数在总分量个数中占比为λ；那么，定义经典Grover算法的完美迭代次数为：

Tpft是根据令经过处理后的叠加态与目标分量的垂直向量成90度夹角(即目标分量的概率幅为1)得到的。但实际情况下，小数次的迭代次数是不可能实现的。从定义1中可以看出随着λ的变化，Tpft有可能为正整数。Tpft为正整数时，那么说明这样的次数是可以执行的。

2.1.2 提出算法的迭代次数

如同经典算法一样，自适应相位匹配量子搜索的迭代次数也是至关重要的。这里先给出一个关于迭代次数的定理，然后确定提出算法的迭代次数。

定理1当且仅当迭代次数t满足t≥Tpft时，存在相位角度φ，使得目标分量的概率幅为1。

证明经典Grover算法的相位角度为π，而相位角度π(π与-π等价)是使得叠加态与目标分量值平面的垂直矢量能产生最大夹角的相位。也就是说，π(或-π)是使得叠加态最快靠近目标分量值平面的相位角度。Tpft是经典Grover算法(即φ=π，-π在产生的夹角大小方面与π等价)在理论上第一次叠加态到达目标分量值平面的迭代次数，但Tpft在绝大多数情况下都是小数，在实际中无法实现。因此，仅当存在整数次迭代次数t，且满足t≥Tpft时，才存在相位角度φ使得叠加态到达目标分量值平面。

证毕。

通过定理1可知，只要满足t≥Tpft，那么就存在相位角度φ使得经过算子处理后的目标分量的概率幅等于1。在算法的设计中，迭代次数越少自然带来的计算复杂度越小，而迭代次数又必须是整数次。因此，改进算法的迭代次数可对Tpft向上取整得到，即T′=CEIL(Tpft)，其中CEIL()为向上取整函数。

经典量子搜索的迭代次数是对Tpft四舍五入取整，提出算法迭代次数T′是对Tpft向上取整。因此，提出算法的迭代次数最多比经典量子搜索算法的迭代次数多一次。

2.2 改进算法算子G′

G′算子也包含两个子算子Ga′和Gs′，表达式如公式(1)和公式(2)。

Ga′=I-(1-eiφ′)|a>

(1)

Gs′=(1-eiφ′)|s>

(2)

可以看出，只要求解出相位角度φ′就可以确定G′算子。假设j次G′算子迭代后得到的叠加态中各目标分量的概率幅为aj，各非目标分量的概率幅为bj，j为自然数。

首先，根据总分量的个数N，可以得出初始状态下a0，b0的表达式如公式(3)所示。

(3)

再者，根据目标分量占比λ、Ga′和Gs′的表达式，j+1次G′算子迭代后，aj+1和bj+1与aj和bj总存在公式(4)和公式(5)所示的关系。

aj+1=-λei2φ′aj-(1-λ)eiφ′aj-(1-λ)eiφ′bj+(1-λ)bj

(4)

bj+1=-λei2φ′aj+λeiφ′aj-(1-λ)eiφ′bj-λbj

(5)

上一节已经证明改进算法在迭代T′次后，存在相位角度φ使得叠加态到达目标分量值平面，即使得bT=0。结合公式(3)、(4)和(5)就可求出相位角度φ′，进而确定算子G′。

2.3 算法描述

通过上面的分析得出的迭代次数、算法的相位角度，自适应相位匹配Grover算法可以描述为:

(1) 根据目标分量个数在总分量个数中的占比求出完美迭代次数Tpft

(2) 对Tpft向上取整求出算法迭代次数T′

(3) 结合公式(3)、(4)、(5)得出bT表达式，令bT=0，求出相位角度φ′

(4) 根据φ′构建算子Ga′和Gs′

(5) 构建等权重叠加态|s>

(6) 将Ga′算子和Gs′算子T′次作用于|s>

(7) 测量得到的叠加态

3 基于改进量子计算的求核算法

3.1 构建黑盒

设S=(U，A，V，f)，a∈A是待求核粗糙集，其属性个数为N，核属性个数为M。要将自适应相位匹配Grover算法应用到S的求核上，我们可以把量子算法的每一个分量x和粗糙集的各个属性做一个映射，既x→a。对应改进的Grover算法，迭代算子中Ga′的判别函数修改为：

3.2 核属性个数确定及算法描述

粗糙集S中的核属性个数M可以通过结合Shor算法和Grover算法的量子计算算法[13]确定，随后便可以确定核属性个数在属性总个数中的占比，接着算法的步骤如下：

(1) 确定完美迭代次数Tpft

(2) 求解迭代次数T′以及相位角度φ′

(3) 构建算子Ga′和Gs′

(4) 构建等权重叠加态|s>

(5) 将Ga′和Gs′算子T′次作用于|s>

(6) 测量得到的叠加态

4 仿真实验及分析

4.1 数据集

为了详细地体现整体分布情况，实验者自行构造数据集如：构造一个32行32列的矩阵，矩阵的斜对角线上由整数0至31构成，矩阵其它位置的数值均为0。

数据集Ik由上述矩阵的第一行至第k+1行构成，其中，k=1，2，3，…，31。由此，上述矩阵可以产生31个数据集(数据集I1，I2，…，I31)。显而易见，数据集Ik的核属性集包含第二至第k+1列共k列属性。

4.2 仿真环境

系统：64位Windows7系统、2GB内存、IntelCorei5处理器。

软件：Matlab2012B。

4.3 测试结果及分析

实验将本文算法与基于经典Grover以及文献[5]中的固定相位Grover算法进行比较。实验得到的数据被绘成图3和图4。

从图3中可以看出：经典Grover算法在核属性不超过半数时总能以0.5以上的概率得到目标分量，当核属性超过半数时算法失效；固定相位Grover算法在得到目标概率上明显优于经典Grover算法，总能以0.9以上的概率得到目标分量；而本文提出的算法总能以1的概率得到目标分量。总的来说，在解分量概率方面，本文提出的算法明显优于经典Grover算法和固定相位Grover算法。

从图4中可以看出：经典Grover的算子迭代次数最少；固定相位算法的算子迭代次数要明显高于经典Grover算法；本文算法的算子迭代次数，明显低于固定相位算法的算子迭代次数，略高于经典Grover算法的算子迭代次数。