0/1背包问题的量子算法

摘要：

近年来针对各种问题提出了许多量子算法,这些量子算法都利用了量子态的可迭加性(Superposition)和纠缠性(Entanglement),本文在量子环境下对0/1背包问题进行求解,介绍了量子算法的基本思想及相关概念.然后分析并给出求解0/1背包问题的量子算法,在量子物理环境下它能在多项式时间内求出所需要的解.这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等.

关键词：NPC问题、0/1背包问题、量子算法、量子计算

所属期刊栏目：22

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金10574163

在线出版日期：2007-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：273-274,176