资源描述：
《0_1背包问题的量子算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、您的论文得到两院院士关注软件时空文章编号:1008-0570(2006)12-3-0273-020/1背包问题的量子算法AQuantumAlgorithmtoResolvethe0/1-kiapsackproblem1余超凡2(1.江门职业技术学院;2.广东教育学院)钟艳花ZHONGYANHUAYUCHAOFAN摘要:近年来针对各种问题提出了许多量子算法,这些量子算法都利用了量子态的可迭加性(Superposition)和纠缠性(Entan-glement),本文在量子环境下对0/1背包问题进行求解,
2、介绍了量子算法的基本思想及相关概念。然后分析并给出求解0/1背包问题的量子算法,在量子物理环境下它能在多项式时间内求出所需要的解。这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等。关键词:NPC问题;0/1背包问题;量子算法;量子计算中图分类号:TP301文献标识码:AAbstract:Thescientistshavegivenvariouskindsofquantummechanicalalgorithmsfordifferentkindsofproblemsinrecentyears.
3、Becauseofmassivequantumparallelismandentanglement,quantumcomputercansolvemanyproblemsmoreefficiently.0/1-kiapsackproblemsisatypicalNPCproblem.Itscomputingcomplexityissteps.Thispapergivesaquantummechanicalalgorithmtosolve0/1-技kiapsackproblems,thealgorith
4、mfindasolutionforthen-elementknapsackprobleminpolynomialtime.Thisalgorithmcanbeextend-edtosolveotherNPCproblem,suchasTSPproblem.术Keywords:NPCproblem,0/1-kiapsackproblem,quantumalgorithm,Quantumcomputation创规模为n的0/1背包问题。1引言20/1背包问题的量子算法新1982年,Benioff深入地研究
5、了量子计算机是否比经典计算机更有效的问题,他定义了量子Turing机,2.10/1背包问题描述了量子计算机的一般模型,研究了它的性质,说0/1背包问题一个典型的、易于描述的却难以处明了量子计算机的潜在能力。1986年,Feynman发现理的NP完全问题。问题是这样提出的:给出n种物品了将量子力学系统用于推理计算的可能。Deutsch是和一个背包,物品的重量W=(w1,w2⋯wn),其价值为V第一个系统地表述了现在人们所理解的量子计算机(v1,v2⋯vn),背包的容量C。问应如何选择装入背包中模型。19
6、94年,PeterShor发现了第一个具体的量子算的物品,使得装入背包中物品的总价值最大?在选择法,这个算法在设想的量子计算机上可以用输入的多装入背包的物品时对每种物品只有两种选择,即装入项式时间分解大数质因子,而求解大数质因子对经典背包或放弃,不能将物品装入背包多次,也不能只装入计算机是个难题。这个问题对经典计算机是如此困部分的物品。因此,该问题称为0/1背包问题。0/1背包难,以至于现在广泛使用的公开密码系统RSA就是以问题就是在资源有限的情况下,追求总的最大收益的这个问题的难解为基础的。1996
7、年,Grover又发现未资源有效分配问题,用数学形式更精确地描述如下:加整理数据库数量级加速查询算法,而且用这种加速的查询算法有可能解决经典上所谓NP难题,因求maxg(x),且满足约束条件f(x)≤c,(1)而引起人们重视。其中xi∈{0,1},1≤i≤n,vi>0,wi>0,c>0。如果xi=00/1背包问题在计算理论中属于NPC问题,其计算时间复杂性为O(2n表示不将第i个物品装入背包,xi=1表示将第个物品),在文献7提出一个量子算法,装入背包。显然,0/1背包问题是一个特殊的整数规划该算法是
8、在Grover量子查询算法上得出一个在能够在O(c2n/2c的概率求解问题规模为n问题。)步以至少1-1/22.20/1背包问题的量子算法的0/1背包问题,但这个算法是指数算法,且由于在利假设物品数为n,求0/1背包问题的量子算法具用Grover算法过程中存在缺陷。本文利用分类的思想体步骤如下:提出一个算法,这个算法能以多项式时间内求解问题步骤1:将一个n位的寄存器R1初始化为
9、0>,即
10、钟艳花:硕士讲师s>=
11、R1>=
12、00⋯>。基金项目:国家自然科学
