子集和问题的量子算法

摘要

本文介绍了量子算法的基本思想及相关概念.在量子环境下利用划分原理,不断地对态矢划分子空间,然后减小不满足条件态矢的概率幅,而增大满足条件的概率幅,最后将以大的概率得到所求的解.从而可以把时间复杂度由传统的指数时间求解的问题变成在量子计算机中能在多项式时间能求解的问题,在量子物理环境下它能在多项式时间内求出子集和问题(背包问题)的解.这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等.