求解0-1背包问题的一种新混合算法

用动态规划算法求解0-1背包问题的时空复杂度为O（nC）。这个空间复杂度在求解大规模问题上是不可接受的。从计算0-1背包问题最优值的递归方程出发,给出高效利用内存的动态规划算法。为了克服内存高效的动态规划算法带来的缺点,设计新混合算法求解0-1背包问题。该新混合算法的时间复杂度为O（nC）;它消除了回溯阶段,并且为求得放入背包的物品所使用的空间复杂度仅为O（「n/d?+C）,其中d为计算机字长。实验结果表明,混合算法的工作效率与理论分析相同。     

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

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

背包问题的一种自适应算法

背包问题是经典的NP-hard组合优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极重要的应用．基于求解背包问题著名的二表算法和动态二表算法，利用归并原理和4个非平衡的子表，提出一种求解该问题的自适应算法，算法可根据计算资源和问题实例规模的大小，允许使用O(2^n/2-ε)的存储空间(1≤ε≤n／4)，在O(ε(2^n/2))的时间内求解背包问题．对算法性能的理论分析和数值实验结果表明，自适应算法可显著扩大背包实例的求解规模，从时间和空间上改进背包问题现有算法的性能．     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

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

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

基于量子计算机的数据库搜索

Grover提出的量子搜索算法,可以用O(N1/2)的时间复杂度完成对规模为N的非结构化数据集的搜索,这在经典计算机上需要O(N)的复杂度。其中量子黑盒(又称为Oracle)依赖于具体问题,根据数据库搜索的要求,设计了量子黑盒的内部结构和相应的量子线路,给出了适合于数据库搜索的量子算法。     

第一寄存器小Qubit量子计算攻击RSA研究

提出了针对RSA的小Qubit量子攻击算法设计,量子攻击的第一量子寄存器所需的Qubit数目由原先至少2L降低到L1,总体空间复杂度记为(L1,L),其中2L1≥r,r为分解所得周期。由于第一寄存器量子比特数的减少,降低了算法复杂度和成功率,且改进原算法中模幂计算,提升运算速率。改进攻击算法的量子电路的时间复杂度为T=O(2L2)。在时间复杂度和空间复杂度上都有明显的进步。改进算法的成功率降低了,但实际成功求解时间,即每次分解时间/成功率,依然低于 Shor 算法目前的主要改进算法。完成了仿真模拟实验,分别用11、10、9 Qubit成功分解119的量子电路。     

基于量子计算的粗糙集核属性求解算法

粗糙集的核属性求解问题在经典计算中是一个NP问题.现有的方法中最优的时间复杂度也需要${\rm O}$$ \left(|C||U|\right)$($U$为论域、$C$为属性列数).由于量子计算的并行性特点, 本文致力于采用量子计算的方法来求解粗糙集的核属性, 拟提出了一种基于量子计算的粗糙集核属性求解算法.经过仿真实验, 在任何情况下, 该算法都能以1的总概率得到目标分量; 且通过理论分析证明了算法的时间复杂度不会高于${\rm O}$$\left(|\frac{{\rm{ \mathsf{ π}}}}{2\arcsin\sqrt {\frac{M}{C}}}+1||U|\right)$.     

基于立方体剖分的传感器网络快速三维k-覆盖判定算法

提出了一种传感器网络中基于立方体剖分的三维k 覆盖快速判定算（CP-RTCDA）和三维最大k 覆盖问题的快速求解算法（CP-RTMCDA）。算法首先把感兴趣区域剖分为立方体区域，从而将复杂的空间区域覆盖问题转化为简单的立方体区域覆盖问题。理论分析与仿真实验表明, 针对具有n个节点的传感器网络, 新算法的计算时间复杂度为O(n)，远低于已有算法O(n3logn)的计算时间复杂度。     

最大团问题的加权分治算法

分支降阶是目前广泛用于求解组合优化领域中难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为[O(1.380np(n)),]其中[p(n)]表示问题规模数[n]的多项式函数。运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂度由原来的[O(1.380np(n))]降为[O(1.325np(n))]。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。     

Faster search by lackadaisical quantum walk

In the typical model, a discrete-time coined quantum walk searching the 2D grid for a marked vertex achieves a success probability of \(O(1/\log N)\) in \(O(\sqrt{N \log N})\) steps, which with amplitude amplification yields an overall runtime of \(O(\sqrt{N} \log N)\). We show that making the quantum walk lackadaisical or lazy by adding a self-loop of weight 4 / N to each vertex speeds up the search, causing the success probability to reach a constant near 1 in \(O(\sqrt{N \log N})\) steps, thus yielding an \(O(\sqrt{\log N})\) improvement over the typical, loopless algorithm. This improved runtime matches the best known quantum algorithms for this search problem. Our results are based on numerical simulations since the algorithm is not an instance of the abstract search algorithm.     

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

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

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

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

改进量子进化算法及其在物流配送路径优化问题中的应用

量子进化算法的性能直接受量子旋转门旋转角计算方法的影响.文中提出一种改进量子进化算法,核心是设计了基于量子比特概率幅比值自适应计算量子旋转门旋转角的新方法,算法具有收敛速度快和全局搜索能力强的特点.通过0/1背包问题分析了新方法中相关参数对算法性能的影响,并应用算法求解物流配送路径优化问题,仿真表明改进量子进化算法性能优于量子进化算法和传统进化算法.     

求最优装载的量子算法

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

搜索空间自适应量子搜索算法

量子搜索算法,相较于经典计算有着平方根的加速,在许多机器学习算法中都有广泛应用,如量子KNN算法、量子特征提取、量子主成分分析等.在目标分量占比较小的时候,量子搜索算法总能以较高的概率得到目标分量;然而,当目标分量占比较大时,量子搜索算法的成功概率急剧下降.为解决这个问题,本文拟提出一种搜索空间自适应的量子搜索算法.新算法依据目标分量占比的不同采用不同的策略:当目标分量占比为λ≥1/2,将搜索空间扩大为8N;当目标分量占比1/4≤λ<1/2时,将搜索空间扩大为4N;当目标分量占比1/8≤λ<1/4时,将搜索空间扩大为2N;当目标分量占比λ<1/8时,保持搜索空间不变.通过理论分析,改进算法整体效率得到显著的改进,能够保持93%以上的成功概率.     

Search an unsorted database with quantum mechanics

In this article, we review quantum search algorithms for unsorted database search problem. Unsorted database search is a very important problem in science and technology. In a quantum computer, a marked state can be found with very high probability using the Grover’s algorithm, or exactly with the Long algorithm. We review the Grover algorithm and related generalizations. In particular, we review the phase matching conditions in quantum search algorithm. Several issues that may cause confusion about the quantum search algorithm are also clarified.     

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

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