量子自动机.doc

量子自动机及其应用 1 背景 当今,计算机技术日新月异,芯片的集成度不断提高,计算速度成指数式提高,据此,摩尔给出了一条不精确的经验性定律:计算机的计算速度每18个月就翻一翻按照此定律,鞋片上的集成电路最终会小到一个极限,此时微粒的波粒二象性将变得十分显著,电路不再服从经典力学规律,而服从量子力学规律.为此,人们提出了量子计算与量子计算机的思想。20世纪80年代初，Benioff和Feynman首先提出了量子计算机的构想。其后，Deutsch将他俩的思想形式化并引入了量子Turing机的概念，在1994年以后,量子计算的研究日益活跃。并提出了量子并行操作技术。在 1936 年,Birkhoff 和 von Neumann提出了量子逻辑.它源于量子力学的形式化。由于量子力学系统可由Hilbert 空间的闭子空间来描述，而Hilbert 空间的所有闭子空间构成正交模格，有些文献定义量子逻辑为正交模格，将量子逻辑定义为完备的正交模格值逻辑，从而提出了基于量子逻辑的自动机理论，即 l值自动机(量子自动机）。量子自动机是量子计算机的数学模型，对研究量子计算机有理论义。 2 知识储备 2.1 希尔伯特空间理论 定义1 设X是复线性空间,如果对X中任何两个向量x,y,有一复数x,y与之对应,并且满足下列条件: 因此，可以设X是一个内积空间，并且由内积导出的范数完备，则称X为希尔伯特(Hilbert)空间。 2.2 格论基础 定义2 设P是一个集合，P上的二元关系≤叫做一个偏序关系,如果满足: 自反性：a≤a，(?a ∈P); 反对称性：a≤b，b≤a = a = b，( ? a,b ∈P); 传递性：a≤b，b≤c = a ≤c，(?a, b, c ∈ P); 这时称(P, ≤）为一个偏序集。 给定一个偏序集P,则对于?a, b∈p,只可能存在四种关系： a b，(2) b a；(3) a = b；(4)a与b不可比较。 定义3 若偏序集(P,≤ )的最大元存在,叫做P的单位元,用I表示,若偏序集(P,≤ )的最小元存在,叫做P的零元,用O表示,I O统称为P的泛界。 定义4 设(L,≤ )是一个偏序集,如果任意两元x, y都有上确界xVy和下确界x∧y,则称偏序集(L,≤ ) 为一个格。 定义5 设格(L,≤ )具有泛界I和O，x，y∈L，x∧y = O， xVy = I，则称y是x的一个补元。 性质 ：在格(L,≤ )中,对任意x， y， z∈L有： 例：图1为由四个元素构成的最简单的分配格： 2.3 量子计算机 量子计算机是以量子器件为硬件支持，能够实现量子计算的量子信息处理工具。是进行量子计算的设备，其计算过程由算法决定，不同的算法有不同的酉变换。量子计算机的计算过程与量子程序的执行过程一致，如图2所示，图中的Ui（i=1,2，...，n）均为酉变换。量子计算机具有经典计算机所无法比拟的高速并行计算能力 图2 量子计算机的计算过程 一般认为，量子计算机的物理实体应由两部分组成：量子部分和经典部分。由于量子计算的效力主要表现在对数据的强大处理能力，一般倾向于由量子部分处理数据而由经典部分处理控制。也就是用经典的计算机来控制量子设备对量子位进行操作。这样的组织结构主要考虑到量子计算机实现的工程问题（多量子位联合参与控制与计算非让困难性）。图3给出了一个简单的量子计算机的控制示意图。由于量子计算的测量结果是概率性的，需要计算和测量多次，才能得到所需的结果。 图3 量子计算机的控制 由图3可知，经典计算机与量子计算机在计算开始之前和结束之后需要进行信息的交互，在这两个时刻由于量子计算机中的量子位的状态处于稳定的基态（或尚未形成叠加态，或已经过测量而处于坍缩），因此，这样的组织结构并不破坏量子计算机的封闭性。 量子并行是量子计算机的特点，对于串行计算，量子计算机并不具有优势。在通用的量子计算机出现之前，量子计算机适合于作为经典通用计算机的高速协处理器或者外围专用处理机，或专门为实现某种量子算法或模拟某种量子量子系统的专用计算机。目前研究的量子计算机原则上都是连接在经典通用计算机上的专用处理机，它的程序设计语言是在通用计算机的程序设计语言中增加一些支持量子计算的成分。 量子计算机的构造： 通用量子图灵机是一个抽象的理论模型,那么如何实现这种通用量子计算机呢?经典计算机是由以与非门构成的电子网络来近似图灵机的。因此构造量子计算机的任务自然也归结到建立一个由量子逻辑门构成的网络。量子门网络由“源、线、门”三部分构成,如图4所示。(a)源—能够提供处于标准态的量子比特,如两能级原子态,光子偏振态,自旋1/2粒子的量子态等。(b)线—能够实现单位变换,把量子态|ji从某处转移到另一处,这实际上是理想的量