量子KNN算法在量子人工智能引论中的应用

最近邻算法完成有监督的集群分配任务。假设有两个集群，用质心向量（1/Mc）Σj∈cxj表示，其中c 是类别，找到合适新向量x 使∣x-（1/Mc）Σj∈cxj∣2最小。估计与质心向量间的距离【89】，并通过查询QRAM 来构造质心状态【90】。

该算法的一种拓展是避免使用质心向量，如果类不能很好地分离，或者类的形状复杂且质心不在类内，这种形式的最近邻分类运算效率会表现得很差【91】。相反，如果计算类中所有向量与目标向量之间的距离，目标就变成判断不等式是否为真：

对于这个变量，假设向量f 是稀疏的，即向量包含不超过f 个非零项。在许多经典算法中，都是利用稀疏数据结构来提高执行速度，而非复杂度。这种结构在文本挖掘和推荐引擎等应用中十分常见。同时假设数据集中任何特征的最大值都有一个上界rmax。假设有两个量子预言：

式中，f（j，1）给出了xj中的第I个非零值的位置。

在这些条件下，寻找最大重叠maxi∣<x∣xj>∣2，满足成功概率至少为1-δ 且误差最多为∈的条件下需要查询达到预期的数量，查询的顺序为

为了达到这一临界值，需要对以下状态使用交换测试

式中，rji 来自xji=rjieiϕji极坐标形式的数字。这些状态由6 次预言调用和两次单量子位旋转产生【91】。

为了快速估计得到0 的概率，不在交换测试中执行测量，而是使用振幅估计，满足误差在∈以内，以O（1/ϵ）为缩放比例估计P（0）。用P（0）来表示这个估计。给定一个维数为R的寄存器，此估计的误差界限为

对于计算欧几里得距离也有类似的结果。(www.xing528.com)

最近邻聚类的另一种观点是将质心向量作为模板状态，将其作为量子模板匹配处理。量子模板匹配类似于状态分层的各种形式。在量子态辨别中，已知一组状态{Pi}的先验分布，且任务决定是正在接收的状态。在量子态估计中，通过估计其参数来重建一个给定的未知态。在模板匹配中，有一个先验的状态集（就像在状态辨别中一样），但未知状态也由参数来表征（就像在状态估计中一样）。【92，93】

使用保真度估计未知状态和目标模板状态之间的距离，并选择保真度最大的模板。匹配策略由正操作值度量{Pi}来表示，其性能由其在所有匹配项上的平均得分来衡量。这种情况既适用于经典输入，也适用于量子输入。在第一种设置下，模板状态是从经典信息派生出来的。在第二种设置下，泛化为全量子模板状态，其中对于每个模板状态，只有有限数量的副本可用。然而，寻找最优正算子值度量的一般策略并不存在，一般只能处理具有特定结构的模板状态的特殊情况。

量子KNN 算法如下：

步1 计算类中所有向量与目标向量之间的距离，确定以下不等式是否为真

步2 寻找最大重叠maxj∣<x∣xj>∣2

查询顺序为：

为达到临界值进行交换测试。

步3 使用振幅估计，得到满足误差在ϵ以内以O（1/ϵ）为缩放比例估计P（0）得到重叠∣<x∣xj>∣2=（2P（0）-1）f2r4max，即可确定分类。