Algorithms Based On Quantum Walks And Algorithm Design

Equipped with quantum superposition and quantum entanglement, quantum computation can achieve amazing speedup over its classical counterpart. Algorithms is the heart of computation. It will make a great different to perform the same computing task with different algorithms. In the world of quantum computation this principle still holds. However, it is incredibly hard to design a powerful quantum algorithm. Because the principle of quantum mechanics is striking different from our intuition. Quantum walks, an analogue of classical random walks, provide a new method to design quantum algorithms. Therefore, we study in detail the quantum algorithms and algorithms based on quantum walks. In this paper we provide a new perspective for designing algorithms based on quantum walks. This paper is composed mainly by the following three aspects:1. A new algorithm based on quantum fourier transform is proposed. It has one more variable than quantum fourier transform. However it is still very easy to realize this new quantum algorithm on quantum circuits.2. Scattering theory is described in detail. The implementing of quantum gates with scattering theory also is included.3. The relation between quantum walks on edges and vertices is proposed. Quantum walks on vertices can be regarded as spectrums operation of quantum walks on edges. As a result we can design algorithms based on quantum walk in frequency domain.