Research On Discrete Quantum Walks

The 21st century is a century of developmental high-information society. Electronic computer is the key of the development of society. However, at present, the development speed of electronic computer technology becomes more and more slowly. Some reasons to this phenomenon are as below:first of all, highly integrated electric circuit contributes to electric leakage and higher calorific power; secondly, a mass of NP-problem cannot be solved efficiently by electronic computer; at third, the security of classical secure communication, which is based on computational complexity, is seriously threatened by the capability of quantum computation. To solve these problems, we need to find new compute platform. Quantum computer is the most efficient computer model in all those new compute platform.Quantum computer utilizes physical property of quantum to compute. Quantum computer can realize highly parallel computing by unitary transform quantum superposition state. So quantum algorithm can solve some NP-problem exponential faster than classical algorithm. Here are some remarkable quantum algorithm types:quantum algorithm based on Quantum Fourier Transform (QFT); quantum searching algorithm based on unstructured database; quantum algorithm based on Quantum Walks (QW) and etc.. Among those algorithm types above, we consider quantum walks mostly. Quantum walks is the quantum counterpart to the classical random walks. And quantum walks can be split into two parts: discrete quantum walks (DQW) and continuous quantum walks (CQW). In this paper, the research emphasis is discrete quantum walks. The research field on DQW can be divided into four fields:how to analyze quantum walks; algorithm based on quantum walks; universal computation by quantum walks; realize quantum walks by quantum reversible logic synthesis. This paper focuses on researching algorithm based on quantum walks and realizing quantum walks by quantum reversible logic synthesis. This paper presents some optimized searching algorithms based on quantum walks and quantum reversible logic synthesis schemes for quantum walks on lots of data structure, and made some achievements, which are listed as follows: 1) Reed-Muller expansion algorithm based on Ring-Sum-Expansion is presented. According to the process that transforming Disjunctive-Normal-Form to Ring-Sum-Expansion, algorithm extracts binary code from true table to output every output variables’s Reed-Muller expansion respectively. Compared with current algorithm, the proposed algorithm has more agility that it can create appointed output variables’s Reed-Muller expansion separateness which current algorithms cannot do. In many cases, it is need to synthesize quantum circuit with not care, which means there is need to output variables’s Reed-Muller expansion separateness. So the algorithm this paper presents has more practicability. 2) The design proposal for low cost quantum reversible comparator based on novel reversible gate is presented. In quantum computing, it is often need to judge the value of target state by Oracle operate which is the atomic operation in analyzing query complexity of quantum algorithm. So we need to consider the cost of the Oracle operate seriously. In all the decision accounting operation, comparison operation is the most frequently-used operation. Therefore, it is very important to realize quantum comparator. This paper ingenious use the theory of code to solve irreversible logic synthesis and provide the scheme for cascading reversible gates to reversible comparator. Compared with comparator circuit presented before, this circuit has lower cost.3) Quantum reversible logic circuit for one-dimensional quantum walks based on NCP quantum gates library and Reed-Muller expansion algorithm which based on Ring-Sum-Expansion is presented. According to the features of the one-dimensional quantum walks, this circuit is divided to two parts, one part is quantum coin tossing and the other one part is S operation which decides how to walk based on the quantum coin tossing. Besides the work above, this paper detailed analyses the S operation and build a mathematical model of the S operation and use controlled add-sub circuit to realize the S operation. The circuit studied in this paper describes element operation of the one-dimensional quantum walks, and make this modular which contribute to the realization for the algorithm of one-dimensional quantum walks. Depend on the primitive recursive, Mathematical expression of every step of the one-dimensional quantum walk is given and this expression can facilitate more in-depth study later on the one-dimensional quantum walks algorithm.4) On the basis of reversible logic circuit for one-dimensional quantum walks, this paper presents quantum reversible logic circuit for quantum walks onmulti-dimensional lattice and the quantum reversible logic circuit for quantum walks on graph.5) This paper bat around the Grover searching algorithm. To solve the problem that how to use Grover searching algorithm to search target state in a part-database, this paper improve the invers mean operator, which contribute to increase the probability of searching the target state in a really database. In Grover searching algorithm, the final probability of getting the target states is depending on the iterations. At present, lots of researches gave the bound of iterations, not the exact number. And the iterations will not be calculated if the number of target states is unknown. So the question is how to perform Grover searching algorithm without the number of target states? Assuming an operator which can judge the sign of the phases of superposition state, based on this technical, this paper shows a novel solution, which can perform Grover searching algorithm even if the number of target states is unknown. This solution only needs adding one gate, which can judge the sign of phase, and one more time Oracle call than the original algorithm. Beside this, this solution improves the probability of getting target state in a lower searching space.6) This paper presents an extensible graph of the quantum walks searching algorithm which simulates the Grover searching algorithm. And this paper detailed analyses this quantum walks searching algorithm.7) In order to solve the multi-objective searching problem by the quantum walk way, this paper presents a novel quantum algorithm by constructs a new quantum coin operator. This new coin operator can amplify the amplitude of the incoming edges of the target vertex, and then the amplitude of the target vertex will increase by performing the migration operator S. This algorithm improves the searching probability close to 1 by checking the neighbor node. Furthermore, this paper embeds the Adaptive iteration control of Grover searching algorithm to the multi-objective searching algorithm based on the quantum walk on the hypercube.In the near future, the author will do research on analyses the DQW and CQW; make use of the phase control technology in more quantum algorithm; realize more quantum algorithm by quantum reversible logic synthesis.