背包问题的量子算法分析

摘要

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