|
|||||
|
|
| 背包问题的量子计算算法 | |
| 引用本文： | 钟普查,鲍皖苏,范得军,徐浩.背包问题的量子计算算法[J].计算机工程与应用,2009,45(20):63-64. |
| 作者姓名： | 钟普查 鲍皖苏 范得军 徐浩 |
| 作者单位： | 1. 解放军信息工程大学,电子技术学院,郑州,450004 2. 解放军75130部队,广西,贵港,537100 3. 解放军信息工程大学,电子技术学院,广州训练大队,广州,510510 |
| 摘 要： | 背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O(2n)。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O((N/M)~(1/2))步完成对规模为n的背包问题求解(M是解的数目),而基于原始Grover算法的背包问题量子计算算法计算复杂度为O((N/M)~(1/2)),成功率是50%～100%。 |
| 关 键 词： | 量子算法 Grover算法 固定相位 背包问题 |
| 收稿时间： | 2008-4-23 |
| 修稿时间： | 2008-7-21 |
Quantum mechanical algorithm to solve knapsack problem |
|
| ZHONG Pu-cha,BAO Wan-su,FAN De-jun,XU Hao.Quantum mechanical algorithm to solve knapsack problem[J].Computer Engineering and Applications,2009,45(20):63-64. | |
| Authors: | ZHONG Pu-cha BAO Wan-su FAN De-jun XU Hao |
| Affiliation: | ZHONG Pu-cha1,BAO Wan-su1,FAN De-jun2,XU Hao31.Institute of Electronic Technology,the PLA Information Engineering University,Zhengzhou 450004,China 2.PLA 75130 Unit,Guigang,Guangxi 537100,China 3.Training Military Unit,Institute of Electronic Technology,Guangzhou 510510,China |
| Abstract: | Knapsack problem is one of the NP complete problems.Its computational complexity is O( 2n).This paper presents the quantum mechanical algorithm based on the fixed phase quantum search to solve the knapsack problem,and the algorithm also gets probability of success at least 98% in O((N/M)~(1/2)) quantum mechanical steps( Where M is the number of matches).This quantum algorithm has higher probability of success than the algorithm based on Grover algorithm with multiple matches in the search space. |
| Keywords: | quantum algorithm Grover algorithm fixed phase knapsack problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 | |
| 点击此处可从《计算机工程与应用》下载全文 | |