Quantum mechanical algorithm to solve knapsack problem

doi:10.3778/j.issn.1002-8331.2009.20.019

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-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

背包问题的量子计算算法

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

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

通讯作者: 钟普查

Abstract

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

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

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

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.

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

[1]	HAO Xiang, HE Yichao, ZHU Xiaobin, ZHAI Qinglei. Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(18): 103-113.
[2]	ZHANG Ming, DENG Wenhan, LIN Juan, ZHONG Yiwen. Modified Ant Colony Optimization Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(13): 85-95.
[3]	WU Congcong, HE Yichao, ZHAO Jianli. New Genetic Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2020, 56(7): 57-66.
[4]	CHEN Changqian, MU Xiaodong, NIU Ben, WANG Lizhi. Improved Binary Grey Wolves Optimization Algorithm Combined with Gaussian Distribution [J]. Computer Engineering and Applications, 2019, 55(13): 145-150.
[5]	YANG Yang1, PAN Dazhi1, HE Yichao2. Improved repair strategy genetic algorithm solve discount {0-1} knapsack problem [J]. Computer Engineering and Applications, 2018, 54(21): 37-42.
[6]	ZHANG Jian, GUO Xing, LI Wei. Application of improved?fruit fly optimization?algorithm on multi object search [J]. Computer Engineering and Applications, 2018, 54(2): 131-136.
[7]	LIU Xuejing, HE Yichao, WU Congcong, CAI Xiufeng. Research on bacterial foraging optimization algorithm for discounted {0-1} knapsack problem [J]. Computer Engineering and Applications, 2018, 54(2): 155-162.
[8]	LIU Xuejing1, HE Yichao1, WU Congcong1, LI Liang2. Adaptive bacterial foraging optimization algorithm for discounted {0-1} knapsack problem [J]. Computer Engineering and Applications, 2018, 54(18): 139-146.
[9]	LIU Xuejing1, HE Yichao1, WU Congcong1, LI Liang2. Chaotic binary crow search algorithm for 0-1 knapsack problem [J]. Computer Engineering and Applications, 2018, 54(10): 173-179.
[10]	QIAN Xi, ZENG Cheng, WANG Tian. Most stably continuous service set recommend algorithm in changing time [J]. Computer Engineering and Applications, 2017, 53(10): 73-78.
[11]	LIN Yunguo, CAI Shuiying. Analysis of hitting time for open quantum walk [J]. Computer Engineering and Applications, 2016, 52(15): 43-48.
[12]	CUI Jianshuang, WANG Chongjing. Solving multiple knapsack problem with speed limit particle swarm algorithm [J]. Computer Engineering and Applications, 2015, 51(9): 244-247.
[13]	WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng. Binary bat algrorithm for solving 0-1 knapsack problem [J]. Computer Engineering and Applications, 2015, 51(19): 71-74.
[14]	YU Juan, HE Yuyao. Hybrid algorithm based on Genetic Algorithm and estimation of distribution algorithm for 0-1 knapsack problem [J]. Computer Engineering and Applications, 2014, 50(9): 12-16.
[15]	WU Jiagao1, ZHANG Xi1, ZHUANG Songjie1, ZOU Zhiqiang1, HU Bin2. Research on cache replacement strategy for space vector data of multi-layer [J]. Computer Engineering and Applications, 2014, 50(7): 89-93.

Quantum mechanical algorithm to solve knapsack problem

背包问题的量子计算算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics