资源预览内容
第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
第9页 / 共14页
第10页 / 共14页
亲,该文档总共14页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
量子自动机及其应用1背景当今,计算机技术日新月异,芯片的集成度不断提高,计算速度成 指数式提高,据此,摩尔给出了一条不精确的经验性定律:计算机的计 算速度每18个月就翻一翻按照此定律,鞋片上的集成电路最终会小到 一个极限,此时微粒的波粒二象性将变得十分显著,电路不再服从经典 力学规律,而服从量子力学规律.为此,人们提出了量子计算与量子计 算机的思想。20世纪80年代初,Benioff和Feynman首先提出了量 子计算机的构想。其后,Deutsch将他俩的思想形式化并引入了量子 Turing机的概念,在1994年以后,量子计算的研究日益活跃。并提出 了量子并行操作技术。在1936年,Birkhoff和von Neumann提出了 量子逻辑.它源于量子力学的形式化。由于量子力学系统可由Hilbert 空间的闭子空间来描述,而Hilbert空间的所有闭子空间构成正交模 格,有些文献定义量子逻辑为正交模格,将量子逻辑定义为完备的正 交模格值逻辑,从而提出了基于量子逻辑的自动机理论,即1值自动 机(量子自动机)。量子自动机是量子计算机的数学模型,对研究量子 计算机有理论义。2知识储备2.1希尔伯特空间理论定义1设X是复线性空间,如果对X中任何两个向量x,y,有一复数与之对应,并且满足下列条件:1. 那尤二0,且(xrx) = 0等价x = 0, x E X;2. ax + py,z) = axtz) + pyfz, xf yf z EX, a, 0为复数:3. (x,y) = (ytx)7 x, y eX,贝!J称(笥刃为尤与y的内积,X称为内积空间.由于xtx 0,令|尤|= 念审,则容易证明|灿是X上的范数.由此 可见,用内积可以导出范数,所以内积空间是一种特殊的赋范空间.因此,可以设X是一个内积空间,并且由内积导出的范数完备,则称X为希尔伯特(Hilbert)空间。2.2格论基础定义2 设P是一个集合,P上的二元关系W叫做一个偏序关系,女口 果满足:自反性:aWa,(V a WP);反对称性:aWb, bWa = a = b, ( V a,b WP);传递性:aWb, bWc = a Wc, (V a, b, c W P);这时称(P, W)为一个偏序集。给定一个偏序集P则对于V a, b Wp,只可能存在四种关系:(1)a b, (2) b 从某处转移到另一处,这实际上是理想的量子通道。(c)量子逻辑门 能够对输入的量子比特进行操作,这实际是具有某特定功能的量子 信息处理器,其输出为ijout=uijin,幺正变换U描述该逻辑门的功能。怨T逻辑i丨 逻辑门-丨忖2U1图4量子网络Deutsch证明能够采用一种通用量子逻辑门来实现量子网络,我们 称之为D门。其后他发现几乎所有的三比特量子逻辑门都是通用逻 辑门。接着A.Barenco和D.Divincenzo各自独立地证明了可用两比特 的量子逻辑门来构造D门。后来,Deutsch和S.Leoyd又各自证明,几乎 所有的两比特门都是通用的。最近Barenco等人给出一个最新结果, 他们用一个对两比特操作的受控非门和对单个比特进行任意操作的 量子门构成了一个通用量子门集。因此,为建造量子计算机,实验物理 学家只需要寻找实现对一个量子比特进行任意操作和对两个量子比 特的受控非(又称异或)操作。前一类操作在量子光学中已经解决了 : 应用Ram-sy场可以将二能级原子制备到任意态上,或者利用其它量子 态工程的方法将两能态体系制备到所需要的量子态上。于是如何实现 量子受控非门便成为量子计算机成功与否的关键。3量子自动机31量子自动机的概念量子逻辑是指真值为完备正交模格的逻辑,也称为正交模格值逻 辑。定义6正交格是七元组1 = (L,A,V,丄,0, 1),其中:1) 1 = (L, W, A, V, 0, 1)是完备格2) 一元运算 丄是L上的正交补,对任意的a,b e L,满足如下条件: a A 8丄=0, a V 8丄=1;(ii) a丄丄=a;(iii) a W b蕴含b丄W a丄。定义7 设1 = (L,W,A,V,丄,0, 1)为正交格,a, b e L, 若a = (a A b) V (a A b丄),则称a和b是可换的,记作aCb。 一个正交模格就是满足如下正交模律的正交格,对任意的a, b e L, 有:(iv) a W b 蕴含 a V (a 丄 A b) = b。定义8 设1 = (L,W,A,V,丄,0, 1)是一个完备的正交模格, 工是一个有限字母表,定义在工上的量子自动机(1-自动机)是一个四元 组 R=,其中:1) Q是有限状态集;2) 1匸Q是有限初始状态集;3) Tc Q是有限终止状态集;4) 6是QxZ xQ的正交模格值子集,即从QxZ xQ到L中的 映射, 为R的正交模格值转移函数” p, qeQ, Z ez ,6 (p, Z , q)表示输入Z使得状态p转化为状态q这一命题的真值。利用转移函数5,可以描述上语言的识别性.任意丫上的量子自动机R=决定工上的正交模格值一元谓词reg其定义如下:对任意 6勺 &,牝(722乐)竺(旳。张一1 Q,qk ET)pathfi(q0o-1q1 qi 弧 qQ其中,pathR(qwiqi 爬-1 乐) =(,5+讥+G 6直观上卩5(112乐)表示量子自动机R识别词。辺2臥这一命题,其真q衣_EQ,qkET *i=03.2量子自动机的分类经典自动机可以分为很多种,包括有限自动机、下推自动机、图 灵机等等。同样基于量子的自动机种类也有很多种,例如,量子有限 自动机、量子Mealy自动机、量子Moore自动机、基于量子逻辑的 下推自动机、基于量子逻辑的图灵机、基于量子逻辑的Biichi自动机、 基于量子逻辑的Muller自动机等等。量子有限自动机:基于量子逻 辑的有穷自动机(也称正交模格值有穷自动机),根据其转移关系5 是否为确定的,可分为两大类:(1)确定型量子自动机(1 DFA), (2) 非确定型量子自动机(1 NFA)。再根据初始状态和终状态是否为分 明的,1 DFA可分为三类,1 NFA可分为四类。根据I和T是 否为分明的,1 NFAR = (Q,Z ,5丄T)可分为以下四类:1) l NF A1,初始状态I和终状态T都是1-值子集;2) 1 NF A2,初始状态 I = q0W Q,终状态T是1-值子集;3) 1 NF A3,初态I是1-值子 集,终状态T = FQ是分明集合;4) 1 NF A4,初始状态I = q0 e Q和终状态T = F匸Q都是分明集合。设R = (Q,工,6 ,1, T) e A(Z , l),若对任意的q e Q, z e工,存在唯一的p e Q,使得6 (q, z , p) = 1,则称R为确定型量子有穷自动机,简记为 l 一 DFA。根据I和T是否为分明的,1 一 DFA R = (Q,工,6 , I, T)可分为以下三类:)1 DF A1,初始状态I = q0e Q,终状态T是 1-值子集;2) 1 DF A2,初始状态I是1-值子集,终状态T = F匸Q 是分明集合;3) 1 DF A3,初始状态I和终状态T都是1-值子集。 与传统有限自动机的区别:定义:有限自动机M=(Q,工,6 , q0, F,),其中,Q是状态的非空有穷集合。工输入字母表6是状态转移函数,6 : QXZ Q,q0初始状态F终止状态集合。性质:量子力学中的Hi1bert 空间的所有闭子空间以及投影本身可能不满足分配律,而是满足正交 模律。量子自动机中状态转移的可能性的大小是Hi1bert空间的一个 闭子空间。识别语言:经典有限自动机只能识别正则语言。经典的有 穷自动机一般由状态集、输入字母表和一个转移关系构成,当输入一 个字符之后,由转移关系决定状态的转移。量子有穷自动机的状态集 一般由有穷个状态的任意次叠加构成,而每次状态的转移有一个转移 幅度(amp1itude)。下面对量子图灵机进行介绍:定义9 一个基于量子逻辑的图灵机(简称为量子图灵机,记为1-V
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号