量子λ演算的测量算子结合概率重写系统的研究

理论计算机科学电子笔记270（1）（2011）59-74www.elsevier.com/locate/entcs显式量子比特对量子Lambda计算的亚历杭德罗·达兹-卡罗a，1，巴勃罗·阿里吉b，2，ManuelGadellac，3和乔纳森·格拉塔格b，4aDepartamentodelaCienciasdeComputación，罗萨里奥国立大学，阿根廷bLaboratoirecDepartamentodeF'ïsicaTe'orica，At'omicayO'ptica，Valladolid大学，西班牙摘要式本文演示了如何在量子λ-演算中加入一个测量算子。语义学的一致性的证明是通过一个一致性的证明来给出的，这个一致性的证明是以一种允许这种技术用于其他语言的一般方式提出的。这里描述的方法可以应用于一般的概率重写系统，并且可以将度量添加到更复杂的语言，例如QML[5]或线性。[2][3]，这是进一步研究的主题关键词：量子λ演算，测量，反流，概率重写系统（QRS）1介绍性在开发量子编程语言的过程中，函数式语言的量子扩展提供了一条有前途的途径，阻碍了量子lambda计算和量子函数式语言工作的爆炸性增长[3][5][9][10]。当前的语言命题可以分为两类：一种是命题，另一种是命题。在第一类中，量子比特被操纵为指向量子存储器的指针[7][9]，因此语法没有提供对量子比特的明确描述然而，它确实与一个线性类型的系统结合在一起，给出了一种方便而一致的方式来处理量子比特上的操作。一个问题是，量子运算的语义不能在语法中内在地给出，因为这将需要量子存储器的当前状态才能在语法中给出。1电子邮件：Alejandro. imag.fr2电子邮件地址：pablo. imag.fr3电子邮件地址：gadella@fta.uva.es4电子邮件：jonathan. ens-lyon.fr1571-0661 © 2011 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2011.01.00660A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）59知道了。在第二类语言[3][5][10]中，量子位的描述是编程语言的一部分，不需要类型系统。这里的一个优点是整个语义学可以简单地表达为语言术语之间的重写这就变成了一个关于测量的弱点，因为测量的固有概率性质使它很难表达为重写系统的一部分。[10]事实上，没有一种语言类别允许此功能。[3][10]Altenkirch和Grattage的QML [ 5 ]的案例QML包含了用量子电路术语给出的操作语义来度量然而，相应的代数理论[1]只适用于语言的一个纯量子子集，省略了类控制和度量[2]。Van Tonder的这种计算提供了一条历史线索，以保持必要的信息来反转还原，以证明整个计算过程是统一的。 它与线性逻辑密切相关，语法是Wadler [11]引入的1的一个片段，用常数扩展以表示诸如量子比特和门之类的量子实体。线性概念被用来区分有限项和任意的重叠项，而不是有限项和任意重叠项。这些合成标记构成了与Arrighi和Dowek的线性[ 2 ][ 3 ]的主要区别，后者如前所述，这两项建议中不包括衡量标准。这里介绍的工作展示了如何以优雅的方式将测量添加到具有显式量子比特的量子λ计算中。 这是完成了完整的细节λq-calculus，证明了影响，并保持了一致性的操作语义，是由这个扩展保存。此外，虽然由于固定的缩减策略，该计算不需要证明对原始设置的影响，但在存在测量的情况下，该证明是必要的。此外，它是非平凡的，并且具有在具有由测量产生的分支的概率设置中显示影响的新颖性。这里所示的方法是一般性的，并且将这些技术应用于QML和线性正在进行中。与经典力学中的测量相反，经典力学中的测量给出了一个给定的可观测值，并带有一个相关的误差，量子力学中的测量具有内在的概率特征。也就是说，一个量子测量可以先验地给出一定数量的结果，每一个结果都具有一定的概率。此外，测量之后的系统状态被测量的行为以不可逆的方式改变，这是不可逆的。这种非直觉行为在量子信息处理中具有非常重要的意义。测量是许多量子信息处理任务中的一个关键属性，如量子密码学、超密集编码和量子搜索算法中的一个关键属性。没有衡量标准可能会导致错误的解释。作为一个例子，考虑图1中定义的具有延迟测量的量子隐形传态算法[10]。这里不清楚爱丽丝和鲍勃是否可以物理分离，因为所有使用的通道都是量子通道。一个显而易见的问题：为什么使用它A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）5961______H·r，·r，H· 。ııı。˜`·X。ııı。Z__Q。如果爱丽丝和鲍勃之间有一个量子通道，这个算法会测量最终状态将导致原始的逻辑量子比特已经被传输到鲍勃的量子比特中的量子比特。问题不在于正确性，而在于解释。其次，理解测量对于避免将量子计算误解为一个整体是至关重要的（例如，量子计算是一个整体为什么量子计算并没有直接导致复杂性的指数级跳跃（2013年）。这篇文章采取的观点为了理解量子计算的可能性和局限性，测量需要以一种优雅的方式被形式化。请注意，本文中讨论的投影测量并不是量子测量的唯一可能性，但它是最简单的测量之一。此外，任何量子测量都可以通过单位映射和投影测量的作用来再现，这是一个很teleportq→let（e1，e2）=eprin在哪里let（q′，y′）= alice（q，e1）in.bob（q′，y′，e2）q.。alice（q，e1）→let（q′，y′）=cnot（q，e1）in（H q′），y′）b或b（q′，y′，e2）→let（y′′，e′2）=cX（y′，e2）inlet（q′′，e′2′）=cZ（q′，e′2）in（q′′，y′′，e′2′）epr″cnot（（H0），0）|0⟩.|0⟩用于具有延迟测量的图1。非扩展λq中的隐形传态算法。在本文的第二部分中，详细描述了van Tonder's λ q的加量过程本节最后给出了远距传输算法在扩展λq中的实现。第3节讨论并证明了扩展λq的影响。最后，第4节以正在进行和未来工作的详细信息结束。2添加测量值在量子λ演算中加入一个测量算子，只需要对语法进行很小的修改就可以实现在本节中，我们将向您展示如何更改语法、为术语添加良好形式的规则以及提供操作语义。2.1语法为了对测量进行计数，λq的语法必须用一个测量算子族MI来扩展，M I测量由集合I指示的量子比特。此外，为了使量子比特的语法精确，这是必要的，因为它们的"形状"是测量运算符所需要的这是以遵循线性[3]和QML[5]的方式实现的。关于vanTonder扩展的语法在图2中示出，并且在图3中给出了良好形式的附加规则。62A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）59术语是由图2中的语法产生的前置术语，它遵循van Tonder [10]给出的良好形式性规则加上图3中的规则。在这些规则中，请注意M和Gate声明MI和cU只是一个常数符号。零和一力|0和|1分别是非线性项。[10] 张量和!张量允许张量产生量子比特之间的张量来写入。虽然像（cU q）q这样的项是不允许的，但它们是cU I（qq）的收缩。叠加提供了一种在叠加中写入量子比特的方法，并且简化了允许去除标量因子为0的子项。请注意，这是一个带有模式的术语! qq不是形式良好的，但总是有一个等价的术语，可以用形式良好的方式来表达。 例如，在 这个期限! |0 ⟩ ⊗ (α! |0 ⟩ + β! |1⟩) isnot well-formed, however, it is equivalent to α (! |0! |0）+β（! |0! |1），这是良好的形式。t：：=Pre-terms：x变量（λx.t）抽象（t t）应用程序! t非线性项。（λ! x.t）非线性抽象cU门控常数Q量子比特常数MI测量常数{\displaystyle I}Q：：=Qubit常数：|0||1基本量子比特（qq）张量积（q+q）叠加α（q）标量积cU：：=门常数：H|cnot|X|Z|...图2。 扩展λq的语法。A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）59632nΣ−1INM► MI► CU门01哦! |0 ►! |1χ►q1Δ►q2χ， Δ►q1q22nΣ−1i=0张量Γ ►! Q1Δ ►! Q2Γ，Δ ►! Q1! Q2!张紧器► α0（! |0··! |0）+··+ α2n−1（! |1! |1）α r= 0，r她家{0，...，2 n− 1\r\n2nΣ−1i=0i=0αiqiSimplificationI R图。3. 在λq上增加了良好形式的规则。注1：通常的let结构将用作useful shorthand，定义为：让x=tinu给出（λx.u）t让! x=tinugives（λ! x.u）t有趣的是，注意到一台克隆机器像λx一样。（让y=xinyy）是λx的合成糖。（（λy. yy）x），它被良形规则所禁止，因为它是线性的（它不能出现两次），而且没有办法得到张 量 变量：它们只能是量子常数。let也可以用在列表上，例如van Tonder 's（x，y），但它们在这里写成张量积。 例如，项让xy = M{1， 2}（q1q2）int与t中的let（x，y）=（M{1}q1，M{1}q2）相同。此外，请注意，xy用于遵循van Tonder's （x，y）;它是运算符的重载，表示量子比特和列表构造函数之间的张量积。2.2操作语义学量子系统中的测量是一种固有的概率运算。根据Di Pierroet al. [4]，其中概率重写系统定义在λ-演算之上，扩展λq中测量的操作语义定义为：{\displaystyle {\}|2 = 1 α i她家C，i = 0...|2 = 1α i∈ C,i = 0... 2 n−1叠加的►γαiqi64A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）59ΣΣ| ⟩1Σ2MK! QK ）与!qk=! Xk=1以下内容：M：（M）q=Q）→2m−1U=0αuq（u）Σαuq（u） i她家I，1≤i≤m在哪里HIPWu她家C（w，m，I）√pw• W = 0，...，2|我|-1。• q（u）=! q（u）! q（u）··! Q（u）with ! q（u）=! |0 ⟩ or ! |1 ⟩ for k = 1 ... M。• C（w，m，I）是长度为m的二进制词的集合，因此它们与w一致在索引I的字母中。• pw=u她家C（w，m，I）|2.|2.• 符号t→ptJ意味着t以概率p到达tJ。看看这条规则的一个实际例子是很有启发性的：2Σ5−1U=05（U）（u）x是u的二进制表示中的第k位。根据上一个规则，（M Iq）将生成2|我|= 8个不同的输出（对应于所拥有的不同的输出）量子比特2、3和5的值，其被测量）。以输出w= 2为例（其3位二进制表示为010）。Hence，C（2， 5，I）={ 4， 6， 20， 22}，其中是0和25−1之间的数u，其二进制表示形式为x01和 0（因此它们与w匹配，如果我们将u的位2，3和5与w的位1，2和3进行比较）。然后，最后一个术语是：α4q（4）+α6q（6）+α20q（20）+α22q（22）√p2√p2√p2√p2在哪里Q（4）=!|0! |0! |1! |0! |0 q（6）= |0!|0! |1! |1! |Q（20）=! |1! |0! |1! |0!|Q（22）=! |1! |0! |1! |1! |0p2=u她家C（2， 5，I）|2 =|α4 |2+|α6 |2+|α20 |2+|α22|2|2其表示以下量子态的量子态的形式：例2.1设m= 5，I={ 2， 3， 5}，q=αu（A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）59651√P2（α4|00100+ α6|00110+ α20|10100+ α22|10110）66A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）59121 11 2 1 2ıı2.3条件性陈述式测量作为一个功能是唯一有用的，如果测量的结果可以用来确定程序的未来发展，那么它是一个功能。需要一个类似于QML中给出的条件陈述式。然而，与QML的if语句[ 5 ]相反，在该条件下只允许基量子比特这就是所需的全部内容，因为IF结构只需要提供一种读取测量输出的方法。条件语句是通过将以下语句添加到语法中来实现的如果t1则t2否则t3而操作语义由以下各项给出：如果! |0 ⟩ then t 如果t →t-|0如果! |1 ⟩ then t 如果t →t-|1请注意，虽然条件可能不是一个基本的量子比特，但并不能保证整个术语会减少。这个加法是必需的，因为如果没有这样的语句，这个对度量的扩展将等价于从单位常数到量子运算常数的一个简单的扩展，就像这个被添加到2.4示例：远距传输算法。随着规则的发展，远距传输算法可能会被重写为图1中所示。4.传送q→1让xy=eprin在哪里让b1b2=M{1，2}使q x在q中鲍勃b1b2yH，/，˜`alizeq x→1letrw=cnotqxin（H r）w）bobb1b2y→1zedb1（exb2y）exb x→1ifbthen（X y）elsey|0⟩|0H·r，~，~，r，~，~，、、、˜`Qzedb x→1ifbthen（Z x）elsexeprqcnot（（H! |0⟩)⊗! |0）用于原始量子隐形传态算法的电路。图。4. 扩展λq中的隐形传态算法3与Fluence在定义一种语言时，还必须提供语法（如何构造术语）和语义学（如何计算这些术语）。语义可以被表示为- tional（术语映射到语义域的元素，每个元素对应于语义域的元素）。Zb1Xb2·A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）5967Σ由该术语计算的内容）或运算式（术语映射到其他术语，每个转换对应于一个计算步骤）。显然，必须提供所提供的语义是明确和一致的。例如，语义学通常会在术语上推导出一个等价理论（通过语义学领域中的等价性，或者通过在一个术语还原为另一个术语的情况下将两个术语等价），重要的是，这个理论不应该使所有术语等价。在λq中给出了一个一致的等式理论。然而，加法测量并不对应于一个简单的方程推理系统。根据任何方程理论，用相等的项来替换项是不可能的，因为测量是一种概率运算，并且每一个约简实例都可能产生在系统中不可能调和的不同的项。在操作语义学存在的情况下，证明结果一致性的通常方法是提供一致性的证明。此属性声明，应用过渡规则的顺序与最终结果无关，因此消除了任何不明确之处。[10] 在本节中，我们将展示这样一项关于影响力的研究是如何持续下去的。即使在可能性存在的情况下，也会被带过。由于λq提供了一个固定的还原策略，证明对原始语言的影响是微不足道的，因为每一步只有一个可能的还原。然而，在测量存在的情况下，情况并非如此，在测量存在的情况下，证明影响是非平凡的。3.1定义与引理虽然上面提到的概率约简是呈现操作语义学的一种优雅而简洁的方式，但在这种情况下，对影响的研究并不是立即的。为了一致，有必要证明，如果任何项都可以还原为u和v，那么就存在一个w，使得u→w？v→w。然而，在概率演算中，它可能是t→pu和t→qv，其中p和q表示各自还原发生的概率，并且不存在u和v都可以还原为的w。例如，给定M{1}，计算中的度量运算符。基本上，它遵循M{1}（α| 0 + β|1）→|α|2| 0和M{1}（α| 0 + β|1）→|β|2|1。然而，没有什么是这样的。|0→pw和|1→qw。处理这个问题的一种方法是假设，如果有一些正常的形式可以以一定的概率达到，那么通过遵循任何路径，它必须是可能的，以同样的概率达到同样的正常形式。然而，这个定义并不严格，也不适用于没有正态形式的术语。Hence，它不允许开发一个正式的证明confluence。概率转换需要被抽象出来，以便为每个项只允许一个可能的范式，并且处理没有范式的项。有了这个目标，下面的定义给出了一个对概率计算有影响的概念：定义3.1一个项集合{}被定义为项t i的集合，每个项都具有关联概率α i，因此α i=1。i请注意，给定一个术语t，它可以被视为一个术语集合{}。68A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）59ΣX24444iiJJiiJJ示例3.2考虑术语集合{，，}，其中termt1出现了两次。 通过对任何等价项的概率求和，这个集合可以与最紧集合{，}等同。注3.3在本文中，符号=将用于α-等价性和等价性。 当环指一组时，即当每个元素出现一次时，它被认为是模α-等价的。{，}与{}相同的适当步骤它需要被拿走。定义3.4将此等效性形式化：定义3.4让first成为一个函数，它取一个集合项并返回一个由fined第一个（{}）={ti}因为共域是一个集合，所以它只允许每个元素的一个实例。设sumprob是一个函数，它取一个项和一个项集合，并返回与集合中该项的每个实例相关联的概率之和sumprob（s，{}）=αjj{ i}|ti = s}最后，让min成为一个函数，它取一个项集合，并返回一个项集合，由min（τ）=t≥firstτ{}{tJ，α γ} }itJ−ΣγJ=1。其中单个术语之间的所有减少都是通过遵循任何规则产生的X或无。引理3.6给出一个概率重写系统P，然后Det（P）保留集合。XXt≥firstτJJγijJJA. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）5969J{}{}{}→ii i iijijRT⎭ΣΣS⎩P证明。 让t、α和t ，α γ是像t，α这样的集合项{}和ν={}和ω2 ={}和ω2={sj，γj}和任何contextC，项集合τ1={C[ti/x]，αi}和τ2={C [sj/x]，γj}a re也是等价的。证明。 ω1″ω2−min（ω1）=min（ω2），定义为等于{}，则min（τ1）=t≥first（τ1）{增加的规则的强大影响力由theo-rem3.11正式表达和提供。定理3.11概率约简规则系统T ={（M），IF-|0，IF-|1>它是强有力的流动。证明。给 定 集合项τ ={}。 （类似于t3）。Q(ii) ν=τ。 ω1=ω2=μ。(iii) t=λx.tJ.设μ={λx.ui，αi}其中（tJ）αiui），其中 αi= 1，让ν=i{λx.vj，γj}其中（tJ→Tγvj）withγj=1。J根据归纳法，存在等价项集合ω1j。={}suc hthatui→βw1andvj→σIKKW2.Henceω1={<λx. w1，αiβi}和ω2={<λx。w2，γjσj}可以beta ken，whi ch它等价于引理3.10。(iv) t=λ! x.tJ，类似于情况（iii）。(v) t=（t1t2）。考虑以下几种情况：(a) 设μ={（t1ui），αi}其中t2→Tαui，其中αi= 1，并且iletν={（t1vj），γj}其中t2→Tγvj，withγj=1。J这种情况类似于情况（iii），因为引理3.10适用。(b) Letμ={<（uit2），αi>}和ν={<（vjt2），γj>}。 这是以下情况（a）。(c) Letμ={（uit2），αi}和ν={（t1vj），γj}，thentakeω1=ω2={（uivj），αiγj}(d) Lett=（MIq），μ={}其中（MIq）→Tα以下情况（ii）。ω1=ω2=μ。q j，其中 α i= 1。这个i(vi) t=如果t1则t2否则t3。 考虑以下几种情况：(a) 让μ={}其中t3→Tαui，其中αi= 1且iletν={}，μ和ν，μ/= ν，suchS Tτ→μ和τ→ν，那么这意味着存在等价项集合（τ → μ和τ → ν）T Sω1和ω2使得μ→ω1和ν→ω2，然后S和T验证假设A. Díaz-Caro et al./理论计算机科学电子笔记270（1）（2011）5973JST1Σ2S定理3.9，它提供了它们之间的强交换。这里使用t上的结构归纳法给出了这个结果。(i) t = x|C U|Q|M I|! t†$μ/=ν。 请注意，在这种情况下，T或S中没有可以减少t的规则，只有Id适用，产生μ=τ。因此，任何ν/=μ都不可能存在。(ii) ν=τ。ω1=ω2=μ。（类似于μ=τ）。S T(iii) t= λx.tJ，μ={<λx.u，1>}和ν={<λx。vj，γj}su chτ→μ和τ→ν。根据归纳法，存在等价物ωJ={}和ωJ={}。1s2jT S{u，1}→ωJ和{vj，γj}→ωJ。因此ta keω1={<λx。w1，δs}和ω2={<λx.w2，σ j>}，其等价于引理3.10。(iv) t=λ! x.tJ.类似于案例（iii）。(v) t=（t1t2）。考虑以下几种情况：(a) μ={（t1u），1}和ν={（t1vj），γj}。 类比t或情况（iii）;注意引理3.10也适用于这种情况。(b) μ={（ut2），1}和ν={（vjt2），γj}。 类比t或其b的情况（a）。（c）μ={<（ut2），1>}和ν={<（t1vj），γj>}。Takeω1=ω2={<（uvj），γj}（类似地，如果t2→1u和t1→γjvj）。(d) t=（cU q）和μ={}其中t3→S1uandν={}，thentakeω1=ω2=ν。 类比ift2→S1uandν={}其中t2→S1uandν={}，thentakeω1=ω2={}。 类似地，如果t3→S1uandν={

下载后可阅读完整内容，剩余1页未读，立即下载