北京航空航天大学学报 ›› 2004, Vol. 30 ›› Issue (11): 1088-1091.

• 论文 • 上一篇    下一篇

背包问题的量子算法分析

吕欣, 冯登国   

  1. 中国科学院究生院 信息安全国家重点实验室, 北京 100039
  • 收稿日期:2004-06-25 出版日期:2004-11-30 发布日期:2010-09-24
  • 作者简介:吕 欣 (1977-),男,河北石家庄人,博士生, lx@is.ac.cn.
  • 基金资助:

    国家重点基础研究发展规划973资助项目(G1999035802); 国家自然科学基金资助项目(60273027,60403004); 中国科学院研究生创新与实践基 金资助项目

Quantum algorithm analysis of knapsack problem

Lü Xin, Feng Denggu   

  1. State Key Laboratory of Information Security, Graduate School, Chinese Academic of Science, Bejing 100039, China
  • Received:2004-06-25 Online:2004-11-30 Published:2010-09-24

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

Abstract: Speeding up knapsack problem, one of the NP complete problems, which could be us ed to design public-key cryptosy stems, was discussed using quantum algorithm. How to use Grover's quantum search ing algorithm to speed up the knapsack problem was talked about based on computa tional complexity theory. Comparisons of quantum searching algorithm with Shor's factoring algorithm were delivered and the factors that affected the performanc e of quantum algorithms were discussed from group theory point of view. The futu re of the quantum algorithms was also augmented in the later.

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发