Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (20): 63-64.DOI: 10.3778/j.issn.1002-8331.2009.20.019

• 研究、探讨 • Previous Articles     Next Articles

Quantum mechanical algorithm to solve knapsack problem

ZHONG Pu-cha1,BAO Wan-su1,FAN De-jun2,XU Hao3   

  1. 1.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,the PLA Information Engineering University,Guangzhou 510510,China
  • Received:2008-04-23 Revised:2008-07-21 Online:2009-07-11 Published:2009-07-11
  • Contact: ZHONG Pu-cha

背包问题的量子计算算法

钟普查1,鲍皖苏1,范得军2,徐 浩3   

  1. 1.解放军信息工程大学 电子技术学院,郑州 450004
    2.解放军75130部队,广西 贵港 537100
    3.解放军信息工程大学 电子技术学院 广州训练大队,广州 510510
  • 通讯作者: 钟普查

Abstract: Knapsack problem is one of the NP complete problems.Its computational complexity is O(n2).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) 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.

Key words: quantum algorithm, Grover algorithm, fixed phase, knapsack problem

摘要: 背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O(n2)。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O(√N/M)步完成对规模为n的背包问题求解(M是解的数目),而基于原始Grover算法的背包问题量子计算算法计算复杂度为O(√N/M),成功率是50%~100%。

关键词: 量子算法, Grover算法, 固定相位, 背包问题