ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (10): 2015-2026.doi: 10.7544/issn1000-1239.2020.20200615

所属专题: 2020密码学与数据隐私保护研究专题

• 信息安全 • 上一篇    下一篇

量子计算与量子密码的原理及研究进展综述

王永利1,徐秋亮2   

  1. 1(山东大学数学学院 济南 250100);2(山东大学软件学院 济南 250101) (wyl@mail.sdu.edu.cn)
  • 出版日期: 2020-10-01
  • 基金资助: 
    国家自然科学基金项目(61632020)

Principle and Research Progress of Quantum Computation and Quantum Cryptography

Wang Yongli1, Xu Qiuliang2   

  1. 1(School of Mathematics, Shandong University, Jinan 250100);2(School of Software, Shandong University, Jinan 250101)
  • Online: 2020-10-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61632020).

摘要: 量子计算与量子密码是基于量子效应的计算技术和密码技术.1984年Bennett和Brassard提出了第一个量子密钥分发协议,开启了量子密码学的研究,此后相继在量子加密、量子签名等领域进行了大量研究.1994年,Shor利用量子Fourier变换,设计了第一个实用的量子算法,在多项式时间内对大整数进行因子分解.1996年,Grover提出了量子搜索算法,能够对无结构数据进行二次加速.Shor算法和Grover算法的提出不仅体现了量子计算的优越性,还对传统基于数学困难问题的密码学体制造成威胁.经过半个世纪的发展,量子计算与量子密码在理论与实践的研究上都取得了丰硕的成果.从量子力学的数学框架、基本概念和原理、量子计算基本思想、量子密码研究进展及主要思想等方面进行总结梳理.

关键词: 量子计算, 量子密码, Shor算法, Grover算法, 量子密钥分发

Abstract: Quantum computation and quantum cryptography are based on principles of quantum mechanics. In 1984, Bennett and Brassard proposed the first quantum key distribution protocol called BB84, which started the study of quantum cryptography. Since then, a great deal of work has been carried out in various fields such as quantum encryption and quantum signature. In 1994, Shor designed the first practical quantum algorithm which can factor large integers in polynomial time. Shor’s algorithm used Quantum Fourier Transform, which is the kernel of most quantum algorithms. In 1996, Grover designed a new algorithm which can search the unstructured data to get the required result in the time of approximately the square root of the total account of the data. Shor’s algorithm and Grover’s algorithm not only embody the advantages of quantum computing, but also pose a threat to the traditional cryptography based on mathematical difficulties such as RSA. After half a century’s development, quantum computing and quantum cryptography have achieved fruitful results in theory and practice. In this paper, we summarize the contents from the perspectives of the mathematical framework of quantum mechanics, basic concepts and principles, basic ideas of quantum computing, research progress and main ideas of quantum cryptography, etc.

Key words: quantum computation, quantum cryptography, Shor’s algorithm, Grover’s algorithm, quantum key distribution

中图分类号: