FJQuantum: 一种基于Featherweight Java的量子面向对象语言

可在www.sciencedirect.com在线获取理论计算机科学电子笔记324（2016）67-77www.elsevier.com/locate/entcsFJQuantum一种量子面向对象语言塞缪尔·S.费托萨1号 朱莉安娜·K维佐托2 爱德华多·K Piveta3圣玛丽亚巴西圣玛丽亚安德烈河杜波依斯4计算机系- CDTec巴西联邦摘要已经提出了几种语言和库来处理量子程序，通常考虑命令式和函数式范式。在本文中，我们讨论了FJQuantum语言的应用，这是一种基于Featherweight Java的面向对象语言，用于开发处理量子数据的程序 和业务。保留字：编程语言，量子计算。1引言量子计算是一个研究领域，研究考虑物理世界量子性质的计算的各个方面。与传统计算机不同，量子计算机呈现出叠加和纠缠等特性，这使得量子计算机能够同时考虑和操纵比特的组合，与传统计算相比，能够实现更快的量子信息处理[21]。虽然没有通用的量子计算机，但有几项工作[15，29，13，14，27，18，7]是关于处理量子信息的不同方法的。1电子邮件地址：sfeitosa@inf.ufsm.br2电子邮件地址：juvizzotto@inf.ufsm.br3电子邮件地址：piveta@inf.ufsm.br4电子邮件地址：dubois@inf.ufpel.edu.brhttp://dx.doi.org/10.1016/j.entcs.2016.09.0071571-0661/© 2016作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。68S.S. Feitosa等人/理论计算机科学电子笔记324（2016）67量子计算中一个具有挑战性的研究领域是设计高级量子编程语言[17，22，23，6，25，3，28，32]，适用于描述和推理量子算法，并提供工具来理解量子计算一般如何工作。在这种情况下，这项工作讨论了FJQuantum语言的实现，显示了一组处理量子计算概念的源代码示例，利用面向对象的范式。FJQuantum语言是Featherweight Java（FJ）[16]的扩展，FJ是一种小型演算，为Java语言的主要方面提供了形式化的语义。因此，FJQuantum提供了FJ的所有功能，通过一元方法添加了几个特性来模拟量子行为。选择FJ作为这个项目的基础是因为Java这项工作遵循了已经使用Monad进行量子计算的其他建议[30，32]，以及QJava库[8]，它提供了使用闭包在Java中模拟量子计算的机制。在这里，我们探索了用FJQuantum语言编写代码的能力，展示了如何通过其新结构来建模一些量子计算方面2量子计算经典计算中的基本信息单位是传统的位，它代表经典的二进制物理系统，只能代表两种状态（真或假，0或1）。每个信息都被描述为比特的组合。在量子计算中，基本的信息单位被称为量子比特或量子位。如果与比特相比，量子比特呈现出本质的不同，因为它不限于经典比特的基本状态，它可以同时有效地处于两种状态（0和1）[21]。一些研究人员已经研究了处理能够提供量子特性的然而，在微观尺度上对元素进行物理操纵仍然存在许多挑战。量子计算理论在数学上将量子比特定义为矢量5|0 + β| 1 ⟩ | 1 ⟩其中，每个位置存储概率幅度α和β，表示其每个基本状态。概率幅被表示为复数，使得|α|2个以上|β|2 = 1。直觉上，人们可以想象一个量子位是0、1或两种状态同时发生，具有决定每个纯态概率的数值系数。任何其他具有不同α和β值的状态都表示量子叠加：|0次|1美元。这些叠加态为量子计算提供了[5]狄拉克的笔记。S.S. Feitosa等人/理论计算机科学电子笔记324（2016）6769一种叫做量子并行性的特性本质上，由于状态叠加，量子位可以同时呈现0和1的值。 此属性的量子算法，它可以获得一个指数加速比（理论上），考虑到允许并行处理几种可能性的特性。可以检查经典位以确定其当前值（0或1），这就是经典计算机在处理内存内容时的每时每刻所发生的事情。在量子比特的情况下，不可能在不干扰系统的情况下可视化它们的值以确定它们的当前状态（振幅α和β）。读取量子状态执行测量操作。在量子计算中，可以执行两种形式的操作：测量操作和酉变换。测量操作与从量子态提取信息的方式有关酉变换是指将当前量子态转换为另一个量子态的操作，类似于我们在经典计算中应用函数时的操作量子计算与经典计算不同，因为它通常是概率性的，所以测量操作在量子态的概率幅度上工作当测量被执行时，概率幅坍缩，并且仅返回它们的基本状态之一，如|0位数|1美元。换句话说，在测量之后，量子比特保持在已知状态，并且概率幅度被破坏。测量操作通常在量子算法的整个处理之后执行以获得信息类似于经典系统中处理信息的方式，量子计算的算法被设计为一系列酉变换，也称为量子门[21]。应用于量子位的这些门修改它们的初始值，将它们转换为所需的输出。第三章FJQuantum语言FJQuantum是一种面向对象的语言，作为Feather- weight Java（FJ）[16]的扩展开发，增加了几个结构，以允许开发具有通过一元层处理量子数据和操作的功能的程序。这种语言旨在形式化以前的工作[8]，考虑在Java语言中使用量子单子。FJ引入了一个轻量级的Java版本，为它的核心部分提供了一个形式化的形式，除了提供Java70S.S. Feitosa等人/理论计算机科学电子笔记324（2016）6722属性访问、强制转换和变量。考虑到量子计算的模拟涉及复数上的数学运算，并且还需要一系列控制机制，我们对FJ进行了几次扩展，主要目的是实现量子一元层。这些扩展包括：• 处理基本类型（布尔和复数）的特性。• 复数的数学运算• 条件控制结构。• 函数元组作为基元类型。Monad在量子计算中的使用已经在一些作品中进行了探索[20，30，33，32]，通常应用于函数语言。Calegaro和Vizzotto [8]使用了一种不同的方法，其中通过使用闭包将monad的概念应用于Java。闭包允许使用匿名函数（或lambda表达式），我们还将它们作为FJ的扩展添加，适应了Bellia和Occhiuto [5]的提议，这与Java实现略有不同使用这种方法是为了简单。由于量子比特的非确定性，量子比特的建模可以被认为是一种侧面效应。更具体地说，量子比特可以被建模为一种单子[20]。这个单子背后的想法是建立量子态空间，在数学上由一个复数向量表示，该向量包含量子比特的概率幅度，使状态能够通过量子门进行转换，量子门表示为酉矩阵，可以通过绑定一元算子应用[12]。为了使FJQuantum语言能够处理量子计算概念，我们提出了几种语法结构，每一种都有特定的目的，例如：创建量子态的功能，通过标量积运算符处理概率幅，使用一元和运算符处理叠加，以及通过绑定一元运算符创建负责转换量子态的函数的可能性为了允许量子态的创建，有一元运算符mreturn，它被用作作用于基态的构造函数。基态可以从布尔值或布尔元组构建，如我们在下面的示例中所看到的1mreturnfalse//创建的状态|0⟩2mreturntrue// 创建 的 状态|1⟩3mreturn{false，false}// 创建 的状态|00⟩4mreturn{false，true}//创建的状态|01⟩作为一种能够操纵概率幅和创建叠加态的方法，我们创建了标量积$n+和一元和mplus。下面的代码展示了叠加态的构造。1ComplexHalf$*mreturnfalsemplusComplexMHalf$*mreturntrue在上面的示例中，关键字ComplexHalf表示复数1而关键字ComplexMHalf表示number-n1。目前，√S.S. Feitosa等人/理论计算机科学电子笔记324（2016）6771√上述代码中的状态定义了叠加态中的量子态|0 ⟩−| 1美元。下2部分的例子显示了这些算子在Hadamard方法中的使用在用必要的工具准备好语言来创建量子态并处理其概率幅之后，可以定义绑定运算符，在FJQuantum中语法表示为>>=，它负责对量子态进行变换。量子变换可以被看作是量子比特上的量子门应用，类似于经典计算中的信息处理下一个示例说明如何使用此运算符。1（mreturnfalse）>>=2qop。hadamard（）>>=3qop.not（）>>=4qop。getString（）;在这段代码中，我们可以看到hadamard在状态上的应用|0，然后对第一次处理的结果应用not运算符，然后在处理not之后再次应用hadamard。除了FJQuantum的定义之外，我们还开发了一个解释器，旨在测试规则并编写量子算法。解释器是用Haskell开发的，它实现了词法分析器、语法分析器、语义和类型系统。4例本节介绍了FJQuantum程序的一些示例首先，我们展示了一个实现一系列通用可逆量子门的类。行（2）示出了表示经典算子的量子版本的not方法，其应用于一个量子比特。线（11）示出了哈达玛方法，其表示负责将量子比特从基本状态转换为状态叠加的算子。第（21）行显示了表示条件not的controlledNot方法。1类QOp延伸对象{2（布尔）->Vec）public void run（）{3返回（布尔）（i）->4如果（i==（false）{5mreturn真正6}7其他8mreturn虚假9};10}11（布尔）->Vec boolean >）public void run（）{12返回（布尔）b）->13如果（b== （false）{14（ComplexHalf$*mreturnfalse）mplus15（ComplexHalf$*mreturntrue）16}其他17（ComplexHalf$*mreturnfalse）mplus18（复杂度MHalf$*mreturntrue）19};20}21（{boolean， boolean}-> Vec {boolean， boolean}>）22public void run（）{23返回（{ boolean， boolean }b）->24如果（b.1==true）{72S.S. Feitosa等人/理论计算机科学电子笔记324（2016）6725如果（b.2==true）{26mreturn{true，false}27}其他28mreturn{true，true}29}30}其他31mreturn {b.1，b.2}32};33}34}在Hadamard方法中，强调叠加态的创建，在第（14）行和第（17）行，我们可以注意到mplus和标量积运算符的使用，解释了在建议的语言中创建这些运算符的原因。在controlledNot方法的情况下，我们可以看到语言在多个量子位上执行操作。重要的是要注意操作符的创建方式，返回一个lambda表达式，允许使用>>=组合操作符，类似于函数式语言。下一个示例显示了具有复杂操作的代码，旨在对具有多个量子位的初始状态执行转换，考虑到先前定义的类。1类QExec延伸对象{2//构造函数和其他方法34{ boolean， boolean， boolean } >public void run（） {5返回letqop=新QOp（）， 单 位 ：6（{ boolean， boolean， boolean }state）->7（（qop. hadamard（））。invoke（state.3））>>=8（布尔）b）->9（（qop. controlledNot（））。 invoke（{state. 1，state.2}））>>=10（{boolean，boolean} tm）->11（（qop. hadamard（））。（b）（a）（b）（c）12（booleanba）->mreturn{tm. 1，tm. 2，ba};13}14{ boolean， boolean， boolean }>15public void run（{boolean， boolean， boolean}nums）{16返回nnwQState{boolean，boolean，boolean}>（ini）17. transfor m（这是）publicvoidrun（）;18}19}2021个 新QExec（）. return（{true，true}）;这个例子展示了一种在量子态上应用部分变换的方法，以及如何通过第（7）行中的绑定运算符组合运算(9)（11）. composedOperation方法作用于具有三个量子位的量子态，并依次执行操作符hadamard到第三个量子位，操作符controlledNot到第一个和第二个，并再次将hadamard应用于第一个量子位，最终返回算法的结果。方法exec显示了类处理的入口点4.1 Deutsch算法Deutsch算法是最简单的例子，展示了量子并行的力量。它的第一个版本是由DavidDeutsch提出的[10]，S.S. Feitosa等人/理论计算机科学电子笔记324（2016）6773除了理查德·费曼的工作[11]，他们还推出了量子计算领域[19]。该算法的目的是确定布尔函数是平衡的还是常数。如果f（0）=f（1），则函数是常数，否则是平衡的。在经典算法中，为了解决这个问题，需要对函数f求值两次，即f（0）和f（1），然后比较结果[31]。使用量子方法，只需一次验证就可以解决问题，与使用叠加原理的经典版本相比，只需一半的时间[19]，它允许同时评估两个条目对于该算法的量子版本，首先需要构建函数f的量子版本，它表示对f执行相同计算的酉变换Uf。所有的量子计算都必须是可逆的，因此我们需要使用两个量子位来建模函数Uf，包裹函数f，正如我们在下一个表达式中看到的那样(1)Uf|X轴|y = |X轴|yf（x）下面的代码对第（5）行之间的一个名为blackbox的方法进行建模，(13)，它表示Uf函数，使用FJQuantum编写。1classsQExecTextendsObject>extendsObject{2Vec T状态;3//构造函数和其他方法45（{ boolean， boolean}->Vec { boolean， boolean } >）blackbox（（ boolean->boolean）（f）6返回（{ boolean， boolean}国家）->7if（state.2==（f）. public voidrun（）{8mreturn {state.1，false}9}10其他11mreturn {state .1，true}12};13}14}此方法接收一个闭包作为参数，表示经典函数f，并返回表示酉变换Uf的另一个闭包。 它-打开一个闭包以允许使用bind运算符。我们可以注意到使用两个量子位，由两个布尔值的元组表示考虑到之前在黑盒方法中建模的酉变换Uf，我们可以遵循关于该算法的量子电路的解释，如图1所示。|0⟩|1⟩Fig. 1. Deutsch算法的量子电路。这个电路的第一步是创建量子态，其中第一个量子位从纯值开始|第二个值为|1美元。使用FJQuantum语法，我们编写mreturn{false，true}。HUfHH74S.S. Feitosa等人/理论计算机科学电子笔记324（2016）6722在创建量子基本态之后，诀窍是在两个量子比特上应用哈达玛门，以创建叠加态。为了完成这个任务，我们创建了hadtb方法，它将之前定义的hadamard方法应用于顶部和底部量子位，正如我们在下一个代码示例中看到的1classsQExecTextendsObject>extendsObject{2Vec T >state;3//构造函数和其他方法4（{boolean， boolean}-> Vec {boolean， boolean}>）hadtb（） {5返回letqop=新QOp（）， 单 位 ：6（{ boolean， boolean }国家）->7（（qop. hadamard（））。invoke（state.1））>>=8（布尔）ta）->9（（qop. hadamard（））。invoke（state.2））>>=10（布尔）}-> mreturn {ta，ba};11}12}（二）处理方法hadtb的结果在数学上表示为：1|2 - 3 - 4 - 5 -| 00 ⟩− |01分彩|10⟩−|（11分）|11 ⟩)国|+++|- ε表示的状态叠加|0次|1例患者，实际上，如下面的等式所示：1 1（三）|2016 - 02 - 22 01：02：02（|0人以上|（1）e| 2016 -02 - 2200：00：00（|0 ⟩ − |1个月）一旦量子态处于叠加态，我们就可以应用我们的黑盒功能下一个表达式显示了处理Uf后的量子态输入的函数|0次|1美元。Uf|X轴|0= |X轴|f（x）（四）Uf|X轴|1 = |X轴|1 f（x）考虑这些方程，为了处理叠加上的Uf函数，国家，我们有以下结果。Uf|X轴|− 1 =1|1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |0 ⟩ − |f（x）= 0（五）1Uf|X轴|-=|1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |1 ⟩−|（x）= 0，则f（x）= 1S.S. Feitosa等人/理论计算机科学电子笔记324（2016）6775下一个表达式表示量子变换以确定这个算法的结果。（六）Uf|X轴|− f=（−1）f（x）|X轴|−⟩然后，我们可以看到下面的量子变换ap的解释折叠术（七）Uf|公司简介|-=⎧⎪⎨|公司简介|（1）如果f（0）=f（1）⎪⎩|−⟩|（1）如果f（0） 为零，则为零。76S.S. Feitosa等人/理论计算机科学电子笔记324（2016）67最后，我们在第一个量子比特上应用hadamard函数（并应用测量），看看函数是常数还是平衡的[31]。deutsch方法包含该算法的整个处理过程1classsQExecTextendsObject>extendsObject{2Vec T >state;3//构造函数和其他方法4Vec public booleanalert（）{5返回letqop=新QOp（）， 单 位 ：6(((这个状态）>>=7这个hadtb（））>>=8这个blackbox（f））>>=9（{ boolean， boolean }tb）->10mreturn{（qop. hadamard（））。invoke（tb. 1）），tb. 2};11}12}（八）然后，结果以下面的形式呈现。|− f如果f（0）= f（1）（常数）|−⟩ if f (0)= f(1)(constant)|f（0）|−⟩ if f (0)f（1）（平衡）给出的例子展示了如何利用面向对象的范式在FJ Quantum中表达量子算法，并演示了Monadic量子层如何适合原始FJ。5相关工作量子编程语言是一个重要的工具，工作和形式化的原因量子算法。出于这个原因，尽管没有量子硬件，但仍然存在对语义模型和量子编程语言的描述。量子语言通常是使用命令或函数范式提出的。第一个量子编程语言是考虑到强制范式而开发的，由Knill [17]提出。Omer[22]、Sanders和Zuliani [23]以及Bettelli等人提出了更完整的编程语言”[6]除此之外。考虑到功能范式，Selinger [24]被视为先驱，与Valiron [26]一起工作。在这种范式中，可以引用Altenkirch和Grattage的工作，他们为纯量子计算引入了一种函数式编程语言[2]，以及Van Tonder的提议，该提议使用λ演算也考虑了纯量子计算[28]，其中包括[4]，[1]，[9]。Vizzotto等人的工作。[30，32]通过使用Monads来模拟量子计算，启发了这项工作中使用的方法。除此之外，Calegaro和Vizzotto的工作 [8]为在面向对象语言中使用单子提供了一个起点S.S. Feitosa等人/理论计算机科学电子笔记324（2016）67776结论和未来工作本文介绍了FJQuantum，一个面向对象的语言，高层次的描述，显示其建设的相关概 念，以及 处理量 子计算概 念的程 序的几个 例子，通 过一个 单子层扩 展FeatherweightJava。我们相信，这种语言可以用来促进传统程序员对量子计算概念的学习，重用他们以前关于面向对象语言的知识。除此之外，还可以通过开发的解释器模拟量子算法作为未来的工作，有可能开发语法调整以改善源代码中量子态的可视化，实现语法糖以使用类似于命令式语言的一元层编写代码，并在所提出的语言中添加测量操作引用[1] S.艾布拉姆斯基量子计算与信息的高级方法。计算机科学的逻辑，2004年，第19届IEEE年会，第410[2] T. Altenkirch和Grattage J.一种函数量子编程语言。 在2005年第20届IEEE计算机科学逻辑研讨会论文集[3] 放大图片创作者：John W. Vizzotto和Amr Sabry纯量子规划的代数。电子笔记理论Comput. Sci. ，170：23[4] P. Arrighi和G.多维克线性代数λ演算：高阶，编码和一致性。eprint arXiv：quant-ph/0612199，2006年12月。[5] M.贝利亚和法医奥奇托Java：证明Java简单闭包的类型安全性。 CSP 2010，第61-72页[6] S. Bettelli，Luciano Sera fini，and T.卡拉科量子编程的架构。CoRR，cs.PL/0103009，2001年。[7] S. Boixo，T. F. Rønnow，S. V. Isakov，Z. Wang，中国山杨D. Wecker，D. A.激光雷达，J.M. Martinis和M.特罗耶超过100个量子比特的量子退火的证据。Nature Physics，10：218[8] 布鲁诺 Crestani 卡莱加罗 和 朱莉安娜卡扎拉尔 维佐托使用java闭包的量子单子。 在理论计算机科学（WEIT），2013年第二次研讨会-学校，第34-39页[9] 鲍勃·柯克和罗斯·邓肯相互作用的量子观测。在Automata，Lang和Prog。第5126卷，Lec. 计算机科学笔记，第298-310页。Springer，2008.[10] 大卫·多伊奇。量子理论、丘奇-图灵原理与通用量子计算机。400：97[11] R.费曼用计算机模拟物理。国际理论物理杂志，21：467[12] Jonathan James Grattage，James Chapman，Alex Green，Mark Jago，Wouter Swierstra，and MauroJaskelio.一种函数式量子编程语言。In：Proceedings of the 20th Annual IEEE Symposium on Logicin Computer Science，pages 249[13] S.哈尔格伦角Moore，M. Rtteler，A. Russel，and P. Sen. Limitations of quantum coset states for graphisomorphism.在STOC[14] P.A. Hiskett，D. Rosenberg，C.G. Peterson，R. J. Hughes，S. Nam，A.E. Lita，A.J. Miller和J.E. 诺德霍尔特光纤上基于长距离纠缠的量子密钥分配。新物理学杂志，8（9），2006年。78S.S. Feitosa等人/理论计算机科学电子笔记324（2016）67[15] D. Hucul，M. Yeo，W.K.作者：J. Olmschenk，和C.门罗 原子离子在线性及多维离子阱阵列中的输运。量子物理学电子印刷品，2月。2007年[16] Atsushi Igarashi，Benjamin C Pierce，and Philip Wadler.轻量级java：java和gj的最小核心演算。ACM Trans. on Prog.和系统，23（3）：396 -450，2001。[17] E. 尼尔量子伪码的约定，1996年。[18] T. Lanting，J.Przybysz，A.Yu. Smirnov，A.M. Spedalieri，F.H. Amin，M.J. Berkley，A.R. 哈里斯，F. Altomare，S. Boixo，P. Bunyk，N.迪克森角放大图片作者：P. Hoskinson，W.约翰逊，M。E. Ladizinsky，N.拉迪津斯基河Neufeld，T.哦，我。佩尔米诺夫角里奇角Thom，M.E. 托尔卡切娃，S.乌柴金湾威尔逊，A.和G.玫瑰量子退火处理器中的纠缠。Phys. Rev. X，4：021041，2014年5月。[19] N. D.人鱼量子计算机科学：导论。剑桥大学出版社，纽约，美国，2007年。[20] 穆新成和理查德·伯德功能性量子编程。2001年12月，在韩国大城市KAIST举办的亚洲程序设计语言和系统[21] Michael A. Nielsen和Isaac L.创. 量子计算与量子信息：10周年纪念版剑桥大学出版社，纽约，美国，第10版，2011年。[22] 伯恩哈德·奥默量子计算的过程形式技术报告，1998年。[23] J. W. Sanders和P. Zuliani量子编程。InMathematics of Program Construction，第80-99页。Springer-Verlag，1999.[24] 彼得·塞林格。量子编程语言。Journal of Mathematical Structures in Computer Science，14（4）：527[25] 彼得·塞林格。Dagger紧闭范畴与完全正映射。Electronic Notes in Theoretical Computer Science，170（0）：139- 163，2007.第三届量子编程语言国际研讨会论文集（QPL 2005）。[26] 彼得·塞林格和本·奥勒维特是狮子座的。用经典控制进行量子计算的一种微积分。J. Mathematical Structures in Computer Science，16（3）：527 -552，2006.[27] R. 拉克萨默中村角门罗·TD. Ladd，F.Jelezko和J.L. 奥布莱恩量子计算机。Nature Physics，464/online，2010.[28] 安德烈·范·唐德。量子计算的Lambda演算。 SIAM J. ，33：1109-1135，2004.[29] L. M. K. Vandersypen，M. Ste Escheren，G.布雷塔角Yannoni，M. H.舍伍德和I.L. 创. 利用核磁共振实验实现shor量子因子分解算法。Nature，414：883[30] 朱 莉 安 娜 ·K Vizzotto ， Thorsten Altenkirch ， and Amr Sabry.结 构 化 量 子 效 应 ： 超 算 符 如 箭 头 。 J.Mathematical Structures in Computer Science，16：453[31] 朱莉安娜·凯泽·维佐托在Haskell中构建一般和完整的量子计算：箭头方法。博士论文，南里奥格兰德联邦大学，2006年。[32] Juliana Kaizer Vizzotto，Bruno Crestani Calegaro，and Eduardo Kessler Piveta.量子计算中的双射λ-演算。在Programming Languages，卷8129的Lecture Notes in Computer Science，第61Springer BerlinHeidelberg，2013.[33] 朱莉安娜·凯泽·维佐托，还有雷·劳伯·杜波依斯，还有阿姆鲁·萨布里。 作为量子编程语言的微积分。在逻辑，语言，信息和计算，卷LNAI 5514计算机科学讲义，第379Springer，2009年。