语义量子程序模型：经典输出流与非终止程序的随机输出（延伸摘要）

理论计算机科学电子笔记170（2007）165-184www.elsevier.com/locate/entcs具有经典输出流的（延伸摘要）Dominique UnruhInstitutfürAlgorithmenndKognitiveSystemme，UniversitüatKarlsruheAm Fasanengarten 5，76131 Karlsruhe，Germany摘要我们展示了如何建模的语义量子程序，使经典的输出在其执行过程中。也就是说，在我们的模型中，即使是非终止程序也可能有输出。该模型将程序解释为机器状态的测量过程，经典输出作为测量结果。这里给出的语义是完全抽象的，在这个意义上，两个程序在语义上是相等的，当且仅当它们在任何组合中给出相同的输出关键词：量子编程语言，指称语义，经典输出流。1介绍大多数（量子）算法接受（经典或量子）输入，计算，并最终给出（经典或量子）输出。然而，这种范式并没有捕捉到程序在终止之前输出数据的情况。然后，即使是一个非终止程序也可能有输出（可能是无限长的输出）。这种程序的一个例子是，枚举某个集合的对象对这种行为建模的一种可能方法是将程序建模为在量子态上操作的经典过程，从而产生随机过程（这种方法的示例可以在[3，2，8，7]中找到这样的语言1Email：unr u h@ira. 英国De1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.12.016166D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165然后可以通过给出经典输出的操作来增加，并且随机过程将在输出上引起概率分布。然而，这种混合方法存在缺点。由于量子力学的定律，存在原则上无法区分的量子态的不同概率分布。因此，两个程序可能具有不同的语义，尽管它们具有完全相同的可观察行为。这个问题由[6]解决，其中提出了量子编程语言的语义，该语言没有对量子数据上的经典随机过程进行建模，而是直接通过密度算子表示程序的状态，这是一种描述量子状态的概率混合的既定形式主义由于两个密度算子相等当且仅当集合是不可区分的，这就产生了完全抽象的语义，即两个程序具有相同的语义当且仅当它们在任何更大的上下文中表现出相同的行为。然而，这些语义没有建模流的经典输出的可能性我们遵循[6]改编的哲学，并为具有经典输出流的量子程序提供完全抽象的语义该模型的基本思想是将程序的执行视为对程序状态的物理测量过程这种测量过程以量子态作为输入（系统的初始状态），返回经典测量结果（程序执行期间的输出），并使系统处于新状态。这样的测量过程可以通过所建立的PMVM形式体系来描述（参见图1）。第1.1节）。当然，对于非终止程序，执行后状态的概念没有定义，因此这些程序将通过测量建模，而没有测量后状态，即所谓的POVM（参见。第1.1节）。我们将展示如何结合PMVM和POVM形式主义，以允许程序，有时终止，有时不。由于非终止程序可能有无数个可能的输出序列，这种情况稍微复杂一些。幸运的是，在[ 1 ]中提出的POVM和PMVM的建模（参见第1.1节）能够处理这种情况。这里介绍的最有趣的构造是循环。如果非终止程序可能有输出，那么将循环定义为最小定点的方法并不简单。因此，我们提出了另一种方法，其中循环的语义由一些直观公理唯一定义（见第7节）。在这个扩展的摘要中，我们给出了完整的形式定义，但省略了所有的证明。D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）1651671.1记法与量子力学形式请注意，这个量子力学形式主义的总结并不提供量子力学的介绍。它主要是为了说明本文中使用对于一个温和的介绍，见例如，[4]或[5]，以及[1]对于POVM/PMVM具有不可数结果的情况。由，我们表示自然数（包括0，>0或更少）、整数和复数。如果A是一个非空集，我们用A∞表示所有有限的集合，用A∞表示所有无限的集合，用Aseq表示A上所有有限或无限序列的集合。空字写为ε。给定两个序列a和b，ab表示级联（如果a是无穷大，ab=a）。当可数集A被视为可测空间时，它的所有子集都是可测的。当集合A∞、A∞或Aseq被视为可测空间时，其可测集合的集合是由{ω：α是ω的前缀}形式的集合生成的σ-代数，其中α∈A∞。纯量子态是具有单位范数的希尔伯特空间H的元素一个纯粹的状态被写入|好吧它的伴随词是|.对于某个集合X，形式为X的希尔伯特空间有一个特殊的基，即计算基{|i∈X}。对一个纯态的运算产生一个新的纯态，可以用幺正变换表示（如果运算不是满射的，一般用等距变换表示）。为了表示混合状态（即，状态，我们有不完全的信息），我们使用密度算子，这是对称的，积极的运营商在most1处的传输H上。一个多（至少可以是很多）的数据集|阿吉什概率pi表示为|阿吉吉|. 每个密度算子对应于至少一种混合物（总可能性≤1）。量子关于密度算符的过程由量子超算符表示密度算子上的完全正映射，不增加迹。保迹超算子我们称之为保概率。给定复合希尔伯特空间HA <$HB上的密度算子ρ，如果第一个子系统丢失，则部分迹trAρ是HB上的密度算子，它表示第二个子系统的密度算子的测量被建模为POVM或PMVM。 如果测量后系统的状态不确定，使用POVM。一个POVME，在一个系统Ω中具有一个POV对称性，H上的度量算子E（A）到Ω的任意可测子集A，s.t.iE（Ai）=E（iAi）对于任何可数的不相交集合（其中和收敛在弱算子拓扑中），E（A）= 0，且对所有的平均值，可扩的A<$Ω和密度算子ρ。如果对所有的密度算子，trE（A）ρ= trρ，我们称之为E概率保持。 给定一个状态ρ，168D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165trF（A）（ρ）trMfinn（A）（ρ）a∈A的度量的一个简单的例子是tr（E（A）ρ）。在测量后系统的状态被定义的情况我们必须使用PMVMS。APMVMFasignsasuperroperF（A）toeach可测量AΩ，s.t.A（A）=A（iAi）对于任何可数集合不交集的（其中和在强拓扑中收敛），F（n）= 0，并且对所有可测的A<$Ω和密度算子ρ，trF（A）（ρ）≤trρ. 如果对所有密度算子，trF（Ω）（ρ）= trρ，我们称F为概率密度.给定一个状态ρ，测量某个a∈A的概率由trF（A）（ρ）给出，在该条件下的结果状态为F（A）（ρ）。2模拟程序现在我们将讨论如何对程序的运行进行建模。我们首先从建模终止程序开始。这样的程序接受一个状态（机器的初始状态，由密度算子表示），给出一些（经典的）输出，并返回一个新的密度算子，即程序执行后机器的状态。这种行为可以很容易地由PMVM建模，PMVM将初始状态转化为结果状态，并将一系列输出作为其测量结果。然而，一个非终止程序不能这样建模，因为这样的程序没有结果状态。因此，它更好地建模为POVM，它采用初始状态并给出输出序列的概率分布，但不是应用后的状态我们现在可以对终止程序和非终止程序进行建模。然而，我们需要对程序进行建模，这些程序有时会终止，但并不总是终止。这样的程序我们表示为混合度量，我们定义如下：定义2.1（混合测量）设H是希尔伯特空间。结果为Ω的混合测量M在H上是一对（Mfin，Mnt），其中Mfin是H上的PMVM，Mnt是H上的POVM，结果为Ω。给定密度算子ρ，测量终止的概率（即，在应用测量后存在一个状态），并且测量的结果位于可测量集合AΩ中，由下式给出：[1][2][3][4][5][6][7][8][9][10][11][12][13][12][11][12][13][12][14][11][12][13][14][15][16][17][10][11][17][11][10][11] [12][17][11][19][10][11][12][14][11测量不终止并在A中有结果的概率是trMnt（A）ρ。我们通常将希尔伯特空间H视为隐式给定的。由于讨论测量是没有意义的，在测量中得到任何结果的概率大于1，我们通常必须限制D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165169混合测量是概率保持或减少，如以下定义所示定义2.2（概率保持）混合 测量 M是概率保持，如果对所有密度算子ρ，tr Mfin（A）（ρ）+ tr Mnt（A）ρ = tr ρ。我们称之为M概率约化，如果对于所有ρ，trM fin（A）（ρ）+tr M nt（A）ρ ≤ tr ρ。使用这种符号，我们现在可以对可能终止或可能不终止的程序进行建模，将它们视为产生程序经典输出的测量结果。定义2.3（程序）设可数字母表是固定的。让εde-注意到seq中的空单词。程序P是概率保持的混合测量，其值满足附加要求Pfinn.{x∈{\displaystyle x}{\displaystyle x}{当P只是概率约简时，我们称P为部分规划。这个定义中的额外要求是因为没有终止程序可以有无限长的输出。我们通过定义一些非常简单的程序来结束这一节首先，考虑程序noop，它什么也不做，立即终止由于noop在任何初始状态下的非终止概率为0，我们得到noopnt（A）= 0。由于输出总是ε（emptyineq），我们得到noopfin（A）=0forrε∈/A. 最后，国家不是修改，所以我们有noopfin（A）= 1，对于ε∈A（因为1是密度算子上的恒等式）。其次，考虑程序循环，它不会终止，也没有输出。按照与noop类似的推理，我们看到对于所有A，loopfin（A）=0，当且仅当ε∈A时，loopnt（A）=1，否则loopnt（A）= 0。最后，考虑一个简单的程序print xforx∈N，它输出x，然后终止。同样，与noop一样，我们有（print x）nt= 0。但是，由于x是输出，我们得到（print x）fin（A）= 1当且仅当x∈A。这当然，程序只能给出恒定的输出;在第6节中，我们将展示如何输出测量结果。2.一个程序的所有可能输出的集合。170D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165我们在下面收集这些例子定义2.4（初等程序）设x∈N。 然后，noop，loop，print x的定义为（对于所有可测量的A循环序列）.noopfinn（A）=1，ε∈A，0，ε∈/A，noopnt（A）= 0，.loopfinn（A）= 0，loopnt（A）=.1，ε∈A，0， ε∈/A，（print x）finn（A）=1，x∈A，0， x∈/A，（print x）nt（A）= 0.很容易看出，所有这些实际上都是程序（如Def. 2.3）。3初等变换除了上一节介绍的基本程序外，一种非常基本的量子程序是将幺正变换应用由于这样的应用程序不会终止，也不会给出输出，下面的定义很简单：定义3.1（程序状态的酉变换U是H上的等距变换3。则程序U被定义为：.乌芬（A）（ρ）=U ρU<$，ε∈A，0，ε∈/A，UNT（A）ρ= 0对于H上的所有密度算子ρ。这一概念是明确的，由以下内容表明引理3.2设U是等距变换。那么U是存在的，而且确实是一个 程序。大多数情况下，人们不想对整个H应用酉变换，而只对某些寄存器应用酉变换。3等距变换是比酉变换更一般的情形。特别是，它们不需要是满射的。大多数情况下，我们将D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165171只使用幺正，因此定义的名称172D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165为了能够定义这一点，我们将假设本节的其余部分，H具有以下结构：H=x∈VTx.这里V是变量名的列表，Tx是任意可数集（变量的类型）。所以H被分解成几个量子寄存器，名字为x∈V。典型的类型可能是位，由setbit：={ 0， 1}表示，布尔型，由bool：={true，false}表示，或整数，由setint：=表示。使用这种分解，我们可以定义酉变换在多个变量上的应用定义3.3（变量的酉变换）设x1，...，xn是与V成对不同的变量名。进一步设U是n的等距变换，Tx1·· ·Txn. 设Φ是H与H之间的典范酉同构（它只对系数进行重排），Tx1·· ·Txn ⊗x∈V\X其中X：={x1，.，xn}。然后U（x1，. ，xn）是酉变换Φ −1<$（U <$1）<$Φ（这里1是上的身份x∈V\XTXn）和U（X1，.，xn）是U（x1，.，xn）解译如定义3.1中的程序。如果n= 1，我们将U（x1）写成短U x1所以U（x1，.，xn）简单地意味着U被应用于对应于变量x1，.，xn.另一个非常重要的操作是对量子寄存器的（经典）赋值例如，在一个示例中，当我们写a：=5时，我们意味着在寄存器a中准备值5。这是很容易正式使用部分跟踪。考虑一个希尔伯特空间H分解为两个空间H=HA<$HB。然后准备状态|其中，HA中的φ n是将H上的密度算子ρ映射到|其中tr A是追踪空间H A的部分迹。| ⊗ tr A ρ, where tr Ais the partial tracetracing out the space HA.这可以很容易地推广到变量的赋值定义3.4（常数赋值）Le t x1，. ，xn是成对离散的。从V输入变量名，并且（a1，.，an）∈HA：=Tx1·· ·Txn，ni=1 Txi. LetHB：=x∈V\XTxn其中X：={x1，.，xn}，D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165173且Φ：H → HA→HB如定义3.3所示。此外，trA表示追踪HA的部分迹。我们定义了H上的超算子S，指定（a1，. ，an）到（x1，. ，xn）：S（ρ）：= Φ †。a，...，一个，.得双曲余切值.|阿格特尔Σ（Φρ <$| 1n1n AΦ）Φ对于H上的所有密度算子ρ。然后（x1，.，Xn）：=（a1，...，an）是程序P，定义为：.Pfinn（E）=Pnt（E）=0。我们也可以把（x）：=（a）写成xS，ε∈E，0， ε∈/E，x：= a的直观含义是将a赋给x，而语句（x1，.，Xn）：=（a1，... .，xn）是将ai分配给xi。然而，请注意，使用此定义，只有常量值的分配是可能的。在第6节中，我们展示了如何分配测量结果请注意，本节中的构造依赖于隐式或显式的定义变量名V和类型Tx。为了使这些明确，我们可以使用下面的约定：一个具有H=变量名V和类型Tx的程序被前缀为var x：Tx;x∈VTx，以及对于每个x∈V。我们为本节中的构造提供两个示例var n：int; n=5;这是希尔伯特空间H =上的一个程序，它总是终止，不输出，执行后的状态是|5⟩⟨5|（独立）初始状态）。对于第二个例子，令CNOT：=然后.Σ10 0 00 1 0 00 0 0 10 0 1 0上操作bool阿穆尔布尔var a：bool; var b：bool; var c：bool;CNOT（a，b）; CNOT（c，b）174D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165我我我是一个在希尔伯特空间H=boolboolbool上的程序。 它首先以第一位为条件，然后以第三位为条件，跳过第二位。4诚然，这些构造是非常基本的，它们主要用于提供一组最小的基本操作，以便能够在以下部分中使用与控制相关的构造。一个具有更丰富类型系统和作用域的变量概念将大大提高这里描述的概念的可用性，并将是有趣的未来工作。进一步注意，在这种语言中只有常量赋值是可能的，这似乎是非常限制然而，在第6节中，它展示了如何将测量结果分配给变量。4概率总和程序上最简单的运算是概率和。设P和Q是程序，且p∈[0， 1]，则P <$pQ表示以概率（1−p）运行P和以概率p运行Q得到的程序。很容易看出，下面的定义可以满足定义4.1（二进制概率和）设P和Q是程序（或部分程序），且p∈[0，1]。然后我们定义程序（部分程序）PpQ，（PpQ）fin：=（1−p）Pfin+pQfin，（P pQ）nt：=（1 − p）Pnt+ p Qnt。我们甚至可以很容易地将这个定义推广到任意数量的被加数：第四章. 2（Probabilist i csum）Let Ibeacoun tablesockett. LetPi（i∈I）是程序（部分程序），且pi∈[0， 1]（i∈I），其中ipi= 1。然后概率和是程序（部分程序）ipiPi，定义为.Pi芬Σ：=piPfin，.Pi我布雷恩特我Σ：=piPnt.我4在这个例子中，我们使用CNOT（a，b）和CNOT（c，b）的顺序组合。我们将在第5节中正式介绍这一点。D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165175P Q QP一个自然产生的问题是，概率和是否总是被定义的，特别是对于无限多个被加数。下面的引理肯定地回答了这个问题。4. 3我是一个可以接受的人。 若所有pi（i∈I）都是可积群，且i∈Ipi= 1，则i piPi存在，是唯一定义的，是一个程序。如果所有的P i都是部分程序，并且唯一定义为部分程序。Σi∈Ipi≤1，则ipiPi存在，示例：使用这个构造函数，以及来自preceding部分的程序print，我们可以制定一个程序，它输出一个随机位：打印0页1 打印1.25顺序组合可能在任何命令式编程语言中最重要的构造是顺序组合，即，程序的连续应用。为了实现这一目标，我们首先制定混合测量的组成。设P和Q是混合测量。QP（Q应用在P之后）的组合直观上意味首先，我们测量P，得到结果xP。然后，如果P终止，我们测量Q，得到结果xQ。这个实验的总体结果应该是（xP，xQ）或xP（取决于Q是否被应用）。这种直觉很容易给我们QP的以下性质，这些性质最终定义了QP（参见：定义2.1）：定义5.1（混合测量的顺序合成）让 P和Q是混合测量，结果分别以ΩP为单位。Ω Q则QP是混合测量，其结果在（ΩP× ΩQ）<$ΩP中满足以下等式，对于所有密度算子ρ和所有可测量的AP<$ΩP，AQ<$ΩQ：（QP）finn（A×A）（ρ）= Qfinn（A）。Pfinn（A）（ρ），tr（QP）nt（AP× AQ）ρ = tr Qnt（AQ）P fin（AP）（ρ），tr（QP）nt（AP）ρ = tr P nt（AP）ρ。下面的引理将这些性质称为定义：引理5.2设P和Q是混合测量，结果为ΩPresp. Ω Q(i) 如果QP存在，它由定义5.1唯一定义。176D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165(ii) 若Ω P和Ω Q可嵌入紧可度量空间，则复合QP存在.(iii) 如果Ω P= Ω Q= Ω，则组合QP存在。(iv) 如果P和Q是概率保持（减少）的，那么QP也是（如果存在）。乍一看，人们可能会认为这个定义已经给了我们程序的顺序组合。然而考虑下面的例子：让Ps输出s ∈N。 那么我们期望Pab和Pc与Pa和Pbc的组合相同的操作语义，即Pabc。然而，使用定义5.1，我们得到PcPab，它以概率1产生结果（ab，c）/=abc。类似地，PbcPa输出（a，bc）/=abc。这个问题可以通过将组合程序Pa;Pbc定义为应用组合混合测量PcPab的结果，然后“忘记”结果的结构来解决我们将（ab，c）映射到abc，并且更一般地将（x，y）映射到级联xy。为了将这个思想形式化，我们首先必须定义将函数f应用于混合测量P的结果意味着什么。请注意，Pfin（A）、Pnt（A）描述了仅限于以下情况的测量行为：结果x位于A中。则Pfin（f−1（A）），Pnt（f−1（A））描述了仅限于f（x）∈A的情况下的测量的可测性。考虑这一点，人们很容易理解以下定义：定义5.3（混合测量的函数应用）设希望我能和我在一起。Letfurtherf：Ω→Ωbe可测量的函数。 然后我们定义混合测量f（P），输出系数（ΩΩ）通过设置（对于所有可用的设备AΩΩ）：.芬芬。− 1Σf（P）（A）：=Pf （A），. f（P）nnt（A）：= Pnt. f−1（A）如果f有一个包含但不等于Ω的域，我们通过设置f（P）来稍微推广定义：|Ω（P）。下面的引理是显而易见的：引理5.4设P是结果为Ω的混合测度。 让进一步f：Ω→Ω是一个可测量的函数。(i) 混合测量f（P）存在，并且由定义5.3唯一定义。(ii) 如果P是概率保持（减少）的，那么f（P）也是。我们现在有办法制定.D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165177定义5.5（程序的顺序组合）令matten是一个函数，它接受一个在matten上的（有限或无限）序列，并返回序列元素的连接。5然后，我们定义两个程序（部分程序）的序列组合P;Q，P;Q：=衰减（QP），其中，在右手侧，P和Q被视为混合测量。我们现在能够制定简单的程序，如打印a;打印b（输出ab），print a; loop（输出a，但不终止），然而，两个问题自然出现：P;Q实际上是一个程序吗？它的运算符是否如人们所期望的那样是下面的引理肯定地回答了这些问题，从而证明了定义5.5。引理5.6设P，Q，R是程序（部分程序）. 然后(i) P;Q存在，唯一定义，是一个程序（部分程序）。(ii) 它是{P;Q};R=P;{Q;R}。6(iii) 它是P;noop = noop;P = P。使用组合的概念，我们现在可以形式化这里提出的语义是完全抽象的：引理5.7设P/= Q是程序。然后有程序S，T和一个可测的输出集A，S. t。S;P;T或S;Q;T在A中有输出的概率对于任何初始状态ρ是不同的。形式上：tr（S;P;T）fin（A）（ρ）+tr（S;P;T）nt（A）ρf = tr（S;Q;T）fin（A）（ρ）+tr（S;Q;T）nt（A）ρ。[5]在这个定义中，我们只在（seq）2上 使 用 atten。然而，在定义7.1中，我们将需要对（seq）seq应用atten。6注意，为了对程序进行分组，我们使用花括号而不是圆括号，这在许多编程语言（如C，Java等）中很常见。[7]形式上，要声明我们的语义是完全抽象的，需要与操作语义进行比较。然而，引理表明，相对于一个合理的概念，可观察的行为的语义确实是完全抽象的。178D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165B）+6分支程序如果没有分支的可能性，很难制定有趣的程序代码。我们将首先讨论分支程序最简单的构造函数，if-语句，然后讨论更一般的构造函数，switch-语句。假设B是具有两个可能结果的PMVM：真和假，表示对程序状态的布尔测试（例如，测量两个寄存器，并返回它们是否相等）。 那么程序“if（B）PelseQ“有以下直观表示：首先，我们应用测量值B，然后，如果结果为真，我们运行P，否则运行Q。“if（B）PelseQ“的输出分别是P或Q的输出。使用定义2.1中描述的语义，我们可以很容易地看到，这种行为是由以下内容捕获的：定义6.1（使用if分支）设B是一个概率保持（减少）PMVM，结果为{true，false}。设P和Q是程序（部分程序）。然后R：=if（B）P elseQ是满足（对于所有可测的Aseq和所有密度算子ρ）的程序（部分程序）：Rfinn（A）（ρ）= Pfinn（A）。（真）（ρQfinn（A））。B（false）（ρ）tr Rnt（A）ρ = tr Pnt（A）B（true）（ρ）+ tr Qnt（A）B（false）（ρ）另外“if（B）P“代表“if（B）P else noop“。这一定义得到以下方面的支持引理6.2如果P和Q是程序（部分程序），B是结果为{ true，false }的概率保持（约简）PMVM，则“if（B）P else Q“和“if（B）P“存在，是唯一定义的，并且是程序（部分程序）。这个引理可以很容易地从更一般的引理6.4推导出来。作为一个例子，我们制定了一个小程序，它将量子位设置为0并输出其先前测量的内容，仅使用测量和酉运算：var a：bit;if（a=0）print 0 else{NOT a; print 1}D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165179）=的这里NOT表示位-nip，并且a=0是PMVM测量a并且当且仅当结果为0时才产生真在6.1节中介绍了初等检验（如a=0）的形式表示法。一个更一般的结构是switch语句，它把if作为一个特例. 在本节的后面，我们将看到它的额外能力有助于制定量子程序。考虑一个结果在可数集C中的PMVMM，以及一族由c∈C索引的规划P（c）。然后我们可以解释程序开关（M为c）P（c）来描述下面的实验：首先，我们使用M测量程序令c∈C表示该测量的结果然后我们执行P（c）。与定义6.1类似，我们得到定义6.3（使用开关的分支）设M是一个概率约简（约简）PMVM，其结果在可数集合C中。进一步设每个P（c）（c∈C）是一个程序（部分程序）.那么程序（部分程序）R：=switch（M as c）P（c）被定义为满足所有可测的A_n_seq和所有密度算子ρ：Rfinn（A）（ρπ. P（c）最小值。M（{c}）（ρ）c ∈C。ΣtrRnt（A）ρ= trP（c）ntM（{c}）（ρ）c∈C在这些方程中使用的收敛概念是弱收敛。8引理6.4在定义6.3的条件下，以下成立：(i) 如果所有P（c）都是程序（部分程序），B是概率保持（减少），则“switch（M as c）P（c）“是程序（部分程序）。(ii) 如果B的结果为{ true， false}，则：switch（M as b）P（b）=if（M）P（true）else P（false）读者现在可能会问，我们为什么需要这样一个switch语句，因为一个无限分支可以用if语句实现，而一个无限分支并不真正反映实际编程中的可能性。然而，下面的例子可能会显示使用switch语句作为指定程序行为的工具。在定义2.4中，我们引入了程序print x，它输出常量字x。在许多情况下，这是不够的，因为人们可能希望8由于和是对称算子的递增范数有界序列，强、弱和超弱收敛是一致的。180D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165以简单地输出测量结果。这可以很容易地制定只使用开关和打印。假设M是一个结果在A中的PMVM，并且f：A→N为结果分配标签。然后下面的程序测量M并输出结果：switch（M as x）print f（x）同样，定义3.4中的常数值赋值也可以扩展到测量结果的赋值：switch（M as x）a：= x将测量M的结果赋给变量a。为了便于阅读程序代码，我们通常会写较短的P（M），而不是不太方便的开关（M as c）P（c）。所以刚才给出的程序将得到更直观的形式print f（M）和a：= M.然而，请注意，当使用这种速记符号时，必须确保没有歧义。例如，在一个示例中，必须记住，所以P（M，N）可以是switch（M as m）switch（N as n）P（m，n）或switch（N as n）switch（M as m）P（m，n）它们只有在M和N对易时才相同所以如果有疑问，就显式地写switch。同样，像a：=f（b）这样的程序可以读作switch（f（b）as x）a：=x（测量f（b）并将结果分配给a）或switch（b as x）a：=x（测量b并将f（b）分配给a）。我们的惯例是假定后一种情况。6.1基本测试为了能够使用上面的if语句，我们仍然需要一些方法来指定基本测试。在前面的部分中，我们只是假设一些PMVM具有布尔结果，这里我们将介绍一种如何指定这些结果的方法。类似于酉变换的情况，我们可以定义变量函数的测量：给定一些变量x1，. ， xn和函数f关于这些变量的类型，我们定义f（x1，... ，xn）为测量f（xi，.，xn）而不测量x1，..，xn（例如，测量x1···xnD. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165181M可以测量x 1的奇偶性，xn而不执行完整的测量）。 通过这样的测量，获得测量结果m意味着将状态投影到状态的子空间Hm上，其中f（x1，...，xn）=m。我们将其定义为：定义6.5（变量的基本测量）设x1，.，xn是V中两两不同的变量名，M是可数集. 进一步证明f：T×1×· · ·×T×n→Ve是一个函数.则对于m∈M，设Bm是H=Hx∈VTxsatisfyingg的计算基的所有元素e的集合：e=x∈V|vx{\displaystyle v x}{\displaystylevx}{\displaystyle v x}{\displaystylev}{\d i s p l a y s t y l e . ，v×n）=m。然后我们可以定义Hm为Bm生成的H的子空间，并且Pm是Hm上的正交投影。最后，这定义了PMVMf（x1，. ，xn）：f（x1，.，xn）（A）（ρ）：=Σm∈APm ρP<$对任意密度算子ρ∈ H和任意A∈M.下面的引理陈述了上述构造的良定性引理6.6使用定义6.5的符号，如果变量x1，.，xn是两两相异的，f（x1，.，xn）是结果为M的概率保持PMVM。在M={true，false}的情况下，上述构造适合与if语句。我们举一个例子：var a：bit; var b：bit;a：=0; b：=0;H2a; H2b;if（a=b）NOT a;这里H2表示一个量子比特上的阿达玛变换，而不是比特-量子比特。如果测试a=b失败，则a和b纠缠为具有相反的值。否则，它们会纠缠在一起，得到相同的值，但a会被删除，所以在if语句之后，它们也有相反的值所以上面的例子生成了一个EPR对。当然，这种PMVM也可以与交换机结合使用。例如，var i：int; switch（i as c）{case（i*i=4）：print“X”;}182D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165和var i：int;switch（i*i as c）{case（i=4）：print“X”;}是不同的程序。第一个完全测量i，第二个直接测量i的平方，即，忽略该符号，因此，例如，i在2和-2之间叠加，这个叠加不会被破坏。和第三节一样，这里给出的基本测量的符号只是初步的。今后的工作将是发展更强大的概念。7环在这个阐述中，仍然缺少一个控制结构，没有它几乎不能编写任何有用的程序：循环。假设给出了程序P和概率保持PMVMB，其结果为{真，假}（参见图1）。定义6.1）。然后，程序while（B）P应直观地表示以下实验：重复测量B。当B为真时，应用P。当B为假时，停止。总输出将是所有P调用的结果的串联。为了得到上述while程序的正式定义，让我们首先考虑中间情况，其中循环的结果不是P的输出的级联，而是这些输出的可能无限列表。也就是说，设R表示以下实验：重复测量B。当B为真时，应用P。当B为假时，停止。总输出应该是P的所有调用的结果的（有限或无限）序列。事实证明，用算子的和与积来描述R的直观定义中的无穷过程是相当困难的（就像我们在定义5.1和6.3中所做的那样），因为没有收敛的直观概念会在下面的地方产生意义：9如果（B）{P;如果（B）{P;··· if（B）{“我的天，n次loop}··· }}=while（B）P[9]事实上，在部分程序集上存在度量，使得上面的语句是有意义的，等价于定义7.1，甚至允许定义while（B）P，其中B和P只是概率减少。然而，我们认为这些指标不能像下面的公理方法那样容易地被证明，因此（可能）更自然的）公理化方法。D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165183i=1（二）（另一种常见的方法是将R定义为X<$→如果（B）{P;X}的最低定点。然而，当在混合测量上使用自然算子理论排序[10]当然，可能还有其他的顺序可以用来定义具有经典输出的程序的循环我们将尝试另一种方法，并假设一些公理，这些公理对R成立，然后将证明这些公理确实定义了R。首先，观察到以下情况中的一种（且只有一种）必然会发生：(i) 循环在n≥0次调用P后终止。(ii) P的第n次调用不会终止（n≥1）.(iii) 每次调用P都会终止，但B总是返回true（因此循环也不会终止）。请注意，R终止的唯一情况是第一种情况。因此，我们至少可以写下，我们对R_f_n的期望：对于任何n≥0，任何初始状态ρ，以及所有可测的A_i_n_seq，它成立n.ΣRfinn（A1×···×An）（ρ）= B（false）<$ Pfinn（Ai）<$B（true）（ρ）。i=1这里nXi表示组成Xn1.类似地，R没有终止，但只有有限个输出的情况由情况ii覆盖，我们可以形式化如下：trRnt（A1× ··· ×An）ρ.trPnt=（An）B（true）n−1。i=1P芬Σ（Ai）AB（true）（ρ），n≥10，n = 0。最后一种情况比较困难。为了接近这种情况，我们首先注意到，通过要求R是概率保持的（这似乎是一件明智的事情，因为P和B都是），我们得到trRnt.（seq）∞∞ρ = 1− tr Rfinn。seqp）−tr Rnt.（seq）ρ。（一）现在考虑以下事件：B总是产生真（即，循环运行无限次迭代），在前n次迭代中，P在[10]自然算符理论的阶由下式给出：A≥B，如果A-B是混合测度（所有混合测度都是正的）。问题在于最小混合测量0和程序循环之间存在差异。两者都是方程的解X=if（B）{P;X}，但loop是我们要找的定点，而0是最小的184D. Unruh/Electronic Notes in Theoretical Computer Science 170（2007）165一个.