Quantum algorithm analysis of knapsack problem
-
摘要: 对可用于密码体制设计的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.
-
Key words:
- quantum computation /
- knapsack problem /
- complexity theory /
- cryptanalysis
-
[1] Anthony Hey J G . Feynman and computation:exploring the limits of computers . Cambridge, 1999 [2]Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer . In:Proceedings of the Royal Society , 1985. 97~117 [3]Yao A. Quantum circuit complexity . In:Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science . IEEE Computer Society Press, 1993. 352~361 [4]Simon D. On the power of quantum computation . In:Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science . IEEE Computer Society Press, 1994. 116~123 [5]Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J]. SIAM Journal on Computing, 1997, 26(5):1484~1509 [6]Grover L K. A fast quantum mechanical algorithm for database search . In:Proceedings of 28th STOC . New York:ACM Press, 1996. 212~219 [7]Schneier B. Applied cryptography (second edition) [M]. John Wiley & Sons Press, 1996 [8]Boyer M, Brassard G, Hoyer P, et al. Tight bounds on quantum searching[J]. Fortsch Phys, 1998, 46(4,5):493~506 [9]Nielson M, Chuang I. Quantum computation and quantum Information . Cambridge University Press, 2000 [10] Lavor C, Manssur L, Portugal R. Grover's algorithm:quantum database search . arXiv:quant-ph/0301079 [11]Grover L K. Quantum search on structured problems [J]. Lecture Notes in Computer Science, 1999, 15(9):126~139 [12] 夏培肃,量子计算[J].计算机研究与发展,2001,38(10):1153~1171 Xia Peisu. Quantum computation[J]. Chinese Journal of Computer Research and Development, 2001, 38(10):1153~1171(in Chinese) -
点击查看大图
计量
- 文章访问数: 2580
- HTML全文浏览量: 16
- PDF下载量: 1576
- 被引次数: 0
下载:
