【作者】 李敏；

【导师】 郭光灿； 张永生；

【作者基本信息】 中国科学技术大学 ， 光学， 2013， 博士

【摘要】 量子随机行走作为经典随机行走的量子推广,自1993年被提出后,就受到广泛的关注,近年来,吸引了许多数学家,计算机科学家,物理学家及工程师等的注意。量子随机行走已经成为量子算法的一个重要工具,一系列基于量子随机行走的量子算法被提出,其中一些到达问题相对于经典算法具有指数加速,搜索问题也达到了O(√N)这一最佳效率,且量子随机行走已被证明可以用于普适量子计算。为了更好的发挥量子随机行走的潜力,我们需要对量子随机行走的各种基本性质有更深的了解,包括方差,熵,到达时间,混合时间,平均位置等有更精确的结果,还有更多情形下量子随机行走需要得到研究。本文主要研究量子随机行走的一些基本性质及应用,包括：1.介绍量子随机行走的的定义,及量子随机行走和经典随机行走的区别。介绍了两种研究一维量子随机行走的方法：Fourier变换方法和排列组合方法,还有利用3变量幺正算UξθS作为硬币,来控制离散量子随机行走的演化,最后还介绍了基于量子随机行走的一些量子算法和普适量子计算的方案,以及多粒子纠缠在量子随机行走中的表现。2.研究使用任意幺正算符作为硬币的离散量子随机行走,我们发现当初始态为平衡态1/(?)(|OL>+i|OR>)时,其平均位置满足更多还原

【Abstract】 Quantum random walks (QWs), as the quantum version of classical random walks, since was introduced in1993, have been widespread concerned. Recently, QWs have attracted great attention from mathematicians, computer scientists, physicists, and engineers. Quantum walks have been exploited as an useful tool for quantum algorithms in quantum computing. A list of quantum algorithms based on QWs have already been proposed. QWs can be used to perform an oracle search on a database of N items with O((?)N) was proved, and in some problems, the hitting time is exponential faster than its corresponding classical random walk, QWs can also be used for universal computation.In order to use the quantum walk to its fullest potential, we need to have a deeper understanding of the basic nature, including standard deviation, entropy, hitting time, mixing time and average position etc., we need more precise results about them and QWs in more situations need to be discussed.In this dissertation, we mainly concentrated some basic properties and appli-cations of QWs. It contains,1. We give the definition of quantum random walk, and the basic difference between classical random walk and quantum random walk. Two methods for computing one-dimensional QWs:Fourier transform method and per-mutations method were introduced. Using3parameters unitary operation to control the evolution of QWs, some algorithms, the solution of universal quantum computing and the evolution of multi-particles in QWs were also introduced,2. We investigated discrete-time quantum walks with an arbitary unitary coin. Here we discover that the average position (x)=max((x))sin(α+γ), while the initial state is1/(?)2(|OL)+i|OR)). We prove the result and get some symmetry properties of quantum walks with a U(2) coin with|OL) and|OR) as the initial state.3. We investigated the discrete-time quantum random walks on a line in peri-odic potential. The probability distribution with periodic potential is more complex compared to the normal quantum walks, and the standard devia-tion a has interesting behaviors for different period q and parameter θ. We studied the behavior of standard deviation with variation in walk steps, pe-riod, and θ. The standard deviation increases approximately linear with θ and decreases with1/q for θ∈(0, π/4), and increases approximately linear with1/q for θ∈[π/4, π/2). For θ∈(π/4, π/2), it means the transmission is larger than the reflection, and become larger, with sensibility, the diffussion will be accelerated, and when θ∈(π/2,3π/4), the transmission becomes smaller and reflection becomes larger, with sensibility, the diffusion will be decelerated, but when θ∈(π/4,3π/4) and q=2, the standard deviations are nearly the same, and when and q>2, the standard deviation will decrease.4. We construct a Parrondo’s game using discrete time quantum walks. Two lossing games are represented by two different coin operators. By mixing the two coin operators UA(αA,βA,γA) and UB(αB,βB.γB), we may win the game. Here we mix the two games correlated to the positions instead of time. With a number of selections of the parameters, we can win the game with sequences ABB, ABBB, etc.. If we set βA=45°,γA=0, αB=0,βB=88°, we find the game1with Uas=Us(-51°,45°,0), UBS=Us(0,88°,-16°) will win and get the most profit. If we set αA=0,βA=45°, αB=0,βB=88°and the game2with UAS=Us(0,45°,-51°), UBS=Us(0,88°,-67°), will win most. And game1is equivalent to the game2with the changes of sequences and steps. But at a large enough steps, the game will loss at last.更多还原