分布式测量的量子计算模型及形式语言的定义和应用监控

理论计算机科学电子笔记170（2007）73-94www.elsevier.com/locate/entcs基于分布式测量的量子计算文森特·达诺斯1Universit'eParis7CNRSEllieVrije Universiteit BrusselElham Kashefi3滑铁卢大学普拉卡什·帕南杰4麦吉尔大学摘要我们开发了一个正式的模型，分布式测量为基础的量子计算，采用基于代理的观点，这样的计算在本地描述的可能。由于网络量子态一般是纠缠的，我们需要将其建模为全局结构，让人想起经典代理系统中的全局记忆。局域量子计算被描述为测量模式。由于基于测量的量子计算本质上是分布式的，这允许我们自然地扩展测量演算的几个概念[2]，这是这种计算的正式模型我们的目标是定义一种汇编语言，也就是说，我们假设计算是良好定义的，我们不关心验证技术。代理系统的操作语义由概率转移系统给出，我们以对应于双相似性概念的方式定义操作等价有了这个地方，我们证明了隐形传态是一个直接的量子通道，这也在更大的网络的背景下。关键词：形式语言，量子通信，量子计算，语义。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.12.01274诉Danos等人理论计算机科学电子笔记170（2007）731介绍基于测量的模型为思考量子计算提供了一个有趣的新框架。虽然量子电路仍然被广泛认为是描述算法的方便形式，但使用测量来引导量子计算被认为是一种严肃的替代方案。由于其固有的概率性质，测量长期以来被认为是对量子计算的干扰-尽管当想要读出计算的最终输出时，它们是不可避免的。它们可以是计算的活跃组件，这一点通过隐形传态协议已经知道了相当长的一段时间。直到很久以后，人们才意识到在容错结构中，测量是非常有用的。不久之后，随着单向量子计算机[11]和隐形传态模型[9，8]等模型的出现，人们确定测量不仅是计算的重复组成部分，而且是计算背后的实际驱动力。此外，测量范式为量子计算机的实际物理实现策略提供了全新的视角[12]。然而，测量并不是这些模型的唯一关键要素：它们也是固有的分布。事实上，这是实现隐形传态协议的变体不仅传输而且转换量子信息，这是隐形传态模型的基础同样，单向量子计算机是通过测量和传输进行转换的，这次是通过一种通用的纠缠态，即图形态。对这种状态的单量子比特测量转换逻辑量子比特，即量子输入，同时通过图形状态量子比特的路径传输它们同样，由特定纠缠特性提供的非局域相关性与测量一起，引导计算。当然，量子测量本质上仍然是概率性的，但这可以通过应用依赖于先前测量结果的校正来解决，从而使计算有效地确定。请注意，测量结果的依赖性是至关重要的，以获得模型的普适性。因此，经典通信的典型分布式概念也自然存在于这些模型中。所有这些都被测量calculus[2]，单向计算的形式框架。测量模式-基本上由单向模型中允许的命令序列定义由此可以定义操作语义和指称语义，1电子邮件：Vincent. pps.jussieu.fr2电子邮件：Ellie. vub.ac.be3电子邮件：ekashefi@iqc.ca4电子邮件：Prakash@cs.mcgi ll。CA诉Danos等人理论计算机科学电子笔记170（2007）7375证明它们的等价性，并证明组合的概念是有明确定义的。更重要的是，有一个相关的重写系统，允许将任何模式放入标准形式。测量演算，可以被看作是一种汇编语言，被证明是一种有价值的工具，用于正式研究所有基于测量的模型;例如，人们可以很容易地显示出隐形传态模型如何通过相关演算之间的转换简化为单向模型[3]。由于固有的分布式方面，量子计算的基于测量的模型非常适合作为分布式量子计算的正式模型的起点。这里我们指的是宏观上的分布式，也就是说，我们谈论的是不同参与方之间的协调行动。在量子计算中有许多例子[10]：隐形传态，当然，还有纠缠交换，逻辑门隐形传态，密码协议，以及经典分布式应用的量子版本，如领导选举[5]。然而，分布式量子计算的形式语言是缺乏的。最近有一些基于经典进程演算的有趣的发展[7，6]，主要集中在并发方面。虽然计算的分布式本质是通过参考文献[6]中的类型引入的，但其目的是开发形式化的验证技术。在这项工作中，我们采取汇编语言的观点，假设计算是定义良好的。这导致了一个紧凑的模型，我们可以探索分布式协议的属性，如代理之间的协调。我们为分布式应用程序定义了一种汇编语言，它直接建立在最基本的分布式模型上：单向量子计算机。我们采用局部的观点，并将系统描述为一组代理同步通信并在全局纠缠量子态上操作;这将在第二节中解释。二、节中2.1我们为作为概率转移系统的代理系统开发了形式语义。运算等价的定义方式与双相似性概念相对应。然后，我们证明了量子隐形传态是bisimilike一个直接的量子通道，这也在其他的背景下，可能纠缠，代理，在SEC。3 .第三章。虽然在[6，1]之前已经在其他形式框架中证明了隐形传态的正确性，但双相似性方法，特别是考虑到更大的上下文，是新的。我们在SEC结束四、假设对测量演算模型有一定的了解;为了深入阐述，我们参考参考文献[2]。76诉Danos等人理论计算机科学电子笔记170（2007）732代理人网络在我们的分布式测量为基础的量子计算模型的主要概念是一个代理。代理是本地化的进程，它们并行执行，构成一个分布式系统。形式上，我们以如下方式定义代理人。定义2.1施事A（i，o）：Q。E，具有经典输入i和输出o，并且由一组量子位参考Q给出排序，由以下组成的有限事件序列E定义：(i) 图案命令序列A，其中输入量子位在Q中;(ii) 经典的消息接收C？x和发送c！y，其中c是经典信道，并且x和y是名称;(iii) 量子比特接收质量控制？x和发送qc！其中Qc是量子信道，并且Q是量子比特参考。代理经典变量和量子位引用，到值。请注意，任何模式P（V，I，O，A）平凡地对应于代理A：I. A.一般来说，排序Q等于IIs，其中I是本地量子输入，Is是网络提供的共享纠缠态的量子位下面2.3。经典的输入i和输出o允许我们对诸如超密集编码之类的协议进行建模，其中代理希望在共享Bell状态的帮助下将经典本地状态用于存储由本地模式执行、输入从其他代理通过经典通道c，和经典的输入绑定从当地的环境。根据需要，进一步的绑定被添加到状态;也就是说，例如，每当测量量子位时，只有对应于量子位参考qi的信号名称si才被添加到Γ的域并绑定到经典测量结果v，表示为Γ[si<$→v]。经典输出集o决定了在计算的最终输出中，必须保留Γ中的我们把局部状态限定为经典的输出。我们对代理人的解释与通常的过程方法不同，因为在我们的设置中，代理人总是对应于分布式网络中的实际各方，由标签A表示。因此，形式A（i，o）的表达式：Q. E应该读作：名为A（Alice）的代理运行程序E与量子位和输入和输出指定。因此，代理是在特定处理器上运行的一段代码。 在这种情况下，如果代理名称相同，则组合代理。我们称之为代理组合，其正式定义如下。 请注意，由于我们允许诉Danos等人理论计算机科学电子笔记170（2007）73771121后续的代理程序提供额外的经典和量子输入以及进一步的过程输出从先前的程序，需要一些照顾除此之外，代理组合只是事件序列的简单串联。定义2.2主体A（i1，o1）的合成：Q1。E1和A（i2，o2）：问题2. E2，仅定义为具有相同代理名称的代理，表示为A [（i2，o2）：Q2. E2][（i1，o1）：Q1. E1]并由A（i，o）：Q. E2E1与⎧⎪⎨i=i1∪(i2\o1)o=o1o2拉吉（一）其中QJQ=Q1<$（Q2\Q1），是第一个代理的输出排序。注意，输出排序可以通过检查代理的事件来确定顺序一般的想法是o1<$i2和QJ<$Q2，因此随后的程序至少是根据以前程序的输出来定义的。 这总是通过假设o1中的这些名称的恒等变换来安排，J不出现在E2中。 特别是，这意味着QJ=QJ。 额外的输入在随后的程序中，例如当几个量子位被一个接一个地传送在这种情况下，爱丽丝需要连续执行她的协议，每次启动协议时都提供新的本地量子输入。同样的论点适用于classi-cal输入排序时，几个密集的编码协议。当然，最好是在网络的背景下理解这一点，而不是下面定义的代理组成。代理网络由多个代理同时执行其事件序列组成由于网络量子态本质上是非局域的，因此除了将其视为某种全局记忆之外，没有其他选择-即使我们希望坚持局部观点。这导致了以下定义。定义2.3代理网络N由一组同时行动的代理以及共享的量子态定义，即N = A1（i1，o1）：Q1. E1|......这是什么？| Am (im,om) : Q m. Emσ为|iAi（ii，oi）：Q i. Eiσ，（二）⎪Q78诉Danos等人理论计算机科学电子笔记170（2007）73i=1i=1i=1i=1当r eσ∈D（H±Is）时，对所有i，Qi=Ii<$Is.我我我定义中的网络状态σ是初始纠缠资源，它在代理之间分配。在初始化过程中，Ii中指定的局部量子输入被添加到网络状态σ通过这种方式，我们可以保持初始共享纠缠作为我们模型中的第一类原语在本文中，我们不描述产生σ的实际过程。请注意，网络中的代理需要有不同的名称，因为它们对应于组成分布式系统的不同部分换句话说，并发性只来自于分布;我们不考虑在一方的上下文中并行组合进程最后，个体代理A（i，o）：Q。E平凡地对应于网络A（i，o）：Q. E =0。因此，关于网络的陈述也包括个体代理。我们定义了两种不同的方式组成网络的代理，即顺序和并行组成。由于我们将代理解释为分布式过程，因此这些操作存在一些约束。序列组合仅定义为包含相同代理的网络;其思想是代理一个接一个地执行两个网络的事件序列。此外，主体组合必须按照定义2.2定义，也就是说，第二个网络的输入和初始排序必须包含第一个网络的输出和最终排序。形式上，如下。定义2.4网络的顺序组成N1= |MAi（i1，i，o1，i）：Q1岛E1，i<$σ1和N2= |mAi（i2，i，o2，i）：Q2，i. E2，i∈σ2定义为N2<$N1= |MAi[（i2，i，o2，i）：Q2，i. E2，i] n [（i1，i，o1，i）：Q1，i. E1，i]<$σ1<$σ2.（三）请注意，我们已经重载了符号来表示代理和网络组成。只要两个网络具有相同数量的代理，人们总是可以通过重命名代理来安排它们两个顺序可组合。事实上，人们甚至可以通过向具有较少代理的网络中添加空代理（即仅代理名称）来组成具有不同数量代理的网络。假设两个网络的准备都是在不相交的希尔伯特空间上定义的;组合网络它们被解释为两个网络都使用的不同的纠缠资源平行合成，表示两个网络平行运行且相互独立，仅定义为包含不同代理的网络同样，人们总是可以重命名代理，以便这是定义良好的。定义2.5网络的组成N1= |MAi（i1，i，o1，i）：Q1，i. E1，i诉Danos等人理论计算机科学电子笔记170（2007）7379i=1i=1σ1和N2= |nBi（i2，i，o2，i）：Q2，i. E2，i∈σ2定义为N1<$N2= |Mni=1Ai（i1，i，o1，i）：Q1，i. E1，iBi（i2，i，o2，i）：Q2，i. E2，i（四）σ1通过组合顺序和并行组合，可以表达广泛的网络组合。节中2.3我们证明了网络的语义在这些操作下得到了保持。上面给出的定义可以用抽象语法的形式简明地表示出来。我们使用[]而不是|分离表达式的选择，因为后者已经用于表示并行组合。A：：= nil [] E [] M [] C [] A A [] A. 一E：：=c？x[]c！x[]qc？q[]qc！q[] A [] E. Ea：：= A（i，o）：Q. E [] A [（i2，o2）：Q2.E2][（i1，o1）：Q1. E1]N：：= |iai<$σ [] N<$N [] N <$N（五）在上面的E，M和C代表任何纠缠，测量或校正命令，nil是空命令。我们避免给出名称的语法;相反，我们使用下面描述的约定请注意，模式命令序列和网络都可以被视为传统进程代数意义上的进程，其中组合操作将任何两个模式（分别为网络）转换为新的模式或网络。事件序列的定义也很常见，可以按顺序组合。然而，代理在进程代数框架中的地位不太明确。这正是因为它们是形式化分布式概念的构造，因此对它们如何组合存在约束这不是我们模型的一个规则，而是一个要求，如果你想使分布显式。在本文中，我们遵循了几个符号约定。当上下文很清楚时，通常情况下，我们不明确地提到输入和输出，而只是写A：Q。此外，我们不写输入，输出，排序或准备，如果没有，有时写-为空的输入或输出集。 例如，A（−，{x}）。c？x是没有输入和没有量子位的代理，而A（−，{x}）。c？X|B（{y}，−）.c！y是没有准备的网络，其中两个代理之间交换经典值。我们写C？xy为c？xc？y，并且对于其他通信信道也是类似的。在定义2.1中，为了简洁起见，我们使用了模式命令序列而不是完整的模式，并约定模式的输入是|80诉Danos等人理论计算机科学电子笔记170（2007）73总是由在模式执行时属于代理排序的计算空间中的那些量子位给出。模式的输出只是由那些未被测量的量子位给出。 比如说，在单个工作A中：{1，2}。Xs1M0E14qubit1是输入到4 1模式和4是一个输出;我们也写为A：{1，2}。H（1，4）。图案假设不在代理排序中的量子位是初始化为|如前所述，并且不需要在代理的排序中明确提及。 另一方面，在模式事件中没有提到的代理量子位，如上面的量子位2，总是被假设为是单独的。也就是说，我们并没有显式地写出我应用于A的剩余量子位2的恒等模式。我们考虑模式命令序列而不是单个命令，以便我们可以使用模式的大步语义。从这些例子中可以看出，我们经常通过数字来指代量子位;具体地说，我们主要将量子位q i称为量子位i，而dsi代替sqi来 表示 相应 的 信号variable。 这是因为模式看起来和参考文献[ 2 ]中的模式一样的优点。在下面的内容中，我们使用特定的字母表示特定的名称，特别是我们使用qi或仅i表示量子位引用，xi和yi表示普通的经典变量，vi表示经典值，si表示经典信号变量。我们将代理网络置于确定性条件下，以确保计算是良好定义的。（H0）代理具有计算空间V的模式事件具有QV中的输入;（H1）一个主体（H2）每个量子和经典消息接收事件具有相应的量子、相应的经典消息发送事件;（H3）所有的名字，即经典变量和量子引用，都是唯一的。2.1操作语义在我们为分布式计算提供具体的评估规则之前，我们给出一些关于如何在本地视图中执行的解释和示例在整个网络演化过程中，每个代理都可以通过它拥有的量子位访问网络状态σ，每当执行模式事件时都会转换σ虽然这些模式是局部的，但σ不是，为了保留相关性的所有信息，我们需要保持σ在任何时候都不约简例如，假设一个代理A拥有系统状态σ（1，2，3，4，5）的前两个量子位它的下一个事件是在它的第一个量子位上执行Hadamard模式H（1，6如上所述，我们没有明确地写出我应用于A更重要的是，在这种情况下，我们也没有为不属于A诉Danos等人理论计算机科学电子笔记170（2007）73813、4和5。总之，这意味着我们有一个评估步骤，如下所示σ，A：{1，2}。H（1， 6）=<$σJ，A：{6， 2}，（6）其中σJ=<$H（1，6）<$I<$4（2，3，4，5））σ，即σJ=（H<$I<$4）σ（H<$I<$4）。我们将转换关系表示为=。 H的执行发生在单个转换步骤依赖于其大步骤语义。通过这种方式，我们避免了进入模式执行的实际细节，这不是本文要讨论的内容。特别要注意的是，A的排序发生了变化。这是因为测量是破坏性的，因此输入量子位1已经消失，输出量子位6已经取代了它的位置。 正因为如此，我们有时明确地写σJ（6， 2， 3， 4， 5）在上述评估规则的右手侧。1的唯一剩余是其对应的测量结果s1，其经由添加的绑定Γ[s1<$→v]记录在状态Γ中，其中v是测量结果。A可能随后通过事件c将s1发送给其他代理！s1，所以一般来说我们不能从Γ中删除这个条目这基本上意味着，当通过执行随后的局部模式或通过来自其他代理的量子通信来生成新的量子位引用时，这些名称需要是唯一的。因为我们不想进入这个命名过程的实际细节，因为我们认为我们的模型是在汇编语言的级别上，即在命名冲突已经解决的阶段，我们在上面强加了这个作为定义条件最后一点涉及代理的经典输入和输出，分别从自己的本地系统接收和发送在局部视图中，模式事件也可以依赖于经典输入，而不仅仅是测量输出。由于局部状态Γ的均匀结构，我们可以将输入依赖性背负到MC的信号依赖性结构上。如前所述，这就是为什么MC是构建分布式量子计算框架的良好基础的原因之一记住了这些具体的例子，我们现在就可以开发局部视图的操作语义像往常一样，我们首先根据小步过渡来定义规则，然后我们切换到大步框架。分布式计算的小步过渡本质上描述了代理和网络如何在不同的时间步长上进化我们采用了一种简化的代理符号，省去了经典的输入和输出，82诉Danos等人理论计算机科学电子笔记170（2007）73我其不随小步长减小而改变ai= Ai：Q i。Eiai.E = Ai：Q i. [Ei.E]a−q= A：Q\{q}。Ea+q= A：Q {q}。E[q/x]，（七）其中E是某个事件，Ei和EJ是事件序列。配置由系统状态σ和一组代理程序以及它们的状态（具体地说，σ，|i r i，ai= σ，r 1，a1|Γ 2，a2|. . . ...这是什么？ |嗯，嗯。（八）配置转换的小步规则，记为= n，在下面详细说明;我们随后给出一些解释。当系统状态在评估步骤中没有改变时，我们通过在规则之前加上σ来强调这一点。σ，P（V，I，O，A）−→λσJ，ΓJ（九）σ，r，A：IR. [E. P]= λσJ，r ∈ r J，A：OR. Er 2（y）= vσ n（r 1，a1. c？X|r 2，a2。c！y=<$r 1 [x <$→ v]，a1|r 2，a2）（十）σσ（r，a. qc？X|r，a. qc！q=r，a+q|r，a−q）（11）1 1 221122L=λRL|LJ= λR |LJ（十二）在这里，表示结果图的并集。这些规则中隐含的是顺序组合规则，它确保代理的事件序列中的所有事件一个接一个地执行。第一条规则是局部操作;我们在这里写了完整的模式而不是命令序列，以使模式输入和输出显式。因为模式的大步语义是由−→描述的概率转移系统给出的，所以我们在这里选择概率λ。此外，代理根据模式的输出O改变其排序，如上面的示例中所解释的下一条规则是关于古典的renewal-vous，很简单。对于量子重定向，我们需要将接收代理的事件序列中的x替换为q，并进一步调整量子比特排序。最后一条规则是元规则，诉Danos等人理论计算机科学电子笔记170（2007）7383这是必需的84诉Danos等人理论计算机科学电子笔记170（2007）73i=1我，我，我γ表示任何其他规则都可以在更大的系统上下文中触发。L和R分别代表前面任何规则的任何可能的左侧和右侧，而LJ是一个任意的配置。请注意，我们可能需要重新排列代理的并行组合中的项，才能应用上下文规则。 这总是可以做到的，因为配置中代理的顺序是任意的。在网络执行的推导中，我们通常不会像（12）那样明确地写出约简，而是指定在当前网络的上下文中其他规则的执行顺序。 正是在这最后一条规则中，引入了网络级的非确定性，也就是说，在网络的上下文中，几个代理转换可能同时发生。从上面的小步规则开始，我们现在可以定义代理系统的大步语义。我们首先定义计算路径，通过小步过渡从初始配置运行到最终配置。在初始配置中，所有的局域态都由包含经典输入约束的映射Γii给出，而网络状态d由输入约束决定资源与本地量子输入一起。 最终配置是一种其中所有代理都具有空命令序列，并且其中所有本地状态都被限制为经典输出绑定ri，oi。由于我们强加的定义性条件，每次计算总是以最终配置结束。假设代理Ai的初始量子态由下式给出：ρi∈Ii，路径定义如下。定义2.6给定一个代理网络N = |iAi（ii，oi）：Q i. Ei<$σ和量子输入ρi，路径γ是最大配置序列{Cj=σ j，|ir j，aj，j= 1，.，k− 1}，即我我C1= σ <$mρ i，|iΓ i，Ai：Q i. Ei我Cj=<$λjCj+1C k= σ k，|ir k，Ai：Qk（十三）我们写C瑟菌的1=λγ其中λγKj=1 λj，称之为Ck 最终配置还要注意，路径总是终止的，因为事件序列是有限的。我们可以直接定义系统的操作语义N是由其所有路径定义的概率转移系统（PTS）然而，我们选择识别那些导致代理网络的相同可观察行为的路径。具体地说，对于特定的输入i和ρ∈I，我们确定最终配置，其中只有在代理的局部状态中的内部绑定是不同的，也就是说，绑定的名称不是在经典的=诉Danos等人理论计算机科学电子笔记170（2007）7385我γ我我输出设置为0。这些绑定对应于模式事件中出现的测量结果，或者来自经典的renove-vous事件。只要这些不是经典输出的一部分，它们的实际值是唯一重要的。我们无法在每个模式事件之后跟踪这些测量结果，因为后续事件可能取决于这些值。请注意，最终的代理类型确实需要相同，很明显，最终的网络量子态也需要相同。识别这样的路径，在测量演算的风格，然后给我们一个网络的代理的语义。然而，由于并发代理执行其事件序列的顺序的非确定性，我们必须定义网络相对于特定调度的操作语义。时间表是代理执行事件的特定顺序。例 如 ，在网络A中：{1}。H（1，2）|B：{3}。H（3，4），可能的时间表是AB和BA。 如果我们不考虑时间表，我们将把所有路径和所有时间表的概率相加，得到相同的最终配置，对于上面的例子，这导致计算任意输入的HH我们避免对时间表给出正式的定义，正如我们将在第二节中找到的那样。2.2网络的语义与时间表无关。把所有这些放在一起，我们得到以下定义。定义2.7网络的操作语义N = |iAi（ii，oi）：Q i. 相对于特定的时间表，Eiσ是将初始配置与最终配置相关联的概率转换系统，<$N）op：iQ i→ iQJ。⊗iρ i，|iI=<$λσJ，|伊俄（十四）Σ其中λ=γλγ，并且求和遍历所有路径γ，使得σσρ，|（Γ，A（i，o）：Q. EσJ，|（Γ，A（i，o）：Q（J）.（十五）我我我我我我i）=λγ我啊我我我我我们称之为iQ iiQj是网络的类型从现在开始，我们将输入量子位的集合记为I=iIi，将输出量子位的集合记为O=iQJ，并分别将D（HI）和D（HO网络的语义相对于因此，该时间表将D（HI）中的量子态加上经典输入与D（HO）中的量子态以及具有特定概率的经典输出相关联。注意，转换系统的类型是从初始排序到最终排序的映射;这个组件在我们在第二节中开发的指称语义中是相同的2.2.我们说两个网络 N1和N2 在操作上是等价的，如果它们的操作语义（由PTS给出）是相同的，并写<$N1）op<$N2）op。我我86诉Danos等人理论计算机科学电子笔记170（2007）73事实上，我们用双相似性的概念来确定操作等价性。这确实是合理的，因为通过像在定义式2.7中那样识别计算路径，我们实际上在最终配置上强加了一个双相似关系。正如我们将在SEC中看到的那样。3，正是通过这样做，我们可以证明，除其他外，隐形传态是双相似的直接量子信道。2.2指称语义由于其更抽象的特征，在许多情况下，它更适合于使用指称语义。这就是为什么我们为代理网络和以前一样，它与操作语义学以及普通模式的语义学密切相关事实上，在检查定义2.7时，我们看到对于任何调度，与代理网络相关联的PTS分解为几个部分。首先，有一个从初始到最终排序的映射，它决定了每个代理从初始到最终配置的量子位所有权如何演变。这被形式化为类型签名，就像我们对操作语义所做的那样。排序映射与经典输入无关：实际上，经典输入只出现在经典通信、泡利校正和测量角度中，而这些都不影响量子比特排序。此外，它们可以从网络定义中静态读取，并且也与调度无关。指称语义是从经典输入到经典输出和量子操作的映射，这反过来又决定了量子态在网络中的演化。然而，这两个分量不是彼此独立的，因为经典输出可以是测量结果，其以取决于所应用的量子操作的概率发生。为了简单起见，让我们首先考虑没有经典输出的情况。在这种情况下，对于每个经典输入i=iii，我们有映射L，它描述了网络量子态如何演化。这个映射是一个多局域量子操作，因为如果我们丢弃所有的分布式信息，即排序和通信事件，我们就只有一个普通的模式，即量子操作。 有一点需要注意：由于计算是异步进行的，所以不同的代理在程序中执行事件的顺序即存在不同的可能的时间表。然而，由于在计算的每个实例处，局部事件对不相交的量子位集合进行操作，因此这些操作以何种顺序被应用或者实际上它们是否同时被执行实际上并不重要这一说法在SEC中得到了正式证明。2.4;我们推迟到那时再进行充分的证明，因为它与下文所述的其他情况有关。因此，计算的任何时间表都会导致相同的量子操作。因此，为了确定L的操作元素，我们选择一个特定的时间表，然后在诉Danos等人理论计算机科学电子笔记170（2007）7387LiJ我我它们被执行的顺序，必要时使用身份模式进行张量，并忽略通信命令。然后，每个操作元素Lj对应于这些模式中的每一个的实现的顺序组合现在假设网络包含经典输出o=ioi。我们需要区分信号输出和外部输出，信号输出是测量结果，外部输出是最初由某个代理输入并在网络中发送的值。根据定义，外部输出oe=ioi，e仅取决于经典输入i;这些常数值通过经典通道在网络中发送。正是信号输出os=ioi，s取决于量子操作，反之亦然。实际上，当存在信号输出时，特定测量结果被保留，因此排除不对应于该结果的L的实现。这实质上意味着对每个可能的信号输出应用不同的量子操作。例如，假设对应于量子位3上的测量的信号输出之一然后只有那些包含运算符<$−α的实现|3、兼容os这个输出。我们将与输出os兼容的实现表示为，通过Los使用操作元素进行量化操作，并对这些元素进行计算限制。 然而，请注意，这是一个迹减少操作，并且Tr（L）os（ρ）正是输出的概率，发生。那么，而操作语义给出了每条路径的显式概率在指称语义中，这些包含在量子操作中。正是这种抽象，加上调度独立性，使指称框架的优势。实际上，经典输入对于所有时间表都是相同的，并且经典输出取决于经典输入和测量值，因此对于所有时间表以相同的概率发生，因为L是时间表无关的。 把所有这些放在一起，我们得出以下定义。定义2.8代理网络的指称语义N=|iAi (ii, oi): Q i. Eiσ由下式给出：<$N）：Q →Q J. i→{（o，Los），Lo}（16）与德伊伊伊ΣL：D（HI）→ D（HO）：iρi→ Lj（σiρi）L†，（17）J其中o=oeos，ρi是量子输入，QJ是主体Ai的最终排序，I和O分别是量子输入和输出空间。在没有输出的情况下，我们有<$N）de：iQ i→iQJ.i→ L，或者只是。如果没有输入也是。S88诉Danos等人理论计算机科学电子笔记170（2007）73S1请注意，上述每个元组中o的oe部分是相同的。作为例如，在nX s2M−α内，将实现比特流通道1 2[10]. Itcanbeintpreprepretedasone-ag entworkA（−，−） ：{1}. Xs2M−α，1 2具有作为指称语义的量子运算L（ρ）=pρ+（1-p）XρX。 然而，在时间上不工作A（−，{s}）：{1}。Xs2M−α具有不同的语义，即21 2{（0，pρ），（1，（1−p）XρX）}，（18）对于所有的ρ，其中p是α的函数。虽然这个例子看起来可能是人为的，但实际上至关重要的是，这些类型的网络的语义是不同的，因为它们描述了输出s2的不同知识状态，因此，采取了什么实际的计算路径。在底层量子操作L是确定性的情况下，所有实际化导致相同的量子输出。然而，即使在这种情况下，我们需要上述公式与不同的痕迹减少量子操作Los，since eedetermineeprobabilitiesofputtinggo。一个没有工作是确定性的，仅当对于任何输入i，量子操作L是确定的。istic，即它实现了一个酉的，并且经典输出o在所有实现中都是相同的如前所述，如果两个网络具有相同的指称语义，则它们被称为指称等价请注意，等效网络可能具有不同的准备状态，而且代理名称可能不同，但两个网络中的代理数量必须相同。有了上述定义，我们现在可以证明以下结果。命题2.9在代理网络的操作语义和指称存在精确的对应关系，也就是说，N1，N2：N1证据设<$N1）de=<$N2）de。这意味着对于所有经典和量子输入，类型和经典外部输出都是相同的。因为对于所有信号输出，Los=Los，所以我们具有L =L 因此，2计算路径对于两个网络也是相同的[4]。 所以两网络在操作上是等效的。Q由于这两种语义我们通常通过操作计算路径导出指称语义，也依赖于语义与时间无关的事实12诉Danos等人理论计算机科学电子笔记170（2007）73892.3组合性一个重要的目标是证明网络的语义是保守的，相对于网络组成的定义。2.4和2.5。知道了这一点，我们可以组合任何两个网络，并确保生成的网络执行预期的计算。换句话说，我们需要证明下面的Prop.2.10-然而，为了做到这一点，我们需要对构成定义2.8形式的数学对象的适当定义。合理的方法是收集类型、输入和输出，在顺序组合的情况下，消除从一个网络输入到另一个网络的类型、输入和输出，就像我们在定义2.2中对代理所做的那样。接下来，我们需要通过张量将量子运算与恒等映射结合起来。正如我们将在下面看到的，通过这种方式，我们已经恢复了大部分Defs。2.4和2.5。事实上，我们只需要仔细检查量子操作是否以正确的方式组合，但是，为此我们可以依靠上述Prop。两点十分命题2.10网络的语义是合成的，即2. N1）=<$N2）。第1类（20）<$N1<$N2）=<$N2）<$<$N1）（21）证据 假设我们有两个网络N1= |iAi（i1，i，o1，i）：Q1，i. E1，i<$σ1，N2= |iAi（i2，i，o2，i）：Q2，i. E2，i∈σ2，语义由下式给出：<$N）：Q→QJ。i→{（o，Los）}1i 1，ii1，i1 11（二十二）<$N）：Q→QJ。i→{（o，Los）}，与2i2，ii2，i2 22ΣL1：D（HI）→ D（HO）<$iρ1，i→L1，j（σ1<$iρ1，i）L<$111，j拉吉L2：D（HI）→ D（HO）<$iρ2，i→L2，j（σ2<$iρ2，i）L†.（二十三）2 22，jJ我们发现，o2，so 1，s（N）。（N）： Q→QJ. i →{（o，L. （LI）），，0 }（24）21 ii i ii211，s2，s其中，类型、经典输入和输出通过逐点应用等式中的规则（1），I是90诉Danos等人理论计算机科学电子笔记170（2007）73I2\O2上的恒等运算。量子诉Danos等人理论计算机科学电子笔记170（2007）7391i=1上述形式的运算将I=I1（I2\O2）中的状态<$iρ1，i<$iρ2，i映射到O=O2中的状态，在用σ1<$σ2张紧它们之后;另一方面，N2<$N1的语义由下式给出：<$N<$N）：Q →QJ. i→{（o，[L. （L）]os），（25）21 ii i ii21s其中os=o1，so2，s，量子操作与上面的I和O所以我们只需要检查一下，首先组成量子操作，然后限制它们与首先限制它们是一样的，然后作曲。然而，这是从普通模式的类似结果[2]得出的。对于并行合成，考虑N2= |nBi（i2，i，o2，i）：Q2，i. E2，i<$σ2in-语义如上。 我们发现，<$N）<$N）：Q→QJ。i→{（o，Lo1，s氧，硫），o ，o}，（26）12i i ii1公升2公升1，s2，s其中，类型、输入和输出通过取组成网络的类型、输入和输出的（不相交的）并集来找到。再一次，通过普通的类似结果，[2]我们发现，L）os=Lo1，s氧，硫因此，1 21 12上面的表达式等于<$N1 <$N2）。Q2.4纠缠语境在前一节中，网络N1和N2分别对形式为iρi的张量积状态进行操作，这是因为它们是由每个智能体提供的局部输入，这在Def中已经明确说明2.7虽然这在考虑孤立运行的网络时是明智的-在这种情况下，纠缠输入态被指定为准备-但它不太所以当网络只是复杂组成结构中的一个因素时。事实上，对于顺序合成，输入状态一般不再通过代理进行解纠缠，因为它部分地作为先前网络计算的输出而被馈送，并且不能保证该输出是产品状态。另一个微妙的区别在于，当组成网络时，各个代理的输入空间被合并。具体地说，当N 1单独运行时，每个代理提供本地输入ρ1，当N1单独运行时，每个代理提供本地输入ρ2。N2是单独运行的，合成网络N2<$N1的输入通常是不具有ρ1<$ρ2的形式。 另一种情况是，混合状态输入，因为它们的输入纠缠到一个比网络运行的系统更大的系统上的状态当然，这些都是纠缠态的典型表现，但我们要强调的是，在分布式网络的背景下，这些纠缠态会出现不同的情况。 的92诉Danos等人理论计算机科学电子笔记170（2007）73KKKKKK问题是，当只对纠缠态的一部分进行操作时，纠缠是否保持不变？我们在下面证明它是存在的，通过证明应用于存在于系统AC上的状态ρ的A-系统的a量子操作不触及该状态在C中的部分。上述情况中的每一种都可以以这种形式进行转换，因为A可以是与系统C所描述的一组其他代理纠缠在一起的若干代理的系统，以及仅与另一输入系统C纠缠在一起的一个代理的输入系统。量子操作本身被定义为将A上的状态映射到B上的状态，因为我们想考虑网络的输出空间与输入空间不同的命题2.11假设L是系统A到系统AB使得L：D（HA）−→ D（HB）：ρA−→ρB=ΣL k ρ A L†.（二十七）K那么，对于系统AC上的所有量子态ρAC，将L应用于ρAC的一半会导致：ρBC= Σ（LkIC）ρAC（L<$IC）（28）K证据首先注意，任何复矩阵都可以写成厄米特矩阵的线性组合，而厄米特矩阵又可以写成densitymatrices. 通过该脉冲位置的线性化，它遵循†给出了所有复矩阵Z都有L（Z） =LkZL的定理。写作ρAC=艾克尔|iA|jCk|一个小女孩|C我们发现Σ（C）C=C（C）C=C（C）C = C（|伊什托克|A.|吉尔|C）、ijkl=ijklΣ01 -02 -2016刘晓波（K（L k|伊什托克|AL†）|吉尔|C）、（二十九）=K证明了这个定理Q（LkIC）ρAC（L<$IC），这个证明虽然简单，但并不简单，而且有几个重要的结论。首先，它表明我们在SEC的声明。2.2网络是独立于时间表的事实是正确的。 事实上，智能体通过局域操作来转换共享纠缠态的部分，上述结果表明，任何顺序都会导致相同的多局域量子操作。接下来，当我们