基于量子算法的指纹数据库搜索方法

摘要

一种基于量子算法的指纹数据库搜索方法，该匹配方法包括如下步骤：1)对指纹进行采集、预处理和细节特征点的提取，选取参照点，将一个输入指纹和N个模板指纹中的细节特征点集以各自的参考点为基准，转移到极坐标中；2)利用量子并行性原理一次求取所有模板指纹与输入指纹的匹配总数，将其保存到匹配分数数据库中；3)将Grover算法中的Oracle算子进行改进，使其包含有两个数据库，最终将索引寄存器中获得的N个状态与全面得到的匹配分数数据库位置一一对应；4)旋转索引寄存器中所有状态的平均值，对索引寄存器进行测量最终获得所要搜索的目标指纹。本发明通过应用量子算法，从而提高在这种非结构化的指纹数据库进行指纹搜索问题的搜索效率和搜索准确率。

主权项

1.一种基于量子算法的指纹数据库搜索方法，其特征在于，包括如下的步骤：(1)对n+1位量子比特状态的前n位应用Hadamard变换，通过n个门的并行作用，得到所有n位计算基态的平衡叠加(2)将制备得到的n+1量子比特的状态连接量子线路U_f上，U_f利用量子并行性原理来计算指纹匹配总数match-score值，最终得到f是用来计算match-score值的函数，|f(x)>对所有的前n位量子基态的平衡叠加态进行了一次f计算，一次计算得到的N＝2ⁿ个模板指纹与输入指纹的match-score值|f(x)>；(3)构造两个数据库，数据库一包括四个寄存器，数据库二包括N＝2ⁿ个寄存器，数据库一的四个寄存器，分别是一个初始化为|0>的n量子比特索引寄存器、一个初始化为|s>并在整个计算中保持该状态的l量子比特寄存器、一个初始化为|0>的l量子比特数据寄存器、一个初始化为的1量子比特寄存器，l为每个match-score二进制字符串最大值长度的比特数，s为输入指纹的细节点总数的二进制字符串，N个模板指纹分别标记为从0到N-1；数据库二保存所有输入指纹与模板指纹所得到的N＝2ⁿ个match-score值，表示为d₀，...，d_N-1，每个单元由l量子比特组成；(4)将数据库二的第x个寄存器内容d_x加到数据库一的数据寄存器，计算方法为：$|0>\to |0\oplus d_x>;---\left(1\right)$(5)对数据库一的l量子比特寄存器和数据寄存器进行比较，如果相同，就应用比特翻转到数据库一的1量子比特寄存器，否则保持不变。(6)再次将数据库二的第x个寄存器内容d_x加到数据寄存器中，前面对数数据寄存器的操作为得到状态|d_x>，故再进行一次这样的操作，这一步数据寄存器恢复到状态|0>，最后索引寄存器得到N个状态。(7)对得到的N个状态应用Hadamard变换对索引寄存器所有状态的概率幅向量应用矩阵D进行幺正变换，旋转所有状态的平均值，将目标量子态的寻找范围大大缩小，放大所要寻找量子态的概率幅，最后对索引寄存器进行测量就可以得到目标量子态的位置，从而搜索到目标指纹的位置，矩阵D为：$\left|\begin{array}{ccccc}-1+\frac{2}{N}& & & & \\ & -1+\frac{2}{N}& & \frac{2}{N}& \\ & & ...& & \\ & \frac{2}{N}& & -1+\frac{2}{N}& \\ & & & & -1+\frac{2}{N}\end{array}\right|---\left(2\right)$