摘要
在Ｇｒｏｖｅｒ算法和量子指数搜索算法的基础上，提出了一个量子算法去求解０／１ 背包问题．这个算法在没有使用任何可以提高搜索效率的经典策略的情况下，能够在Ｏ（ｃ２ｎ２ ）步以至少１－ １２ｃ 的概率求解问题规模为ｎ 的０／１
The scientists have given various kinds of quantum mechanical algorithms for different kinds of problems in recent years. Because of massive quantum parallelism, quantum computer can solve many problems more efficiently. 0/1 knapsack problem is a typical NPC problem. Its computing complexity is O(2 n ) steps. This paper gives a quantum mechanical algorithm to solve 0/1 knapsack problem, which is based on Grover algorithm and quantum exponential searching algorithm. The algorithm doesn't involve any classical method to improve search efficiency and the solution can be obtained in O(c2 n2 ) steps with a probability of at least 1-12 c.
出处
《计算机学报》
EI
CSCD
北大核心
1999年第12期1314-1316,共3页
Chinese Journal of Computers
关键词
量子算法
量子计算机
NP问题
0/1背包问题
Quantum mechanical algorithm, NPC problem, 0/1-knapsack problem, Grover algorithm, quantum parallelism.
