Haskell实现的并行量子计算机中的软件事务存储模型

理论计算机科学电子笔记270（1）（2011）183-190www.elsevier.com/locate/entcs基于transmitted存储器Juliana Kaizer Vizzotto1ProgramadeP′os-GraduacaoemInform′aticaUniversidadeFederal de Santa Maria圣玛丽亚和r'eRauberDuBois2ProgramadeP′os-GraduacaoemInorm′aticaUivrsidadeCatolicdePelotas佩尔蒂摘要我们提出了一个在单个系综量子计算机中使用Haskell的软件事务存储器进行并行量子计算的模型。并行系综量子计算机除了具有量子并行性外，还具有一种经典的单指令多数据并行性。它通过使量子计算机并行工作来探索额外的加速，就像经典计算一样。整个状态是以这样的方式准备的：量子比特的子集处于代表通信量子计算机的混合状态，而处于纯状态的其他量子比特是每个量子计算机的适当参数寄存器。 从本质上讲，这种构造并行量子计算机状态的特殊方式与众所周知的多线程编程相适应。软件事务存储是一种很有前途的新的共享存储并行程序设计方法。函数式编程语言Haskell优雅地实现了并发通信的这种抽象。关键词：量子计算，并行量子计算，事务存储器1引言量子计算[3]（EQC）通常是通过使用NMR的某种方案来物理实现的。它本质上不同于传统的量子计算，只是因为它使用量子系统的许多副本（例如，液体溶液-例如每个分子潜在地是单个量子计算机），并且测量的结果是可观察的期望值，而不是随机本征值。单系综量子计算机中的并行量子计算[9]（PQC）1电子邮件地址：juvizzotto@gmail.com2电子邮件地址：dubois@atlas.ucpel.tche.br1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.01.017184J.K. Vizzotto，A.R.Du Bois/Electronic Notes in Theoretical Computer Science 270（1）（2011）183探索合奏，以获得额外的加速。除了使用叠加量子态所固有的量子并行性之外，通过使量子系统（分子）并行工作，如在经典计算中那样，还实现了一种经典的单重多数据并行性。在PQC中，整个状态是以这样的方式准备的：一个量子比特的子集处于混合状态，代表通信的量子计算机，而其他处于纯状态的量子比特是每个量子计算机的真参数寄存器作者已经证明，PQC可以为Grover和Shor等重要的量子算法提供额外的加速。特别是，无序数据库搜索可以大大加快我们已经注意到，这种构造PQC状态的特殊方式适合于众所周知的多线程编程。基本上，在多线程环境中，一个进程有许多执行线程，每个线程独立运行，并且可以共享一个公共内存区域。有趣的是，在计算上，生活在希尔伯特空间中的PQC量子态被解释为全局的。因此，PQC的所有量子计算机共享公共全局存储器区域。并行程序对同步机制的需求并不新鲜，文献中有许多替代方法，如锁和多线程。然而，一些作者[11，8，7]声称这些编程风格很难使用，并且很容易产生错误的程序软件事务存储是一种很有前途的新的共享存储并行程序设计方法。函数式编程语言Haskell优雅地实现了并发通信的这种抽象。这项工作是一个垫脚石的发展，一个高层次和优雅的方法来结构和项目并行量子算法。第二章量子计算机中的PQC [9]的思想是并行运行多个量子系统的副本，这些副本在系综中与经典计算一样，目标是实现并行运行任务的例如，通过并行运行几台相同的量子计算机，可以大大加快未排序的数据库搜索速度[4]。考虑具有N1= 2n1个分子的EQC量子计算机模型，使得每个分子都可以被操作和测量。 PQC计算机工作在 一种称为参数寄存器的状态，它被分为两部分：一部分具有n1个量子比特，称为n1-寄存器，另一部分具有n2个量子比特，称为n2-寄存器，n=n1+n2。在计算之前，参数寄存器处于混合状态，具有N1个成分。每个组成部分的特征在于n1寄存器的状态。 在一个给定的成分的n2寄存器是在其N2=2n2基本状态的叠加状态。系综的密度算符为：ρ=1NN1−1N2−1[N2−1c j1，j2 |j1，j2][c j1，j2 j1，j2|]1j1=0 j2=0j2=0J.K. Vizzotto，A.R.Du Bois/Electronic Notes in Theoretical Computer Science 270（1）（2011）183185在EQC中，有N1个组分和N1个分子。 每个分子都在 一异质态<$N2 −1c|j，j是N个com的叠加，j2=0推定的基础状态。j1，j212 2上述计算状态上的酉变换可以由下式表示：ρ→ρc=Uc ρU−1=1N1−1N2−1[N2−1c j，jU c|j1，j2][c j，jj1，j2|U †]cN1 j1=01 2j2=012cj2=0这种量子计算被定义为并行量子计算。事实上，它是N1台量子计算机并行工作。对于所有分子，计算Uc可以是相同的，但是数据库，由不同分子表示的数字，可以是不同的。在PQC中，测量值被视为平均期望值，并将在本工作的进一步版本中进行讨论。3 Haskell中的软件事务内存在[5]中，STM Haskell提出了一种新的基于软件事务内存的Haskell并发模型.在这个模型中，程序员定义了原子块，这些原子块相对于每个其他原子块以原子方式执行。STM Haskell提供了原子原语来定义原子块：原子地：：STM a→IO a原子原语将内存事务（STM a）作为参数，并原子地执行它。内存事务只有在没有其他事务修改其执行所依赖的内存时才被提交。如果存在对共享变量的并发访问，则事务将重新启动。原子块的执行必须保证[10]：• 原子性：原子块的结果对其他线程是一次性可见的• 隔离：一个原子块的执行不能被其他线程的执行所隔离。一个原子块的执行就好像它有自己的程序在内存事务中，程序可以读写事务变量。类型TVar a的变量是可以保存类型a的值的事务变量。STM Haskell提供了以下原语来读写事务变量：readTVar：：TVar a→STM awriteTVar：：TVar a→a→STM（）readTVar原语接受TVar作为参数，并返回一个STM操作，该操作在执行时返回TVar的当前值。writeTVar原语用于将新值写入TVar。STM动作可以使用Haskell中用于组合IO动作的do符号addTVar：：TVar Int→Int→STM（）186J.K. Vizzotto，A.R.Du Bois/Electronic Notes in Theoretical Computer Science 270（1）（2011）183addTvar tvar i=do{v←readTvar tvar;writeTVar tvar（v+i）}addTVar函数可用于读取新值，然后将其写入TVar。这两个动作可以通过使用原子原语原子地执行：IncTVar：：TVar Int→IO（）incTVar tvar=原子地（addTVar tvar1）在内存事务中，只能执行纯函数和STM操作。由于事务可以被中止并重新运行，类型系统保证在原子块内不能执行其他不可撤销的副作用（如IO操作）。STM Haskell还提供了一个retry：：STM（）原语，用于中止事务，以便从头开始重新启动：withdraw：：TVar Float→Float→STM（）withdraw tvar v=do{r←readTVar tvar;if（r=）：：（基a，基b）<$Vec a→（a→Vec b）→Vec bva>= f = λ b→sum [（va a）<$（f a b）|a←基础]返回仅将值提升为向量，并绑定，给定酉运算符（即，酉算子）表示为函数a→Vecb，给定Vec a，返回Vec b（也就是说，它指定如何将Vec a转化为Vec b）。 实际上，正如[12]中所解释的，由于我们可以构建向量的集合上的Basis约束，我们使用了一个稍微更一般的monad概念，称为Kleisli结构[1]或索引monad。4.2作为箭头的直觉上，密度矩阵可以被理解为状态向量的统计视角。在密度矩阵形式主义中，一个量子态过去是用矢量v来建模的，现在是用它的外积来建模的。类型Dens a=Vec（a，a）pureD：：BasisaVec a→Dens a pureDv=lin2vec（vv）lin2vec：：（a→Vec b）→Vec（a，b）lin2vec=uncurry函数pureD在其密度矩阵表示中嵌入状态向量。为了方便起见，我们将密度矩阵的参数去掉，使它看起来更像一个将密度矩阵映射到密度矩阵的运算称为超运算符：类型Super a b=（a，a）→Dens b上面的应用函数>=定义了超算子如何作用于矩阵。箭头的概念[6]扩展了核心lambda演算，其中有一种类型和三个常数满足九个定律。类型是A→B，表示接受类型A的值并返回类型B的值的计算，可能执行一些副作用。这三个常量是：，它将函数提升为一个没有边项的纯箭头;>>，它包含两个箭头;以及first，它将箭头扩展为作用于一对中的第一个分量，离开第二个分量不变正如与向量相关联的概率效应由于Basis约束而不是严格的单子一样，Super类型也不是严格的箭头，因为以下类型包括要求元素可比较的附加约束。我们在[12]中定义了索引箭头的概念，它允许约束。接下来，我们将Super类型的实例化显示为箭头。n：：（基b，基c）n（b→c）→超b c nf=fun2lin（λ（b1，b2）→（fb1，fb2））188J.K. Vizzotto，A.R.Du Bois/Electronic Notes in Theoretical Computer Science 270（1）（2011）183>>：：（Basis b，Basis c，Basis d）<$Super b c→Super cd→Super b d f>>g b=（f b>=g）第一个：：（Basis b，Basis c，Basis d）<$Super b c→Super（b，d）（c，d）f（（b1，d1），（b2，d2））=permute（（f（b1，b2））置换（return（d1，d2）其中置换v（（b1，b2），（d1，d2））=v（（b1，d1），（b2，d2））该函数通过将纯函数应用于向量及其对偶，从纯函数构造了一个超算子。箭头的复合只是使用4.1节中的绑定来复合两个超算子。 该函数首先将超算子f应用于第一个分量（及其对偶），并保持第二个分量不变。定义分别计算每个部分，然后排列结果以匹配所需的类型。4.3箭头的一种更好的表示法Paterson（2001）遵循Haskell我们只集中于解释我们在例子中使用的新形式。下面是一个简单的例子来说明符号：e1：：Super（Bool，a）（Bool，a）e1=proc（a，b）→dor←lin2superhadamardreturnA（r，b）do-notation只是在其主体中对动作进行排序。 函数returnA等价于一元函数return的箭头。这两个额外的关键字是：• 箭头抽象过程构造箭头而不是常规函数。• 箭头应用程序将表达式的值输入到箭头中。Paterson（2001）表明，上述符号足够通用，可以表达箭头计算，并实现了一个Haskell在上面的e1的情况下，转换到Haskell会产生以下代码：e2：：Super（Bool，a）（Bool，a）e2=first（lin2super hadamard）因此，使用Haskell中的箭头方法可以以高级别的方式操纵量子态。例如，在定义了正确的操作之后，隐形传态算法[2]可以编程如下：teleport：：Super（Bool，Bool，Bool）Bool teleport=proc（eprL，eprR，q）→do（m1，m2）←alice（eprL，q）qJ←bobj（eprR，m1，m2）return A−=s）}隐形传态是一种典型的分布式量子算法。远距传送的概念是在一个地方分解一个物体，在另一个地方制造一个完美的复制品事实上，量子隐形传态[2]可以通过经典的通信信道，通过先前共享的epr对传输未知的量子态。在文[12]中，我们用箭头和Patterson引入的符号表示了量子隐形传态我们把算法分解成两个独立的过程，alice和bob。除了使用箭头符号来表示超算子对特定量子位的作用外，我们还将测量纳入Alice的过程中alice：：Super（Bool，Bool）（Bool，Bool）alice=proc（eprL，q）→do（q1，e1）←（lin2super（controlled qnot））<$（q，eprL）q2←（lin2super hadamard）q1（（q3，e2），（m1，m2））←meas（q2，e1）（m1J，m2J）←trL（（q3，e2），（m1，m2））returnA（m1J，m2J）bob：：Super（Bool，Bool，Bool）Bool bob=proc（eprR，m1，m2）→do（m2J，e1）←（lin2super（controlled qnot））<$（m2，eprR）（m1J，e2）←（lin2super（controlled z））<$（m1，e1）qJ←trL<$（（m1J，m2J），e2）190J.K. Vizzotto，A.R.Du Bois/Electronic Notes in Theoretical Computer Science 270（1）（2011）183返回AqJ在定义了爱丽丝和鲍勃的过程之后，我们现在可以使用QST来编码隐形传态过程。我们的想法是按照第2节中的建议在QSt中安排状态。这样，我们就有了一个由Alice和Bob共享的量子态。QSt中的第一个量子位是标识符，表示状态是来自Alice还是Bob。6结论我们已经提出了一个模型，在一个单一的系综量子计算机使用Haskell的软件事务存储器的并行量子计算。我们希望这种方法能为我们提供一种简单而高级的方法来编写和开发并行量子算法。确认我们希望与AmrSabry和AntonioCarlosdaRoch a Costa的同事进行有趣的讨论，并就我们的工作提出反馈意见引用[1] Thorsten Altenkirch和Bernhard Reus。使用广义归纳类型的lambda项的一元表示。计算机科学与逻辑，1999年。[2] C. H. Bennett，G.巴拉德角克雷佩奥河Jozsa，A.Peres和W.伍特通过经典和EPR双通道传送Phys RevLett，第1895-1899页[3] David G. Cory，Amr F. Fahmy，and Timothy F.哈维尔利用核磁共振光谱学进行量子计算。Natl.Acad. Sci. USA，94：1634 - 1 6 3 9 ， 1 9 9 7 .[4] 洛夫·K格罗弗量子力学有助于大海捞针。物理修订信函，79（2）：325[5] 蒂姆·哈里斯，西蒙·马洛，西蒙·佩顿·琼斯，莫里斯·赫利希。可组合内存事务。在05年的PPoPPACMPress，2005.[6] 约翰·休斯。把单子推广到箭头。Science of Computer Programming，37：67[7] 西蒙·琼斯 2007年，美丽的并发[8] Edward A.李你 threads的问题。 Computer，39（5）：33[9] 桂绿龙和L.萧单系综量子计算机中的并行量子计算。A，69（5）：55[10] 西蒙 ·佩顿 ·琼斯 美丽 的并 发症 。Andy Oram 和Greg Wilson， 编辑 ，Beautiful Code， 第385-406页。O’Reilly,[11]拉维·拉杰瓦和詹姆斯·古德曼transmittance执行：迈向可靠的高性能多线程。IEEE Micro，23（6）：117[12] 朱 莉 安 娜 ·K Vizzotto ， Thorsten Altenkirch ， and Amr Sabry. 结 构 化 量 子 效 应 ： 超 算 符 如 箭 头 。Mathematical Structures in Computer Science，Special issue on Quantum Programming Languages，16：453