The Design Of Quantum Algorithm Of Set Operation And Its Application

Quantum computation and quantum information is a new research field and interdiscipline of physics, mathematics, computer and information sciences. The idea of quantum computation and quantum computer was firstly presented by the great physicist Feynman. It is a wonderful combination of the theory of quantum mechanics and classical computation. Quantum computation has obviously higher performance than classical computation and has universal application. It has been concerned by many national governments and research groups. The technique of quantum information is derived form the quantum properties, such as quantum coherence, non-locality, entanglement. It has some new properties that could solve the difficulties of current information technique. In 1994, Peter W Shor presented an algorithm that can solve the problem of finding prime factorization of integer within polynomial running time. The factorization problem is the foundation of RSA cryptology, and is thought no efficient method to solve it on classical computer. Shor's algorithm breaks cryptology RSA and demonstrates that quantum computer is more powerful than classical computer.Algorithm is the kernel of classical computation as well known, and this situation is same to quantum computation. In fact, the boom of quantum computation and information comes from the presentation of Shor's algorithm. Currently, the most representative algorithms are only two. And one is Shor's algorithm. The other is Grover's algorithm. Only O ( N) steps of computation are cost by Grover's algorithm to find a marked element in an unsorted database with size N , while O ( N) steps are needed for classical compute. Quantum algorithm is a difficult research topic. The famous researchers include Cleve, Ekert, Mosca, Kitaev, Brassard, Hoyer, Boyer, et al, in the world. And in China, the famous researchers include Long Gui-Lu (Tsinghua University), Li Da-Fa (Tsinghua University), Dong Dao-Yi (Zhejiang University), Zhou Ri-Gui (Tsinghua University), and so on.In this thesis, the motivation is to study quantum algorithm. And two candidate topics are thought. One is how to load classical data information onto quantum sate. And the other is to study quantum algorithm for the search problem that complex computing is required.As well known, before processing the data, we should load data into registers. The time complexity of loading scheme is the efficiency bottleneck of classical computer, which cost O ( N )steps of running time. It is the basic computation progress of electronic computer that loading data into registers one by one via I/O(input/output) equipments, then executing computation instructors one by one to change the status of bits of register. If it has huge amount of elements to processing, this method of loading scheme is inefficient and it is difficult in classical computing theory. In addition, the classical data cannot be processed directly by quantum computer. It only processes quantum state. Therefore, it must have a quantum loading scheme (QLS), and it will be introduced in the thesis. The fast computation of set operation is very important, and it is the base of many sides of sciences and techniques, such as database operation, image processing, signal processing. But, for the set with high-dimension unsorted vectors, electronic computer can do nothing for the requirement of fast computation. Therefore, we need new computation principle and new algorithm for set operations. In this thesis, for those difficulties we present a new algorithm-quantum set operation and an application of it to the task of signal processing. Moreover, for the efficiency bottleneck of classical register, a new method of QLS is presented.In this thesis, the main research work consists of three parts:1.The first part is the review of quantum computation, especially quantum algorithm. The conceptions and principles related to quantum computation, Shor's algorithm, Grover's algorithm, and Boyer's algorithm are introduced. Boyer's algorithm is the important improved Grover's algorithm2.The second part is the introduction of QLS that can load classical data information into quantum superposition states with O (log N ) steps of computation. Then the method of rotation on the subspace is introduced, which is related to quantum search algorithm.3.The third part is the design of quantum algorithm of set operation. Then its application to signal processing is proposed.