Analysis And Applications Of Discrete Quantum Walks

Quantum Mechanics and the Theory of Computation are two of the most important intellectual achievements of the 20th century. One of the most recent joint ventures between physics and the theory of computation is Quantum Computation. Quantum computation can be defined as the scientific field whose purpose is to solve problems with finite time procedures, i.e. algorithms, which exploit the quantum-mechanical properties of those physical systems that are used to implement such algorithms. As a key element in modern science, quantum computation is a new kind of computation which based on quantum physics and quantum computer. We find the development of novel and powerful methods of computation that may allow us to significantly increase our processing power for solving certain problems and the simulation of complex physical systems that no classical computer would be able, even in principle, to efficiently simulate.Quantum walks, just as the name implies, are quantum counterparts of classical random walks. Quantum walks are an important tool of quantum computation and a dominated model to realize quantum computation. Quantum walks take advantage of superposition of quantum state, so a quantum walker could walk on different positions simultaneously. This provides the possibility to have exponentially high efficiency rather than classical walks. In addition, the probability distribution of position of quantum walks is totally different with that of classical walks, which brings many peculiar properties to quantum walks.These properties are beneficial to the development of quantum algorithms and are widely used.The contributions of this dissertation are mainly on different kinds of discrete quantum walks. We also consider the application of these quantum walks, including lazy quantum walks, two-particle interacting quantum walks, quantum walks on closed surfaces, quantum walks with memory. The details are as follows.For lazy quantum walks: ?We study the limit time behaviour of lazy quantum walks. ? We show that the entanglement between position state and coin state for lazy quantum walks, which converges to its possible maximum value, is higher than that for normal quantum walks. ?We show that lazy quantum walks have higher occupancy number and occupancy rate than other walks. These two concepts are introduced to explore the advantages of lazy quantum walks.For two-particle interacting quantum walks:? We present the controlled two-particle interacting quantum walks. ?We analyze the probability distribution of this kind of quantum walks, compute the moments of controlled two-particle interacting quantum walks on the line and odd circles, measure the relation between two particles of controlled two-particle interacting quantum walks. ?We present and analyze a kind of quantum Hash scheme based on controlled two-particle interacting quantum walks, whose security is not based on difficult mathematical problems.For quantum walks on closed surfaces: ?We analyze the properties of crossing boundary for quantum walks on Cylindrical Strip. ?We analyze the properties of crossing boundary for quantum walks on Mobius Strip.For quantum walks with memory on regular graphs:? TWe find the relationship between quantum walks with memory and quantum walks without memory.?Through transforming quantum walks with memory on graphs to quantum walks without memory on line digraph of the original graph, we present a generic model of quantum walks with memory, which provides a method to build any quantum walks with memory. ?We study the properties of quantum walks with memory 1 on the line, such as variance, occupancy rate, localization.