《量子自动机》由会员分享，可在线阅读，更多相关《量子自动机（14页珍藏版）》请在金锄头文库上搜索。
1、量子自动机及其应用1背景当今,计算机技术日新月异,芯片的集成度不断提高，计算速度成 指数式提高，据此,摩尔给出了一条不精确的经验性定律：计算机的计 算速度每18个月就翻一翻按照此定律，鞋片上的集成电路最终会小到 一个极限，此时微粒的波粒二象性将变得十分显著，电路不再服从经典 力学规律,而服从量子力学规律.为此，人们提出了量子计算与量子计 算机的思想。20世纪80年代初，Benioff和Feynman首先提出了量 子计算机的构想。其后，Deutsch将他俩的思想形式化并引入了量子 Turing机的概念，在1994年以后，量子计算的研究日益活跃。并提出 了量子并行操作技术。在1936年,Birkh
2、off和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) =
3、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， b
4、Wc = 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各
5、自独立地证明了可用两比特 的量子逻辑门来构造D门。后来,Deutsch和S.Leoyd又各自证明，几乎 所有的两比特门都是通用的。最近Barenco等人给出一个最新结果, 他们用一个对两比特操作的受控非门和对单个比特进行任意操作的 量子门构成了一个通用量子门集。因此，为建造量子计算机，实验物理 学家只需要寻找实现对一个量子比特进行任意操作和对两个量子比 特的受控非(又称异或)操作。前一类操作在量子光学中已经解决了 ： 应用Ram-sy场可以将二能级原子制备到任意态上，或者利用其它量子 态工程的方法将两能态体系制备到所需要的量子态上。于是如何实现 量子受控非门便成为量子计算机成功与否的关键。3量
6、子自动机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
7、, 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=决定工
8、上的正交模格值一元谓词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自动机、 基于量子逻辑
9、的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)
10、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-值子集。 与传统有限
11、自动机的区别：定义：有限自动机M=(Q,工,6 , q0, F,),其中，Q是状态的非空有穷集合。工输入字母表6是状态转移函数，6 : QXZ Q,q0初始状态F终止状态集合。性质:量子力学中的Hi1bert 空间的所有闭子空间以及投影本身可能不满足分配律,而是满足正交 模律。量子自动机中状态转移的可能性的大小是Hi1bert空间的一个 闭子空间。识别语言：经典有限自动机只能识别正则语言。经典的有 穷自动机一般由状态集、输入字母表和一个转移关系构成，当输入一 个字符之后,由转移关系决定状态的转移。量子有穷自动机的状态集 一般由有穷个状态的任意次叠加构成，而每次状态的转移有一个转移 幅度(amp1itude)。下面对量子图灵机进行介绍：定义9 一个基于量子逻辑的图灵机(简称为量子图灵机，记为1-V
