集合运算在量子计算机上的实现

发布时间：2018-03-09 08:57

本文选题：量子计算　切入点：量子集合算法　出处：《四川师范大学》2012年硕士论文　论文类型：学位论文

【摘要】：量子计算与量子信息是涉及物理学、计算机科学、数学以及信息科学等多个学科的新兴综合性交叉研究领域。在处理众多特殊问题上,量子计算机展示了它比传统计算机,更加优越的巨大潜力。例如：1994年,petershor提出的算法能在量子计算机上有效的解决两个非常重要的问题：整数质因数分解、离散对数问题,这些问题在传统计算机上都是不能有效的被解决的。在量子计算的研究中,计算性能的优越性主要体现在算法的有效性上。目前为止,被公认的最具代表性的量子算法有Shor的大数质因子分解算法以及Grover提出的数据库搜索量子算法。然而,Grover搜索算法在搜索复杂的数据库时存在着很大的足限性,因为Grover搜索算法只能处理在全空间中的量子比特,而不能处理在子空间中的量子比特。例如,它在处理部分量子比特时不可能保持另一部分量子比特不变。此外,数据在被处理之前,必须先加载到寄存器中,才能完成处理任务。但由于经典的数据是通过输入输出设备,被逐个的加载到寄存器中去的。输入输出设备由于其逐个加载数据的方式,严重地拖慢了计算机的运算速度,从而成为经典计算机的效率瓶颈。量子计算机又不能直接处理经典的数据信息,只能对量子态进行处理。要对量子态进行处理必须把经典数据加载到量子态上,因此必须有一个针对量子计算机的数据存储方案。这正是本文将研究的量子数据加载方案(QLS)。数据库操作、信号处理、图像压缩等领域,由于其数据库的庞大性,在经典计算机上处理这类问题是非常困难的。而这些问题最终又可以归结为对集合的操作。因此在量子计算机上有效地处理集合问题,就成了解决上述问题的关键。基于以上问题,在这篇文章中,提出了基于量子装载方案(QLS)和旋转子空间理论的量子集合算法,能够在量子计算机上有效地解决集合运算类问题。本文分为以下三个部分：第一部分对量子计算的历史概况进行了简述,以及量子计算的准备知识。对历史上比较重要的量子算法进行了重点分析,如shor因子分解算法、Grover搜索算法等已被提出的算法。第二部分这部分介绍了旋转子空间理论和量子数据加载方案(QLS),同时也介绍了针对Grover量子搜索算法而提出来的Ggeneral,最后在这些算法的基础上提出了一个新量子集合算法。第三部分在文章最后对量子集合算法的一个运用——模式识别进行了分析。主要是从如何实现在包含大量的干扰信号中实时地识别出真实的目标这方面进行了详细的分析。
[Abstract]:Quantum computation and quantum information is involved in physics, computer science, new comprehensive interdisciplinary research field of multiple disciplines of mathematics and information science and so on. In dealing with many special problems, quantum computer shows its great potential than traditional computers, more superior. For example: in 1994, petershor proposed the algorithm can effectively solve two a very important problem in quantum computer: integer factorization and discrete logarithm problems, these problems are not effectively solved in the traditional computer. Research in quantum computing, superior computing performance is mainly reflected in the effectiveness of the algorithm. So far, the most representative of the quantum algorithm the recognized Shor large number factorization algorithm and quantum algorithm proposed by Grover database search. However, the Grover search algorithm in the search of complex database storage In a big foot limiting, because Grover search algorithms can only handle qubits in whole space, it can not deal with the qubit in the subspace. For example, it is not possible to keep the other part of a quantum bit qubit constant in the processing part. In addition, the data before the treatment, must be loaded to register, to complete the processing tasks. But due to the classic data is through the input and output devices, one by one is loaded into the registers to input and output devices. Because of its loading data one by one way, seriously slow down the computer operation speed, thus becomes the efficiency bottleneck of classical computer. Classical quantum direct processing the computer can not only information on the quantum state for processing. For the quantum state must be loaded into the classic data processing of quantum state, so it must be for a quantum computer This is the data storage scheme. This paper will study the quantum data loading scheme (QLS). The database operation, signal processing, image compression and other fields, because of its huge database, it is very difficult to handle this kind of problem in classical computer. These problems can be attributed to as set operation. So in a quantum computer effectively deal with a collection of problems has become the key to solve the above problems. Based on the above problems, in this article, based on the proposed quantum loading scheme (QLS) and quantum rotation subspace theory set algorithm, can effectively solve the problem of set operations in a quantum computer.
This article is divided into the following three parts:
The first part introduces the history of quantum computing and the knowledge of preparation for quantum computation. The important algorithms in history are analyzed, such as shor factorization algorithm and Grover search algorithm.
The second part introduces the theory of spin subspace and the loading scheme of quantum data (QLS). At the same time, it also introduces the Ggeneral proposed for Grover quantum search algorithm. Finally, based on these algorithms, a new quantum set algorithm is proposed.
The third part, at the end of the paper, analyzes the application of quantum ensemble algorithm -- pattern recognition. It mainly analyzes how to reallocate real targets in a large number of interfering signals in real time.

【学位授予单位】：四川师范大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：O413;TP38

【参考文献】