| 在量子计算机上求解0/1背包问题 |
| |
| 引用本文： | 胡劲松,陈国良,郭光灿.在量子计算机上求解0/1背包问题[J].计算机学报,1999,22(12):1314-1316. |
| |
| 作者姓名： | 胡劲松 陈国良 郭光灿 |
| |
| 作者单位： | 1. 中国科学技术大学计算机科学与技术系国家高性能计算中心,合肥,230027
2. 中国科学技术大学非线性科学中心,合肥,230026 |
| |
| 摘 要： | 在Ｇｒｏｖｅｒ算法和量子指数搜索算法的基础上，提出了一个量子算法去求解０／１背包问题。这个算法在没有使用任何可以提高搜索效率的经典策略的情况下，能够在Ｏ（ｃ＾２ｎ／２）步以至少１－１／２＾ｃ的概率求解问题规模为ｎ的０／１背包问题。
|
| 关 键 词： | 量子算法 OPC问题 0/1背包问题 Grover算法 量子并行性 |
| 修稿时间： | 1998年12月23日 |
SOLVING THE 0/1-KNAPSACK PROBLEM ON QUANTUM COMPUTER |
| |
| HU Jin-Song,CHEN Guo-Liang,GUO Guang-Can.SOLVING THE 0/1-KNAPSACK PROBLEM ON QUANTUM COMPUTER[J].Chinese Journal of Computers,1999,22(12):1314-1316. |
| |
| Authors: | HU Jin-Song CHEN Guo-Liang GUO Guang-Can |
| |
| Abstract: | 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. |
| |
| Keywords: | Quantum mechanical algorithm NPC problem 0/1-knapsack problem Grover algorithm quantum parallelism |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
