【作者】 李丹；

【导师】 温巧燕；

【作者基本信息】 北京邮电大学 ， 计算机科学与技术， 2016， 博士

【摘要】 量子力学和计算原理是20世纪人类最重要的两个智力成果。而两者的一个最新的结合点就是量子计算。量子计算是一个利用物理系统的量子力学特性,来实现在有限时间过程解决问题的科学领域。量子计算作为现代科学的一个重要组成部分,也是一种新兴的计算方式,依托于量子物理与量子计算机。量子计算的发展可以明显的增大解决特定问题的处理能力,并且可以模拟复杂物理系统,而这都是经典计算机无法实现的。量子漫步作为经典漫步的推广,是量子计算的基础和重要工具,被视作实现量子计算的一种主要模型。量子漫步利用量子态的叠加性,可以同时行走在不同的线路上,故比经典漫步效率有了指数级的提高。而且漫步者位置的概率分布也与经典漫步有着截然不同的形式,这给予了量子漫步更多的奇特性质,有益于提出量子算法,并被广泛的应用于量子算法的开发过程中。本文主要研究不同种类的离散型量子漫步模型,并考虑其应用背景,内容涉及懒惰型量子漫步、两粒子交互型量子漫步、闭合曲面上的量子漫步、量子有记忆漫步。论文的具体内容如下:在直线上的懒惰型量子漫步方面,①分析了懒惰型量子漫步的时间极限行为。②验证了懒惰型量子漫步的位置态和硬币态之间的纠缠关系远远大于普通量子漫步,趋近于最大可能值。③提出了占有数和占有率两个统计量,发现懒惰型量子漫步在有相同的时间极限行为的同时,却拥有更高的占有数和占有率,发掘了懒惰型量子漫步潜在的优势。在一维图上两粒子交互型量子漫步方面,①提出了受控的两粒子交互型量子漫步。②研究了受控的两粒子交互型量子漫步的位置概率分布的特性,计算了直线上和奇圈上的受控的两粒子交互型量子漫步的高阶矩,还度量了受控的两粒子交互型量子漫步中两粒子之间的联系。③根据受控的两粒子交互型量子漫步,提出了一种不依赖于数学困难问题的量子哈希机制,并分析了该机制的安全性,弥补了没有量子哈希机制的空缺。在闭合曲面上的量子漫步方面,①研究了圆柱面上的量子漫步的跨越边界的性质。②研究了莫比乌斯带上的量子漫步的跨越边界的性质。在正则图上的量子有记忆漫步方面,①发现了有记忆的量子漫步和无记忆的量子漫步之间的联系。②通过将有记忆的量子漫步映射到原图的线图上的无记忆量子漫步,提出了通用的量子有记忆漫步模型,提供了构建任意量子有记忆漫步的方法。③研究了直线上的记忆为1的量子漫步的性质,包括方差、占有率和局域性。更多还原

【Abstract】 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.更多还原