摘要
近年来针对各种问题提出了许多量子算法,这些量子算法都利用了量子态的可迭加性(Superposition)和纠缠性(Entan-glement),本文在量子环境下对0/1背包问题进行求解,介绍了量子算法的基本思想及相关概念。然后分析并给出求解0/1背包问题的量子算法,在量子物理环境下它能在多项式时间内求出所需要的解。这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等。
The scientists have given various kinds of quantum mechanical algorithms for different kinds of problems in recent years. Because of massive quantum parallelism and entanglement,quantum computer can solve many problems more efficiently.0/1-kiapsack problems is a typical NPC problem.hs computing complexity is steps. This paper gives a quantum mechanical algorithm to solve 0/1- kiapsack problems,the algorithm find a solution for the n-element knapsack problem in polynomial time.This algorithm can be extended to solve other NPC problem,such as TSP problem.
出处
《微计算机信息》
北大核心
2006年第12X期273-274,176,共3页
Control & Automation
基金
国家自然科学基金(10574163)
