量子计算算法设计与实现方法研究

The presentation of Shor’s and Grover’s quantum algorithm, which shows the powerful ability of quantum computer in parallel computation, brings huge impact to the modern cipher. And the quantum computation gains much more focus. However, there are some difficult problem, which can’t be solved on quantum computer. Thus it is badly in need of designing new quantum computation, which can provide a basis of the cryptographic security. It is difficult to produce big dimension on the current technology. And it is also need to do research on the implementation of quantum computation. But implementing quantum computation is costly and difficult. And researchers begin to explore simulation for quantum computation on classical computer. In this project, we will study designing, implementation and simulation of the quantum computation.

Shor量子计算算法和Grover量子搜索算法的提出，使得量子计算机的强大并行计算能力得到了充分展示，对现代密码提出了严峻的挑战，量子计算算法的研究越来越受关注。量子计算机并不是万能的，不能有效的解决所有困难问题，因而亟需设计新的量子计算算法，为现代密码安全性提供理论依据。在现有技术条件下，大维数量子寄存器难于生成，因而同样需要研究量子计算算法的实现方法。然而在量子计算机上实现量子计算算法的代价高且操控难，因而，研究学者开始探索在经典计算机上仿真量子计算算法的方法。为此本课题将深入研究量子计算算法的设计，重点研究量子计算算法的实现方法，探讨研究量子计算算法的仿真方法。

自Shor算法和Grover算法提出以后，量子计算就受到人们的广泛关注，这主要在于量子计算对现代密码学的安全性产生了重要的影响，特别是公钥密码算法。本课题主要围绕量子计算算法的设计与实现方法两个方面展开研究。. 在量子计算算法设计方面，主要以量子搜索算法为研究对象。首先针对Chor-Rivest背包公钥密码的背包向量的重量固定特点，基于时空折衷法，提出了基于目标解重量固定的量子中间相遇搜索算法，并给出了量子二分检索法。然后针对相干在量子算法中的作用对分析量子加速的原理具有重要意义，利用相干的联合熵量化方法系统地分析了相干在绝热量子搜索算法中的作用。最后设计了一种多相位互补量子搜索算法。本课题研究的这些算法，可为现代密码在量子计算模式下的安全性提供理论依据。. 在量子计算算法实现方面，主要以量子Fourier变换为研究对象。首先针对在现有技术条件下难于实现大维数量子Fourier变换的问题，实现了一个资源节约的方法，并基于该方法实现了Shor算法，且能在IBM量子云计算机上成功分解整数N=15。然后，针对现有广义量子Fourier变换的实现方法要么不具有普适性，要么不具有精确性，给出了广义量子Fourier变换的逐比特实现方法，并设计了其精确的实现线路。最后，提出了线性光学平台的确定性Toffoli门实现方案。本课题提出的这些实现方法，可加速Shor算法实用化进程，同时还为算法在线性光学量子计算平台上实现提供理论基础。