Research On One-dimensional Three-state Discrete-time Quantum Walk And Its Application In Clustering Analysis

Quantum walk is the generalization of classical random walk in quantum s-cenario. It opens a new window on the design of quantum algorithms and has achieved a enormous success in various problems, such as search problem, element distinctness, finding triangles in graphs and so on. Moreover, it has been shown that quantum walks are universal for quantum computation. Therefore, quantum walk has become one of the most active quantum computing research area. Generally speaking, there are two major types of quantum walks, discrete-time quantum walk (DTQW) and continuous-time quantum walk (CTQW). The key difference between them is that DTQW has an extra coin system. In addition, DTQW evolves at discrete time intervals, while CTQW at any time. In this thesis, we restrict our at-tention to DTQW. Specifically speaking, three works on one-dimensional three-state DTQW have been done.1. Two families of three-state quantum walks with single-point phase defects are proposed. At each step, the walker of the proposed models gain an extra phase at the designated position. We numerically investigate the properties of two models via the position probability distribution, the position standard deviation, and the time-averaged probability at the designated position. It has shown that three characteristic peaks of the distribution and localization effect for a special initial coin state can be governed by the phase defect's position and strength. Especially, we find that the initial coin state |?2-) may be a variation of the dark state for|1), which is not found in other quantum walks.2. Two kinds of one-dimensional three-state discrete-time inhomogeneous quantum walks (IDTQWs) are proposed. In the first one model, a time-dependent coin is introduced. Another model is constructed by introducing a position-dependent coin. By selecting the appropriate coin parameters, localization effect, quasi-periodicity and periodicity can be observed in two models. Moreover, it has shown that these phenomenon is independent to the initial coin state.3. A quantum clustering algorithm based on the one-dimensional three-state quan-tum walk is proposed. In this algorithm, each data point is regarded as one particle. Then, these particles perform the three-state quantum walk. After that, according to the particles'measurement results, the attribute values of the corresponding data points are updated. At last, the data points belonging to the same group will gather together, while those belonging to different group will be separated. The simulation results have demonstrated that the proposed algorithm is effective.