背包问题的量子计算算法

doi:10.3778/j.issn.1002-8331.2009.20.019

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (20): 63-64.DOI: 10.3778/j.issn.1002-8331.2009.20.019

背包问题的量子计算算法

钟普查¹，鲍皖苏¹，范得军²，徐浩³

1.解放军信息工程大学电子技术学院，郑州 450004
2.解放军75130部队，广西贵港 537100
3.解放军信息工程大学电子技术学院广州训练大队，广州 510510

收稿日期:2008-04-23 修回日期:2008-07-21 出版日期:2009-07-11 发布日期:2009-07-11
通讯作者: 钟普查

Quantum mechanical algorithm to solve knapsack problem

ZHONG Pu-cha¹，BAO Wan-su¹，FAN De-jun²，XU Hao³

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

摘要/Abstract

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

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

Abstract: Knapsack problem is one of the NP complete problems.Its computational complexity is O（n²）.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

钟普查¹，鲍皖苏¹，范得军²，徐浩³. 背包问题的量子计算算法[J]. 计算机工程与应用, 2009, 45(20): 63-64.

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.

[1]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[2]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[3]	吴聪聪，贺毅朝，赵建立. 求解折扣{0-1}背包问题的新遗传算法[J]. 计算机工程与应用, 2020, 56(7): 57-66.
[4]	陈长倩，慕晓冬，牛犇，王立志. 结合高斯分布的改进二进制灰狼优化算法[J]. 计算机工程与应用, 2019, 55(13): 145-150.
[5]	杨洋1，潘大志1，贺毅朝2. 改进修复策略遗传算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(21): 37-42.
[6]	张健，郭星，李炜. 改进果蝇优化算法在多目标搜索的应用[J]. 计算机工程与应用, 2018, 54(2): 131-136.
[7]	刘雪静，贺毅朝，吴聪聪，才秀凤. 基于细菌觅食算法求解折扣{0-1}背包问题的研究[J]. 计算机工程与应用, 2018, 54(2): 155-162.
[8]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 自适应细菌觅食算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(18): 139-146.
[9]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[10]	钱汐，曾承，王甜. 时序范围最具稳定性服务集推荐算法[J]. 计算机工程与应用, 2017, 53(10): 73-78.
[11]	林运国，蔡水英. 开放量子行走的击中时分析[J]. 计算机工程与应用, 2016, 52(15): 43-48.
[12]	崔建双，王憧憬. 求解多重背包问题的限速粒子群算法[J]. 计算机工程与应用, 2015, 51(9): 244-247.
[13]	吴聪聪，贺毅朝，陈嶷瑛，刘雪静，才秀凤. 求解0-1背包问题的二进制蝙蝠算法[J]. 计算机工程与应用, 2015, 51(19): 71-74.
[14]	余娟，贺昱曜. 解决0-1背包问题的遗传分布估计算法[J]. 计算机工程与应用, 2014, 50(9): 12-16.
[15]	吴家皋1，张曦1，庄嵩杰1，邹志强1，胡斌2. 面向多图层的空间矢量数据缓存更新策略研究[J]. 计算机工程与应用, 2014, 50(7): 89-93.

背包问题的量子计算算法

Quantum mechanical algorithm to solve knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics