Set Computation Via Quantum Computer

Quantum computation and quantum information is a new research field and interdiscipline of physics, mathematics, computer and information sciences. Since the theory of quantum computer was proposed firstly in the early1980’, more and more attentions were paid to this field and have shown to be exponentially more power than classical computer on various specialized problems. Many results form research in this field have been presented. Not only theory but also experiments have all been evolved. Especially, in1994, Peter Shor presented an algorithm that can effectively solve two very important problems:finding prime factorization of integerand solving the problem of discrete logarithm via quantum computer, which are thought no efficient method on classical computer. Grover presented another exciting algorithm for the searching in an unsorted database in1996, which can find a marked element in an unsorted database of size N in O((?)N) steps,by contrast O(N) steps on classical computer. It has been proved that Grover’s quantum algorithm is optimal on searching unsorted database. Today, more and more people pay attention on quantum computer, some of them present algorithms and some present realizing approach. For example, pattern recognition, quantum network, quantum image compression, and so on, paid many attentions. But many of these algorithms now were based on Grover’s searching algorithm, most of them can be equaled to the problems of set computation in fact CPU and memory are the most important parts of computer,"CPU+memory=Computer". In the same way, quantum memory is one the most important part of quantum computer. Pang presented a quantum loading scheme (QLS) to make quantum computer compatible with classical memory. The QLS can load all vectors of set into quantum register at one time. Grover’s algorithm is finite in searching complicated database. It can only operate qubits in global space not for subspace, i.e. it can not operate on parts qubits but keep others. Pang’s algorithm—the quantum VQ iteration which is a rotation over subspace has solved this difficulty.Set computation is a fundamental calculation in mathematics. It is a basic theory and application in many sides of science and technology, such as signal process, pattern recognition, and so on. But, there is a difficult for classical computer while set contain a large number of elements, for example:recognizing genuine targets real time from the disturbed signal which has giant amount of data is inefficient on classical computer. These elements are called vectors in this paper. It is an efficiency bottleneck of classical computer. In this paper, we firstly present an integrated and complete quantum algorithm for set computing that based on quantum loading scheme (QLS) and the rotation over subspace, which can efficiently solve a class of problems of set computing via quantum computer.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 withO (logN)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.