量子计算复杂性理论综述

Overview of Quantum Computation Complexity Theory

量子计算复杂性理论是量子计算机科学的基础理论之一,对量子环境下的算法设计和问题求解具有指导意义.因此,该文对量子计算复杂性理论进行了综述.首先,介绍了各种量子图灵机模型及它们之间的关系.其次,量子计算复杂性是指在量子环境下对于某个问题求解的困难程度,包含问题复杂性、算法复杂性等.于是,该文介绍了量子问题复杂性、量子线路复杂性、量子算法复杂性,并且介绍了量子基本运算和Shor算法的优化实现.第三,格被看做是一种具有周期性结构的n维点空间集合.格密码有很多优势,包括具有抗量子计算的潜力,格算法具有简单易实现、高效性、可并行性特点,格密码已经被证明在最坏条件下和平均条件下具有同等的安全性.因此该文介绍了格的困难问题,以及主要的格密码方案现状.最后,对今后值得研究的一些重要问题和量子计算环境下的密码设计与分析给出了展望.

The quantum computation complexity theory is one of the basic theories of quantum computer science, and it has guiding significance for the designing and solving some problems under the environment of quantum algorithms. Therefore, in this paper, the quantum computation complexity theory is reviewed. Firstly, this paper introduce the relationships between quantum Turing machine model and classical Turing model. Secondly, due to the quantum computational complexity is the degree of difficulty under the quantum environment for problem solving, including the complexity of the problem, the complexity of the algorithm and so on, this paper describes the quantum complexity of the problem, quantum circuit complexity, the complexity of quantum algorithms, and introduces the basic optimization for quantum computation and Shor algorithm. Thirdly, the lattice has n-dimensional periodic structure in space. Lattice based cryptography has many advantages, including post-quantum computation potential, lattice algorithm is simple, efficient, parallel and easy to implement, lattice cryptography has been shown to have equal safety under the worst conditions and average conditions. This paper describes some difficult problems about lattice, and the status of the main lattice cryptography scheme. Finally, the prospect about the cipher design and analysis of some important issues worthy of study and quantum computing environments is given.