背包问题的量子算法分析

• 作者: 冯登国 吕欣
• 来源期刊: 北京航空航天大学学报
• 学科: 工学
• 关键词: 量子计算 背包问题 复杂度理论 密码分析
• 年，卷（期）: 2004,（11）
• 页码范围: 1088-1091
• 页数: 4页
• 分类号: TP301.6
• 字数: 3346字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5965.2004.11.014

摘要

对可用于密码体制设计的NP完全问题--背包问题,进行了量子算法分析.从复杂度理论角度出发,讨论了如何用量子搜索算法加速背包问题等NP完全问题的求解.并从群论的角度与Shor的大数分解算法做了比较,讨论了影响算法速度一些因素.对量子算法的特性和前景做了展望.