改进量子搜索算法及其在核属性求解上的应用

大部分的量子算法都必须先求解目标分量占比，否则算法的迭代次数无法确定。迭代次数自适应Grover算法有效地避开了目标分量占比求解这个步骤，但其性能相对于Grover算法来说并没有任何改善。致力于提升迭代次数自适应Grover算法的性能，提出了一种改进量子搜索算法，并将其应用于求解粗糙集的核属性。经过仿真实验，改进算法不仅实现了迭代次数自适应，而且整体上提升了获得目标分量的概率，使得获得目标分量的概率恒高于85%。     

改进的多目标元素量子搜索算法

Grover量子搜索算法解决了未加排序的数据库搜索问题,在2ⁿ个元素中搜索M个目标元素,其计算复杂度为O（（2ⁿ/M）^-2）,相对于经典算法实现了二次加速,但是,当目标元素个数接近2ⁿ/2时该算法成功率只达到50%。从任意相位的Grover变换从发,给出一种改进的多目标元素量子搜索算法,该算法在目标元素个数M≥2ⁿ/4时,只用一次Grover变换就能以概率1完成搜索。     

基于Grover搜索算法的整数分解

非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的。Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。文中提出基于Grover搜索算法并结合经典预处理实现整数分解。首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子P和Q;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率。仿真结果验证了使用Grover算法求解素因子P和Q的可行性。文中实现了在搜索空间为16且一次G迭代条件下以近78%的成功概率搜索到目标项。文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异。通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显。     

多目标元素的量子搜索算法

Grover量子搜索算法解决了未加整理的数据库搜索问题,在2ⁿ个元素中搜索M个目标元素时,计算复杂度为O（√2ⁿ/M）,相对于经典算法实现了二次加速,但Grover算法在目标元素个数接近2ⁿ/2时成功率较低。提出了一种针对多目标元素的量子搜索算法,当目标元素个数大于2ⁿ/3时,能以不低于97.36%的概率找到目标元素。     

Grover量子搜索算法的线路优化

Grover算法是能够高效查找到目标态的量子搜索算法，但随着搜索数据量的增大，它的量子线路面临着复杂的门分解问题。在如今的NISQ时代资源非常有限，因此线路的深度成为一种重要的度量标准。介绍了一种基于分治思想的二阶段量子搜索算法，能够在量子计算机上快速地并行运行。提出一种线路优化方法，应用块级的Oracle线路来减少迭代次数。将该方法与分治思想相结合，提出2P-Grover算法。在量子计算框架Cirq上进行模拟实验，与Grover算法进行对比。实验结果表明，2P-Grover算法能够使线路的深度至少减少60%,并且保持了较高的搜索成功率。     

一种改进的量子搜索算法

Rrover提出的对无序数据库进行搜索的量子算法，可以将搜索时间复杂度从经典计算机上的O（N）降低为O（N的平方根）。该算法显示了量子计算的强大能力，在量子计算研究中具有重要地位。但是，我们在研究Grover算法中发现Grover算法存在搜索失效等问题。本文分析了Grover算法中存在的问题，针对其不足之处进行了改进，并证明了改进后量子搜索算法的有效性。     

一种Grover量子搜索算法的改进策略

在使用Grover量子搜索算法对给定规模的数据库搜索时，随着搜索目标数的增加，获得正确结果的概率大幅度下降．分析了出现这种现象的原因，提出了一种基于新的相位匹配条件的改进策略．在新的相位匹配条件中，使2次相位旋转的大小相等方向相反．当要搜索的目标数目多于记录总数的1／3时，应用改进后的算法只需一步搜索，能以至少25／27的概率得到全部搜索目标．实验证明这种策略是有效的．     

基于固定目标权重的量子搜索算法

针对现有量子搜索算法均未考虑目标对象重要性的差异,提出了一种对已分配权重的目标对象进行搜索的量子搜索算法。首先对改变叠加态初态幅值会对迭代结果产生的影响进行了分析;在此基础上得出了保证算法有效性前提下,引入权重系数必须满足的条件;基于该条件,构建了含有目标权重信息的量子叠加态,并使算法同时保持了Grover算法的原有性质。仿真结果表明,提出的算法能够以权重值的概率,对成功搜索到的目标态得到满意的结果。     

Grover算法改进与应用综述

量子信息科学是一门新兴的交叉学科,它在信息领域中有着独特的性能,在提高运算速度、确保信息安全、增大信息容量和提高检测精度等方面可突破现有经典信息系统的极限.Grover算法是一类典型的量子算法,能够对任意经典暴力穷举搜索问题实现二次加速,进一步推动了量子计算的发展,如何有效地改进和应用Grover算法成为量子计算的一个重要研究领域.文中综述了Grover算法的优化改进和应用,对Grover算法在不同领域应用及不同方面的改进进行了概述,并对Grover算法未来的改进和相关应用的若干研究方向进行了探讨.     

基于Grover量子搜索算法和量子计数的BLAKE算法安全性分析

从量子计算的角度考虑,本文结合Grover量子搜索算法与量子计数思想,提出一种搜索Hash碰撞的量子搜索模型,给出量子计数方法分析Hash碰撞的量子线路图,针对典型Hash函数BLAKE算法给出相应的量子黑箱线路设计,并对本文提出的方法进行了简要的性能分析.     

Quest for Fast Partial Search Algorithm

The Grover quantum algorithm can find a target item in a database faster than any classical algorithm. In partial search, one trades accuracy for speed, and a part of the database (a block) containing the target item can be found even faster. We consider different partial search algorithms and argue that the algorithm originally suggested by Grover and Radhakrishnan and modified by Korepin is the optimal one. The efficiency of an algorithm is measured by the number of queries to the oracle.     

Sure Success Partial Search

Partial search has been proposed recently for finding the target block containing a target element with fewer queries than the full Grover search algorithm which can locate the target precisely. Since such partial searches will likely be used as subroutines for larger algorithms their success rate is important. We propose a partial search algorithm which achieves success with unit probability.      

在量子计算机上求解0/1背包问题

在Ｇｒｏｖｅｒ算法和量子指数搜索算法的基础上,提出了一个量子算法去求解０／１背包问题。这个算法在没有使用任何可以提高搜索效率的经典策略的情况下,能够在Ｏ（ｃ＾２ｎ／２）步以至少１－１／２＾ｃ的概率求解问题规模为ｎ的０／１背包问题。     

用Grover量子搜索算法挖掘网络数据

利用Grover量子搜索算法和概率论给出了挖掘网络数据的关联规则挖掘、权威页面挖掘和Weblog记录挖掘的一种新方法,最后说明该方法比任何经典方法要快得多。     

求最优装载的量子算法

随着Grover量子搜索算法的不断发展,它的实际应用价值也在逐渐体现.通过介绍量子并行计算和量子算法的基本思想以及对改进的Grover搜索算法进行研究的基础上,分析给出了一个时间复杂度为O(√N)的求解最优装载问题的量子算法.对于最优装载问题,分别用经典计算机上的贪心算法和量子算法来求解,得出了这两种算法的时间复杂度,从而可以看出量子算法相对于经典算法具有更快的搜索速度.     

针对运动目标的多无人机协同鸽群优化搜索方法

针对多无人机协同运动目标搜索问题,本文设计了改进鸽群优化算法的协同搜索决策.首先,基于运动目标的独立性,建立了服从正态分布的目标概率信息图模型;为了提高环境中目标存在的确定度,建立了搜索环境的确定度信息图.其次,通过建立的吸引和排斥数字信息素图,引导无人机向未搜索区域飞行,减少重复搜索概率,提高协同目标搜索效率,并基于传统的鸽群算法,通过加入速度更新修正机制和精英代机制对其进行改进.然后,结合环境中目标的存在概率信息以及无人机搜索目标的探测信息,使用改进鸽群优化算法,规划无人机的最优搜索飞行路径.并设计避碰机制,以有效防止无人机搜索过程中的碰撞.最后,通过比较仿真实验验证了改进鸽群优化算法对运动目标协同搜索的有效性.     

量子查找算法的发展与前瞻

量子查找算法是一种利用波的特性进行查找的新方法，它以量子位作为描述问题 的基本信息单位，为 NP-完全问题的解决提供了一种有效的途径。量子查找算法的主要特 点 是查找的高度并行性、非结构化查找和巨大的信息存储容量。该文介绍了量子查找的基 本思 想；综述了量子查找的典型实例及其广泛应用；分析了量子查找算法的特点及其与传 统算法 的关系；指出了量子计算目前存在的问题；最后对量子计算的发展前景进行展望。