背包问题的量子计算算法

• 作者: 徐浩 范得军 钟普查 鲍皖苏
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 量子算法 Grover算法 固定相位 背包问题
• 年，卷（期）: 2009,（20）
• 所属期刊栏目: 研究、探讨
• 页码范围: 63-64,67
• 页数: 3页
• 分类号: TN301.6
• 字数: 2710字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.20.019

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钟普查	解放军信息工程大学电子技术学院	6	29	3.0	5.0
2	鲍皖苏	解放军信息工程大学电子技术学院	39	129	6.0	9.0
3	徐浩	解放军信息工程大学电子技术学院	1	3	1.0	1.0