没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记135(2006)119-128www.elsevier.com/locate/entcs经典控制量子计算西蒙·佩德里克斯1 菲利普·乔兰德2莱布尼茨实验室IMAG-INPG法国格勒诺布尔摘要假设量子计算是在经典世界的控制下进行的是合理的。为了对这种标准情况进行建模,我们引入了一个经典控制的量子图灵机(CQTM),它是一个具有量子磁带的图灵机,用于作用于量子数据,以及用于形式化经典控制的经典转换函数。在CQTM中,允许幺正变换和量子测量。 我们证明了任何经典图灵机在不损失效率的情况下,用CQTM进行模拟。 此外,我们证明了任何k带CQTM用二次效率损失的2带CQTM模拟。经典计算和量子计算之间的差距已经在基于测量的量子计算的框架中指出(见[14]),在经典控制的量子计算的一般情况下得到证实。为了理解编程经典图灵机和编程CQTM之间的相似性,CQTM的一些例子将在本文的完整版本中给出。引理和定理的证明在这个扩展的摘要中被省略了。保留字:量子图灵机(Quantum Turing Machine)1介绍量子计算在量子世界中运行为了使他们的结果以任何方式有用,例如通过测量,他们在经典世界的控制下运作量子隐形传态[1]说明了经典控制的重要性:在最后应用的校正泡利操作是由先前测量的结果经典控制的经典控制重要性的另一个例子是基于测量的量子控制。1Email:simon. perdrix@imag. fr2Email:phili pp e. 我是一个很好的朋友。fr1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.09.026120S. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)119计算[10,12,15,14,16,5],其中需要经典的条件结构来控制计算。 这种经典控制可以描述如下:“如果测量数i的经典结果是λ,则测量数i + 1根据可观测值O a在量子位q a上,否则测量数i +1根据可观测值O b在量子位q b上“。基于测量的量子计算的一个特别优雅的形式化是测量演算[5]。在量子计算的描述中集成经典控制的必要性现在是量子编程高级语言设计中的一个很好理解的要求[7,17]。也有一些集成经典控制的较低级别计算模型的提议,如量子随机存取机(QRAM[9,2])。然而,目前还没有一个明确的、抽象的、与经典控制相结合的量子计算模型本文旨在定义这样一个经典控制量子计算的抽象模型。量子计算的主要抽象模型之一是由Deutsch [4]引入的量子图灵机(QTM),它是经典图灵机(TM)的模拟。量子图灵机是量子计算机的抽象模型,它通过允许量子跃迁函数扩展了图灵机的经典模型。在QTM中,配置的叠加和干扰是允许的,但是经典的计算控制没有形式化,机器的输入和输出仍然是经典的。这第二点意味着QTM的模型探索了量子力学解决经典问题的计算能力,而没有考虑量子问题,即量子输入/输出。虽然处理量子态的模型,如量子电路[8,19]和QRAM,主要用于描述特定的算法,但复杂性类的发展,如处理量子态的QMA[18],指出了量子计算理论模型作用于量子数据的必要性。介绍了最近由S.Iriyama,M.奥希亚,我。Volovich [6]是QTM的推广,处理混合态并允许不可逆的过渡函数,允许表示量子测量而没有经典结果。由于缺乏经典的结果,经典的控制在LQTM中没有形式化,并且,除其他外,像隐形传态这样的方案无法表达。此外,像QTM一样,LQTM只处理经典的输入/输出。本文介绍一种经典控制的量子图灵机(CQTM)S. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)1191212| ⟩τ|⟩其是具有用于作用于量子数据的量子带和用于形式化经典控制的经典转换函数在CQTM中,允许幺正变换和量子测量。注意,限制于投影测量的CQTM模型等价于[14]中引入的基于测量的量子图灵机(MQTM)模型。定理2.1表明,任何TM都可以用CQTM来模拟,而不损失效率.第三节介绍了多带CQTM。定理3.1表明任何k带CQTM都可以用具有二次效率损失的2带CQTM来模拟.此外,在基于测量的量子计算框架中已经指出的经典计算和量子计算之间的差距(见[14])在经典控制的量子计算的一般情况下得到了证实。一个观点是使CQTM不仅是一个定义良好的理论模型,而且是通往量子计算的实际模型(如QRAM)的桥梁,这依赖于量子计算的自然模型是经典控制的这一事实。2经典控制的量子图灵机2.1量子态与容许变换CQTM的量子存储器由量子单元组成量子胞是一个d能级量子系统[11],它的态是d维希尔伯特空间中的归一化矢量。这个希尔伯特空间的一个基是由一个有限的alpha b到sy molsuQsuchtat来描述的|QQ|=d。 那是那是|φ∈H<$Q量子细胞是Σ|φ⟩=Στ∈Qατ|τ,与τ∈Q |ατ| =1。一般量子测量根据相应的量子力学的假设:量子测量由ωn{Mτ1, .. . ,Mτk}的测量操作器的状态空间上被测量的系统。 指数τ是指实验中可能出现的测量结果。如果量子系统的状态在测量之前是π,那么经典结果τ出现的概率由下式p(τ)=0|Mτ†Mτ|但是,测量后的系统状态为M- 是的p(τ)122S. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)119λ。测量算子满足完备性方程,ΣMτ†Mτ =I.τ一般的量子测量也称为容许变换。注意,仅由一个算子Mτ构成的容许变换是酉变换,因为p(τ)= 1,变换后的状态是Mτ|则完备性方程简化为Mτ<$Mτ =I。反之,任何酉变换A都是容许变换。对于给定的HilbertpaeH<$Q,我们证明了一些具有经典结果的容许变换属于有限集<$C =<$Q <$$>{λ},其中<$Q={τ:τ∈<$Q}且λ∈/<$Q:• Std={Mτ}τ∈<$Q是一个在标准基础上成立的预射方法:Q,Mτ= |τ ⟩ ⟨τ|、• Tτ={Mτ,Mτ}是符号τ的检验:Mτ= |τ ⟩ ⟨τ|且Mτ= I −|τ ⟩ ⟨τ|、• P∈[τa,τb]={Mλ}是一个带有输出λ的酉变换,且Mλ=( τ∈<$Q−{τa,τb}|τ⟩ ⟨τ|)+的|τaτb|+的|τbτa|是符号的排列τa和τb。•UV={Mλ}是酉变换Mλ=V,具有经典结果• OO={Pk}k,是根据可观测O=kPk的投影测量。2.2定义CQTM为了完整起见,定义2.1是确定性TM的定义[13]。经典控制的量子图灵机(定义2.2)由量子单元的量子带,一组经典内部状态和一个用于对带上的单元应用可接受变换的头部的作用至关重要,因为它实现了机器的量子部分和经典部分之间的相互作用定义2.1确定性(经典)图灵机定义为三元组M=(K,ε,δ),其中K是具有可识别初始状态s的有限状态集,ε是具有可识别“空白”符号#的有限字母表δ:K×→(K{“yes“,“no“,h })× × {←,→,−}。S. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)119123一--| ⟩我们假设h(暂停状态)、定义2.2经典控制的量子图灵机是一个五元组M=(K,C,Q,A,δ)。 这里K是经典状态的有限集合,一个识别的初始状态s,是表示量子单元的基态的有限字母表,是经典结果的有限字母表,是一组单量子单元可允许的变换,δ是经典过渡函数:δ:K × C→(K {“yes“,“no“,h })× {←,→,−} × A。我们假设h(停止状态)、此外,我们假设,Q总是包含一个函数δ是量子计算的经典控制的形式化,也可以被视为机器的它规定,对于当前状态q∈K和最后获得的经典结果τ∈C的每个组合,一个三元组δ(q,τ)=(p,D,A),其中p是下一个经典状态,D∈ {<$,→,−}是头部移动的方向,A∈ A是接下来要执行的容许变换空白试验容许变换M#,M#建立了量子空白符号(#)与经典空白(#)和非空白(#)符号之间的对应关系:|被测量子单元的φ φ为|#你,出去-如果是#,则|φ n与|#(φ |#= 0),则结果为#。该计划如何开始?计算的量子输入|φ =τ∈(<$Q−{#})n ατ|通常未知的τ被放置在n个相邻单元格上而该带的所有其他量子单元的状态是#。头部指向紧邻输入左侧的空白单元格最初,机器的经典状态是s,而#被认为是最后一个经典结果,因此第一个转变总是δ(s,#)。程序如何停止?跃迁函数δ是K×λC上的全函数(不相关的跃迁将从其描述中省略机器无法继续的原因只有一个:三个停止状态h、如果机器M在输入时停止,|(1)在A中,A的值为(|φ(单位:φ),|φ在φ中定义。如果达到状态“是“或“否“,则M(|φ(单位:φ)=“是“或“否“。否则,如果停止124S. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)119|⟩|⟩|⟩QQ联系我们2如果达到状态h,则输出是在停止时M的带的状态φout由于计算已经进行了有限多步,只有有限数量的细胞不处于状态#。输出状态φout是由来自最左边单元的量子单元组成的有限寄存器的状态,该状态不|#在一个状态下,返回到最右边的单元格,|#⟩.自然地,M可能永远不会停止输入|φ(单位:φ)如果是这样的话,我们就写M(|φ(单位:φ)= 3。CQTMM的配置直观上是对计算当前状态的完整描述。形式上,配置是三重态(q,τ,|其中q∈K <${h,“yes“,“no“}是M的内态,τ ∈ C这是最后一个被淘汰的,|ψ⟩∈HΣJ 表示当前的状态和头部的位置。这里,n_JQ = n_Qn_Q,其中n_Q={τ:τ∈n_Q}是n_Q中的s_m_o_l的p个方向的集合。 Fromastate|φ∈H<$Q,tappe,state |ψ⟩∈HΣJ 是通过重新绘制CNOQ的数据库获得的,头部所指量子单元的对应符号为SQREQ例如,如果K=q1,q2,C= #,#,t,u,v和Q= #,a,b,则配置1(1)1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,10,1 |a#bb |b #ab(b))这意味着机器的内部状态是q1,最后一个结果是u,t ape的状态是q1(|a#bb|b#ab右边的细胞3CQTM和TM下面的定理表明,任何TM被CQTM模拟而不损失效率。定理3.1给定在时间f(n)上操作的任何TM M C,其中n是输入大小,存在在时间O(f(n))上操作的CQTMMQ并且使得对于任何输入x,MC(x)=MQ(|xx x)由于任何TM都可以用一个CQTM来模拟而不损失效率,CQTM的模型是经典普适的(关于经典和量子普适性的定义见[14]),但是,正如引理4.4所示,带有一个带的CQTM不是量子普适的,因为只允许单胞的可容许变换。为了允许在多个单元上进行转换,我们引入了多个磁带CQTM。直观地说,对于k个头,可以执行kS. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)1191254带多个磁带的我们介绍了一个推广的CQTM,经典的控制图灵机与多个磁带。我们表明,任何k-磁带CQTM模拟的2-磁带CQTM与无关紧要的效率损失。此外,通过证明1-和2-磁带CQTM是不等价的,我们指出了经典和量子计算之间的差距定义4.1k带经典控制的量子图灵机,其中k >0,是五元组M=(K,C,C,Q,A,δ),其中K是具有识别的初始状态s的经典状态的有限集合,C,Q是表示每个量子单元的基态的有限字母表。A是一个k-cell可容许变换集,λC是k-cell可容许变换的经典结果的有限字母表,δ是一个经典转移函数δ:K×C→(K{“yes“,“no“,h })×({←,→,−})k × A。我们假设A的每个测量的所有可能的经典结果都是在CXC中,并且A总是包含k个可接受的“空白测试”变换,每个变换直觉,δ(q,τ)=(q,Τ,(D1,. Dk),A)意味着,如果M处于状态q,最后一个经典结果是τ,那么下一个状态将是qJ,机器的k个头将根据D1移动,.,Dk和下一个k-量子单元容许变换是A。这种可接受的变换将在机器的头部移动后指向的k个k-胞腔容许变换A可以直接定义,例如通过使用k-胞腔酉变换V(A=UV)。A也可以定义为分别在j和l个单元上的两个容许变换A1,A2的合成,使得j+l=k,则A=[A1,A2]意味着前j个头应用A1,同时,后l个头应用A2。经典结果是A1和A2的结果的级联,其中λ是级联的单位元素(即τ。λ=τ)。k带CQTM以输入状态开始|如果达到停止状态h,则机器停止,输出为指定带T1的状态。定理4.2给定在时间f(n)中操作的任何k带CQTM M,其中n是输入大小,存在在时间O(f(n)2)中操作的2带CQTM M j,并且使得对于任何输入|2016年01月01日@上午10时30分01秒|10)=MJ(|ψ>)。定理4.1是CQTM的能力和稳定性的强有力的证据:向2-磁带CQTM添加有界数量的磁带并不增加126S. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)119| ⟩| ⟩它们的计算能力,并且仅多项式地影响它们的效率。这种稳定性使得2-tapeCQTM成为量子普适性的良好候选者,即模拟任何量子计算的能力。这个能力可以用以下两个引理证明引理4.3测量演算[5]的任何模式都可以通过2-tape CQTM在模式大小的时间多项式中模拟。引理4.4任何量子电路都可以用2带CQTM在多项式时间内模拟。以下引理表明,某些双磁带CQTM无法由单磁带CQTM模拟:引理4.5存在2-带CQTMM,使得没有1-带CQTM模拟M。总而言之,两个磁带对于量子计算是足够的(引理4.3),而一个磁带对于经典计算是足够的(定理3.1),但对于量子计算是不够的(引理4.4)。因此,在经典计算和量子计算之间出现了一个鸿沟请注意,这个结果并不与经典计算和量子计算之间在可判定性方面的等价性相矛盾:在考虑量子数据时出现差距。人们可能想知道为什么1-tape CQTM不是量子通用的,而Briegel 和Raussendorf已经用他们的单向量子计算机证明了单量子比特测量是通用的[16]。Briegel和Raussendorf的证明是在一个强有力的假设下给出的,即存在一个辅助量子比特的网格,这些量子比特最初是由一些未指定的外部设备在全局纠缠态(簇态)中准备的,而纠缠的产生是引理4.4证明中的一个关键点。此外,单向量子计算的另一个强假设是,输入状态必须是经典已知的(即,需要对输入状态的数学描述),而对未知状态的操纵(即,在未知状态下操纵量子比特)在量子计算中是常见的(例如远程通信[1])。由于这些 假 设 都 没 有 被 1-tape CQTM 验 证 , 因 此 以 前 的 结 果 与 Briegel 和Raussendorf的结果并不5结论介绍了一种新的量子计算抽象模型-经典控制量子图灵机模型(CQTM)。该模型允许在量子计算期间量子世界与经典世界之间的固有相互作用的严格形式化。任何班级-S. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)119127用一个CQTM来模拟一个典型的图灵机而不损失效率,而且用一个2-tapeCQTM来模拟任何k-tape CQTM,而执行时间仅是多项式的。此外,在基于测量的量子计算框架中已经指出的经典计算和量子计算之间的差距(见[14])在经典控制的量子计算的一般情况下得到了证实。经典控制的量子图灵机是一个很好的候选者,可以在理论模型(如QTM,CQTM,MQTM [14])和量子计算的实际模型(如量子随机存取机)之间建立桥梁引用[1] C. Bennett等,通过双经典和EPR通道传送未知量子态,Phys Rev Lett,1895-1899,1993。[2] S.贝泰利湖Sera fini和T. 卡拉科 为了量子编程,http://arXiv.org/cs.PL/0103009网站,2001年[3] E. Bernstein和U. 量子复杂性理论,北京:科学出版社. 26,1411-1473,1997。[4] D. 德语量子理论,丘奇-图灵原理和通用量子计算机,伦敦皇家学会学报A 400,97-117,1985。[5] 诉Danos,E.Kashe fi,P.PanangeloThe Measurement Calculus ,电子版http://arXiv.org/quant-ph/0412135网站。[6] S. Iriyama , M. 奥 希 亚 岛 沃 洛 维 奇 广 义 量 子 图 灵 机 及 其 在 SAT 混 沌 算 法 中 的 应 用 ,http://arXiv.org/quant-ph/0405191,2004。[7] 博士Jorrand和M.拉里尔TowardaQuantumProcess Algebra , Proceedings of the first conference on computing frontiers , 111-119 ,2004,e-print http://arXiv.org/quant-ph/0312067.[8] A. Y. Kitaev,A. H. Shen和M. N.维亚利经典与量子计算,美国数学学会,2002年。[9] E. H.尼尔量子伪码惯例,未发表,LANL报告LAUR-96-2724[10] D. W. 小良量子计算的测量,arXiv,quant-ph/0310189,2003年。[11] A. Muthukrishnan和C. R.斯特劳德量子计算的多值逻辑门,arXiv,quant-ph/0002033,2000。[12] M. A. 尼尔森仅使用投影测量的通用量子计算,量子存储器和0态的准备,http://arXiv.org/quant-ph/0108020,2001年。[13] C. M.帕帕迪米特里乌计算复杂性,Addisson-Wesley Publishing Compagny,1994。[14] S. Perdrix和Ph. Jorrand. 基于测量的量子图灵机及其普适性,arXiv,quant-ph/0404146,2004。[15] S.珀德里克斯基于测量的量子计算中的状态转移而不是隐形传态,arXiv,quant-ph/0402204,2004。128S. Perdrix,P.Jorrand/Electronic Notes in Theoretical Computer Science 135(2006)119[16] R. Raussendorf,D. E. Browne和H. J·布里格尔基于测量的簇态量子计算,http://arXiv.org/quant-ph/0301052,2003年。[17] P.塞林格。量子编程语言。出现在计算机科学中的数学结构,2003年。[18] J. Watrous,有限群性质的简洁量子证明,Proc.41st计算机科学基础年度研讨会,pp. 537-546,2000。[19] A. C. Yao,量子电路复杂性,Proc.34th IEEE Symposium on Foundation of ComputerScience,pp. 352-361,1993年。
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)