没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记270(2)(2011)251-261www.elsevier.com/locate/entcs一致性结果量子λ演算与测量1Ugo Dal Lago2Dipartimento di Scienze dellAndrea Masini3 Margherita Zorzi4Dipartimento diInformaticaUniversit`adiVerona摘要证明了带测量的量子λ演算Q_∞的一个强相合结果。更准确地说,连续性被证明对有限和无限计算都成立。在一致性证明中使用的技术是语法的,但创新。 这使得Qλ不同于类似的量子λ演算,要么是无措施的,要么是有减少战略的。保留字:量子计算,lambda演算,连续性1引言众所周知,量子系统的无测量演化是确定性的。因此,可以预期,一个好的无测量的量子lambda演算具有连贯性。这是Q的情况,由作者[4]和最近由Arrighi和Dowek [1]引入的lambda演算。如果我们引入一个测量算子,情况就变得更加复杂。事实上,测量打破了量子系统的确定性演化1作者部分得到PRIN项目应用数学研究所。2电子邮件:dallago@cs.unibo.it3电子邮件:andrea. univr.it4电子邮件:margherita. univr.it1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2011.01.035252联合Dal Lago等人/Electronic Notes in Theoretical Computer Science 270(2)(2011)语法中的显式测量运算符允许在计算的中间步骤进行观察:例如,如果我们想要编写Shor因子分解等算法,则需要此功能在量子计算中,测量的预期含义是观察(可能叠加的)量子比特,给出经典比特作为输出;两种可能的结果(即,所获得的经典比特的两个可能值)可以用两个概率之和为1来观察由于测量在计算中迫使概率进化,因此我们需要概率工具来研究语言的主要特征也就不足为奇了。在本文中,我们研究了Q的扩展,通过赋予术语语言一个合适的测量算子和连贯地扩展约化关系,由于我们刚才解释的原因,它变得概率性。我们调查由此产生的演算,称为Q,重点是,特别是在concilience。在Q和Q中,状态通过配置形式化,即, 形式为[Q,QV,M]的三元组,其中M是λ项,Q是量子态,QV是集合量子变量的名字因此,控制是经典的(M只是一个术语),数据是量子的(Q是有限维希尔伯特空间的元素我们感兴趣的是以下问题:在存在测量时,诸如连续性之类的性质会发生什么变化?此外,在由测量引起的概率环境中,是否有可能保持连续性?显然,上面的问题不能得到肯定的答案:正如我们将在第3节中看到的,有可能展示一个构形C,使得有两个不同的约简从C开始,并以两个本质上不同的构形结束,这两个构形分别为标准形式[1,n,0]和[1,n,1]。换句话说,连贯性以其通常的形式失败了但现在的问题是:在这种情况下,通常的计算和计算概念是否足够?在Q中,有两个不同的分歧来源:• 一方面,涉及测量操作员的redex可以以两种不同的方式减少,即,发散可以来自单个redex。• 另一方面,一个项可以包含多个redex,并且Q不具有约简策略。因此,由于一个术语中存在不同的赎回,一些配置可以以不同的方式减少我们不能指望在分歧的第一个来源上是一致的,但无论如何,我们可以问自己,是否所有的缩减策略在某种程度上都是等价的。更确切地说,我们说Q是连续的,如果对于每个配置C和每个正规型D的配置,存在一个固定实数p,使得 在约简C时观察到D的概率总是p,与约简策略无关。这种一致性的概念可以很容易地通过分析混合状态的重写而不是配置的重写来捕获混合状态是支持度有限的配置上的概率分布。对配置的重写自然延伸到对混合状态的重写。混合态上的重写不是一个概率关系,而推论是来自重写理论的通常推论[13]。联合Dal Lago等人/Electronic Notes in Theoretical Computer Science 270(2)(2011)253本文证明了在这个意义下Q_n从技术上讲,连贯性是以创新的方式证明的。关键是我们需要一个新的计算定义。通常把计算看作是一系列配置的概念在这里是不够的。概率计算的概念取代了它,作为比线性配置序列更一般但比约简树更不一般的东西:概率计算是(可能)无限树,其中二元选择(一个节点最多可以有两个孩子)对应于测量的两个这种新的计算概念是必要的,因为直接证明混合状态的连续性是不平凡的。作为副产品,我们证明了其他结果的风格的concilience。任何带有测度的量子lambda演算的另一个重要性质是无限计算的重要性。在标准lambda演算的情况下,无穷计算的研究与无穷lambda项的研究密切相关。这不是Q的情况(一般来说,量子演算的测量)。这一现象迫使我们把对连续性的研究扩展到无限概率计算的情况。拟议的分析不是标准的,是基于新技术。据我们所知,唯一一篇关于量子环境中的连续性的论文是[6]。作者声称已经研究了Van Ton der量子λ演算λ q [ 14 ]的扩展的连续性,主要结果在于表明,一致性和操作语义的一致性在扩展演算中成立,这里称为λM,只要在λq中也成立。 这可能是一个有前途的结果,弱,但类似于本文提出的。然而,在我们看来,[6]存在一些问题,这妨碍了我们正确地评价它:• 主要结果的意义尚不完全清楚。关键的一点是λM不是λq的扩展,主要的区别是缺乏策略(例如,参见[6]中定理3.13的证明,其中作者假设约简可以在λ-抽象的范围内发生,或者当β-redex的参数不是值时),而λq上的约简关系是完全确定的,因为λq是按值调用演算[14]。此外,λM的句法在某些方面似乎比λq的句法更具限制性例如,在λM不允许•在[6]中,关于λM 规则在图2中,允许证明不是术语的语法对象的良构性。以叠加规则为例:它的结论是一个语法对象,不能从图1中的规则中导出,因为例如!|0 ⟩ is not a qubitconstant.此外,像t1<$t2(其中t1和t2不是量子位常数)这样的语法对象似乎不能是项。作者自己在注1中观察到。现在,看看算法2中alice的定义:什么是((Hr)w)?它不可能是一个术语。实际上,我们认为[6]中描述的λM不能表示隐形传态方案。254联合Dal Lago等人/Electronic Notes in Theoretical Computer Science 270(2)(2011)7√本文其余部分的结构如下:•第二节介绍了量子λ-演算Q•在第三节中,我们以一种非正式的方式介绍了并发问题;•在第4节中,我们给出了概率计算的定义;•第五节给出了概率计算的一个强相合结果• 第六节介绍了混合态和混合计算,并给出了混合计算的一个同余定理一个扩展的版本与所有的证据是可用的[3]。2Q简介在[4]中,我们基于量子数据和经典控制范式引入了一个无测量、无类型的本文通过用一个测度算子推广Q的项类,得到了Q_n。由于篇幅有限,我们无法详尽无遗,必要时,我们将参考我们的论文[4]和文献。Q是基于配置的概念,即三元组[Q,QV,M],其中 Q是一个量子寄存器5,QV是一个有限的名称集合,称为量子变量,M是一个基于Wadler [15]和Simpson [12]定义的线性代数演算的无类型项。Conf表示所有这些配置的集合。量子寄存器是n个量子比特的系统,从数学上讲,是有限维希尔伯特空间的归一化向量。特别地,配置为[Q,QV,M]的量子寄存器Q是希尔伯特空间l2({0,1}QV)的归一化向量,这里用H(QV)表示。[6]粗略地说,不熟悉希尔伯特空间的读者可能会认为量子变量是指向量子寄存器中量子比特的指针。在量子寄存器上有三种操作:(i)新操作,负责创建量子比特;(ii)酉算子:每个酉算子Uq1,...,qn nn对应于作用于具有名称q1,.,qn(数学上,希尔伯特空间H({q1,...,qn}),参见[4]);(iii)一个量子比特测量操作Mr,0,Mr,1,其响应于量子态的概率约简加上由r引用的量子比特的破坏:给定量子寄存器Q ∈H(QV)和量子变量名称r ∈ QV,我们允许具有名称r的量子比特的(破坏性)测量。配置的另一个主要组成部分是术语。 项的集合是从(i)经典变量的可数集合构建的,其范围为x,x0,. 。;在图5中,6见[4]关于H(QV)的充分讨论, [9]对l2(S)空间作了一般处理。7更准确地说,对于每个量子变量r,我们假设存在两个线性测量算子Mr,0,Mr,1:H(QV)→ H(QV−{r}),满足完备性条件Mr,0 <$Mr,0+Mr,1<$Mr,1=id H(QV),并且,给定量子寄存器Q ∈ H(QV),Q中名为r的量子比特的测量给出结果c(c∈ {0,1}),概率为pc=<$Q| Mr,c†Mr,c| Q表示并产生新的量子寄存器Mr,c Q;参见[8,7]关于一般纯测量的详细讨论和[3]关于pc给出了Mr,0和Mr,1的形式定义和详细结果。联合Dal Lago等人/Electronic Notes in Theoretical Computer Science 270(2)(2011)255►► ►►ααl.βc.βq.β如果1如果1UQ新L.cmR.cm(ii)量子变量的可数集,其范围为r,r0,.。(iii)对应于酉算子的有限个或至多可数个名称集;(iv)布尔常数 0, 1和(v)算子new和meas。一个环境Γ是一个(可能是空的)形式为Λ,的有限集合!Δ,其中Λ是经典变量和量子变量的(可能是空的)集合,并且!Δ表示一组(可能为空)模式!x1,., !xn. 我们假设在一个环境中,每个经典变量x都出现在最多一次(或者作为!x或作为x)。一个判断是一个表达式Γ<$M,其中Γ是一个环境,M是一个项。我们说一个判断是良构的,如果它是通过图1中的良构规则可导出的。!ΔΔCconst!Δ,rQvar!Δ,xcvar!Δ,!xxder!ΔM舞会!啊!MΛ1,!ΔMΛ 2,!ΔNappΛ 1,Λ 2,!Δ TMNΛ 1,!ΔM1···Λ k,!Δλ Mk几十Λ 1, . ,Λ k,!ΔM1, . ,MkΓM(男)新r,x1,...,xn MΓλx1, . ,xn.M哀1Γ,x<$MΓλx.M哀2你!xM你好!x.M哀3ΓMmeas测量值(M)N!ΔM1!Δλ M2如果啊!Δ ► 如果N则M1否则M2Fig. 1. Well–Forming设L ={Uq,new,l.β,q.β,c.β,l. 厘米河cm,如果为1,如果为0,则测量r}。 对于每个α ∈ L和每个p ∈ R[0,1],我们通过图2中的重写规则压缩集加上标准闭包规则定义关系→ p <$Conf × Conf。记法C→αD代表C→1D。为了与所谓的不克隆和[Q,QV,(λx.M)N]→1[Q,QV,M{N/x}][Q,QV,(λ!x.M)!N] →1[Q,QV,M{N/x}][Q,Q V,(λx1, . ,xn.M)r1, . ,rn=1[Q,Q,V, M{r1/x1, . ,rn/xn}][Q,QV,if1thenM1elseM2]→1[Q,QV,if0thenM1elseM2]→1[Q,QV,M1][Q,QV,M2][Q,Q V, Uri1,...,n=1[U((ri1,...,rin⟩ ⟩Q,Q V,∗ri1,..., [rin][Q,QV,meas(r)] →measr[Mr,c(Q),QV−{r},!c](c∈ {0, 1}且pc∈R)pc[0,1][Q,QV,new(c)] →1[Q]|r<$→c,QV {r},r](r是新鲜的)[Q,QV,L((λπ.M)N)]→1[Q,QV,((λπ.M)N)L]→1[Q,QV,(λπ.LM)N][Q,QV,(λπ.ML)N]图二. 宫缩。非擦除性,我们采用表面还原[12,4]:还原范围内不允许有任何!操作符.此外,256联合Dal Lago等人/Electronic Notes in Theoretical Computer Science 270(2)(2011)像往常一样,我们也禁止在如果M则N否则P的项中减少N和P。注意,收缩包括两个交换规则l。cm和r. cm(见图2):它们来自Q,在那里它们是实现量子标准化的必要条件[4]。我们区分了三个特定的子集联合Dal Lago等人/Electronic Notes in Theoretical Computer Science 270(2)(2011)2572我2我≡,即K={1。厘米河cm},N =L−(K{measr})和nM =L −{measr}。在下文中,我们写M →αN意味着存在Q,QV,R和RV使得[Q,QV,M] →α[R,RV,N]。类似地,对于符号M→SN,其中S是L的子集。3Conquience问题:非正式介绍正如在引言中强调的那样,一致性问题是任何带有测量的量子λ让我们考虑以下配置:C=[1,λ,(λ!X. (if x then 0 else 1))(meas(H(new(0)]。如果我们专注于约简序列,很容易检查到有两个不同的约简序列以C开始,第一个以规范形式[1,n,0]结束(概率为1/ 2),第二个以规范形式[1,n,1]结束(概率为1/ 2)。但如果我们用混合状态来推理,情况就变了:混合状态{1:C}(即,混合状态将概率1分配给C,将概率0分配给任何其他配置)确定性地重写为{1/ 2:[1,n,0], 1/ 2:[1,n,1]}(其中[1,n,0]和[1,n,1]都具有概率1/ 2)。因此,一致性似乎成立。其他量子计算与无测量的情况类似,上述的一致性概念不是量子lambda演算的预期结果实际上,它在Selinger和Valiron [11]提出的量子λ演算λsv中不成立在λsv中,可以展示一个配置C,当按值调用减少时,它给出分布{1:[1,n,0]}作为结果,如果按名称调用减少,它给出分布{1/ 2:[1,n,0], 1/ 2:[1,n,1]}作为这是一个真正的一致性失败,即使人们使用概率分布代替配置,它也存在。同样的现象不会发生在Qλ中(正如我们将在第5节中展示的那样):这个基本的区别可以追溯到另一个:具有曲面约化的线性lambda演算(Qλ是基于它的)享有所谓的钻石性质[12],而在通常情况下,纯lambda演算(λsv是基于它的)的连续性只在较弱的意义上成立有限的还是无限的重写?在Q中,无限计算可以趋向于一种与计算本身的配置本质上不同的配置例如,可以构建配置C= [1,N,M]8,使得:•在有限个归约步骤之后,C重写为以下形式{n1
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 电力电子系统建模与控制入门
- SQL数据库基础入门:发展历程与关键概念
- DC/DC变换器动态建模与控制方法解析
- 市***专有云IaaS服务:云主机与数据库解决方案
- 紫鸟数据魔方:跨境电商选品神器,助力爆款打造
- 电力电子技术:DC-DC变换器动态模型与控制
- 视觉与实用并重:跨境电商产品开发的六重价值策略
- VB.NET三层架构下的数据库应用程序开发
- 跨境电商产品开发:关键词策略与用户痛点挖掘
- VC-MFC数据库编程技巧与实现
- 亚马逊新品开发策略:选品与市场研究
- 数据库基础知识:从数据到Visual FoxPro应用
- 计算机专业实习经验与项目总结
- Sparkle家族轻量级加密与哈希:提升IoT设备数据安全性
- SQL数据库期末考试精选题与答案解析
- H3C规模数据融合:技术探讨与应用案例解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功