您好、欢迎来到现金彩票网!
当前位置:2019欢乐棋牌 > 指称语义 >

量子程序设计语言研究

发布时间:2019-08-11 11:34 来源:未知 编辑:admin

  南京大学硕士学位论文量子程序设计语言研究 申请人:刘玲 学号:MG0833029 专业:计算机软件与理论 研究方向:新型程序设计 指导教师:徐家福教授王林章副教授 201 SomeResearches QuantumProgramming Languages By Liu Ling Supervised Prof.XUJiafu&Assoc.Prof.Wang Linzhang Athesis Submitted NanjingUniversity PartialFulfillment MASTERoF ENGINEERING Computer SoftwareTheory Department ComputerScience TechnologyNanj ing University April,2011 Nanjing,P.R.China 南京大学硕士学位论文 摘要 南京大学研究生毕业论文中文摘要首页用纸 毕业论文题目: 量子程序设计语言研究 过篁垫鏊鲑皇堡迨专业至QQ墨级硕士生姓名: 指导教师(姓名、职称):堡塞揎塾援三莶童剜塾堡摘要 量子程序设计语言是用于书写量子程序的语言,自1996年出现以来,颇受业界重视,它 已经成为量子计算领域研究热点之一。 本文在明确研究宗旨、简述几种有代表性的量子程序设计语言之后,着重介绍南京大学 计算机软件研究所所开发的NDQJava语言和NDQFP语言,以及作者自行设计的一种结构化 量子程序设计语言NDQJava-2。 NDQJava-2在NDQJava的基础上增添了量子条件语句、量子循环语句、量子子程序、量 子模块以及量子异常处理机制等量子成分,它是一种结构化的量子程序设计语言,文中给出 ]"NDQJava-2语言的形式语法和非形式语义。书写量子程序的实践表明,NDQJava-2是一种 比NDQJava更为实用、更为易读,其成分设定更为合适的量子程序设计语言。 关键词:量子程序设计语言,命令式风范,申述式风范,语法,语义,语用,量子算法,操 作语义,指称语义。 南京大学硕士学位论文 Abstract 南京大学研究生毕业论文英文摘要首页用纸 珊SIS:Some Researches SPECIALIZATl0N:POSTGRADUATE: SUPERVISORS: Quantum Programming Languages Computer SoftwareTheory LiuLing Prof.XU JiafuAssoc.Prof.Wang Linzhang Abstract Since firstquantum programming language came about 1996,manyscientists field.Ithas become one hotresearch field quantumcomputation. After giving quantumprogramming language,the reason why we do research talkingabout several representative quantum programming languages,this paper focuses quantumprogramming languages NDQJava NDQFPdeveloped ComputerSoftware NanjingUniveristy,especially,the quantum poragramming language NDQJava-2 developed myself.Thedesign ofNDQJava-2 somepowerful constructs,such quantumconditional statement,quantum loop statement,quantum subroutine,quantum module,and quantum exception handling mechanism astructuredquantum programming language.In formalsyntax informalsemantics amorepractical,more readable moreconvenient quantum programming language. Keywords:quantum programming language,imperative paradigm,declarative paradigm,syntax, semantics,pragmatics,operational semantics,denotational semantics. II 南京大学硕士学位论文 目录 目录摘要………………………………………………………………………………………………………………………………..I ABSTRACT…………………………………………………………………………………………………………………….. 目录…………………………………………………………………………………………………………………………….I 第一章 引言………………………………………………………………………………………1 1.1什么是量子程序设计语言………………………………………………………………………1 1.1.1什么是语言…………………………………………………………………………………1 1.1.2自然语言和人工语言………………………………………………………………………1 1.1.3经典程序设计语言…………………………………………………………………………2 1.1.4量子程序设计语言…………………………………………………………………………2 1.2为什么要研究量子程序设计语言………………………………………………………………3 1.2.1适应量子计算机之需………………………………………………………………………3 1.2.2 Shot算法及Grovel算法之出现……………………………………………………………3 1.2-3南京大学的研究…………………………………………………………………………….3 1.3如何研究量子程序设计语言……………………………………………………………………4 1.3.1学习研讨…………………………………………………………………………………….4 1.3.2设计实现…………………………………………………………………………………….6 1.4本文的结构………….……………………………………………………………………………6 第二章 几种有代表性的量子程序设计语言……………………………………………………。7 2.1量子伪码…………………………………………………………………………………………7 2.2 Qgol…...….………......…..…………….………………..………………………………………….……….…………….1() 2.3 QCL……….….…….……...…….……………….………….……………………………………………………………...14 2.4 qGCL.............................................................................................................................……........19 2.5 QML.......,.......................................................................................…….……......……………...........22 第三章研究背景……………………………………………………………………………….29 3.1语言风范……………………………………………………………………………………….29 3.1.1理解………………………………………………………………………………………29 3.1.2种类………………………………………………………………………………………………………………29 3.1.3命令式语言和申述式语言比较………………………………………………………….30 3.2命令式语言…………………………………………………………………………………….31 3.2.1 NDQJava.............................................................…….........................................................31 3.2.2 NDQJava的实现………………………………………………………………………….33 3.3申述式语言…………………………………………………………………………………….37 3.3.1 NDQFP................................…….........................................................................................37 3.3.2 NDQFP的实现………………………………………………………………………….40 第四章NDQJava一2…………………………………………………………………………….42 4.1设计准则………………………………………………………………………………………..4.2 III 南京大学硕士学位论文 第一章引言 4.2基本成分…………………………………………………………………………………………43 4.2.1增添的量子成分…………………………………………………………………………..43 4.2.2其它量子成分……………………………………………………………………………..48 4.3示例……………………………………………………………………………………………一50 第五章今后的工作……………………………………………………………………………….54 5.1 NDQJava-2的形式语义与实现………………………………………………………………54 5.2风范问题研究…………………………………………………………………………………54 致{射……………………………………………………………………………………………………………………………55 参考文献…………………………………………………………………………………………u 56 附录攻读硕士学位期间发表论文及参与项目情况………………………………………………58 南京大学硕士学位论文 第一章引言 第一章引言 本章主要包括什么是量子程序设计语言、为什么要研究量子程序设计语言、如何研究 量子程序设计语言,以及本文的结构等四节。 I.I什么是量子程序设计语言 为了理解什么是量子程序设计语言,首先必须理解什么是语言,盖因语言分自然语言和 人工语言两大类,程序设计语言是一种人工语言,量子程序设计语言又是一种程序设计语言 之故。 1.1.1什么是语言 语言是人们赖以交流信息之工具,严格说来,语言的基础是一组符号与一组规则。根据 规则由符号构成之符号串的总体就是语言。 任何语言都包括语法,语义,语用三个方面【l,2]。 语法指明语言的结构,亦即,语言的结构规则。符合结构规则的符号串才是语言的组成 部分,不符合结构规则的符号串则不是语言的组成部分。 语义表示语言和情景无关的含义,亦即表示语言各个组成部分和情景无关的含义,或者 可以说,语义表示语言的固有含义。 语用表示语言和情景有关的含义,或者可以说,语用表示在实际情景下使用时语言的含 1.1.2自然语言和人工语言自然语言[3】是随着人类社会的发展自然演化而成的语言,简言之,由于人的智力而产 生天赋语言能力,其结果按照非预谋的方式而形成的语言,即自然语言,如英语、华语、 法语等皆是自然语言。值得注意的是,自然语言的形成与发展,也并不一定完全自然,其 中也会伴随一些人为的带有预谋性质的因素,如日语的形成即是如此,不过,自然语言的 形成与发展主要却是自然演化而成的,亦即,按照一种非预谋的方式而形成的。 人工语言恰恰相反,它是由人们根据一定的意图,按照一种预谋的方式设计而成的语 言[3],语言的一组符号与一组规则都是由人自行设计的,如世界语,各种程序设计语言均 为人工语言。 南京大学硕士学位论文 第一章引言 1.1.3经典程序设计语言 用于书写经典计算机程序的语言即为经典程序设计语言。它是伴随经典计算机的诞生 而出现的语言。按语言级别分,有低级语言与高级语言。低级语言包括机器语言和汇编语 言。在一定程度上和具体机器有关,因而,用低级语言书写程序时,冗长繁琐,易出差错, 高级语言则是较为接近算法之表达形式,较为接近数学语言之语言,它摆脱了低级语言的 机器相关性,以及由此带来的繁琐,从而更便于人们书写程序。按语言之使用范围分,有 专用语言和通用语言,专用语言只适用于特定领域,通用语言则可适用于多种领域。当然, 经典程序设计语言尚有其它分法,如交互式语言与非交互式语言,命令式语言与申述式语 言等等。高级语言的思想源于1951年瑞士学者H.Rutishauser的设想【2,4】,国际上第一个 可用的高级语言乃是1956年由J.Backus所领导的小组在IBM704机器上实现的Fortran, 其它著称的高级语言有Algol、Cobol、Pascal、C、C++、Java、Ada等。 1.1.4量子程序设计语言 量子程序设计语言是用于书写量子计算机程序的语言。由于量子算法中也会包含经典 计算,因而业界设想,最近将来出现的量子计算机是一种混成结构的,它包含两大部分: 一部分是经典计算机,负责执行经典计算与控制;另一部分是量子设备,负责执行量子计 算,其中又包括两类量子运算,即酉运算(即酉变换)与测量运算。前者是可逆的,用于 量子态的改变,后者是不可逆的,用于获取量子计算之结果。量子设备是基于量子力学基 本原理而构建的,其最基本的存储单位是量子比特(qubit),和经典比特不同,量子比特 在一定时刻,其取值可以同时为0和1,并且还可以取0与1之间的任何实数为值,这是 由于量子态为一叠加态的缘故。和经典计算类似,量子计算过程亦为三步,即入(初态制 备),算(执行一列酉运算),出(执行测量运算)。 Deutsch[5]在1985年首先提出“设计为量子计算机而用的程序设计语言是一个有趣的 难题”,此后,有少数计算机科学家开始进行尝试。虽然人们相信量子信息处理设备应该像 经典计算机一样使用高级语言来编写程序,但基于这种目标设计的语言在1996年6月才出 现,即Knill[6]提出的“量子伪码”(“伪码”[7】可以看作是一种强调书写紧凑与清晰、又 不涉及诸如类型抽象、模块性,以及异常处理等和软件工程有关之成分的高级语言),15 年来,量子程序设计语言己发展成量子计算的一个重要分支,著称的量子程序设计语言有 量子伪码、Qgol、qGCL、QCL、QML等,其中量子伪码、qGCL、QCL是命令式语言, Qgol、QML则是申述式语言。 南京大学硕士学位论文 第一章引言 1.2为什么要研究量子程序设计语言 1.2.1适应量子计算机之需 1982年Feynman[8]提出基于量子力学原理构建计算机的设想,引起国际业界普遍重视, 理由是,作为经典计算机之物质基础之集成线路,其集成度之增加超过某一界限时,集成 线路之部分与部分之间出现的量子现象会互相干扰,致使集成线路不能正常工作,因而, 其集成度存在某一极限值,不可能无止境地增加。从而Feynman的设想促使世界循不同途 径展开研究,如核磁共振途径,离子阱途径,光学途径,超导途径等。从硬件角度看,研 究工作已有相当进展,但难度很大,其中最大的困难是解决消相干问题,以及降低实验环 境的苛刻要求问题,据报道,后一问题最近有较大进展。从软件角度看,当今可用之量子 算法为数甚少,即使硬件困难解决,可用之量子计算机造出,缺少合适可用之量子算法, 则量子计算机之优越性亦难以发挥,尽管如此,业界依然认为,量子计算机具有存储容量 大,运算速度快,安全性能好等三大优点,受到国际高度重视,前景十分看好,有人认为, 可用之量子计算机可望在2030年左右出现,因此,我们理应“未雨绸缪”,及早开展量子 软件,特别是量子程序设计语言之研究。 1.2.2 Shor算法及Grover算法之出现 1994年美国数学家P.W.Shor[9】发表了大数质因子分解算法(即所谓的Shor算法), 其中运用了量子快速傅氏变换,以及量子并行性,将其复杂度由先前算法的之指数级降至 多项式级,这一成果引起国际业界轰动。1996年L.K.Grover『101又发表了数据库的搜索 算法,将其复杂度由先前算法的O(n)降至o(百),其下降幅度虽逊于Shor算法,但 这一结果亦同样令人震惊,这两项成果从软件角度证实了量子计算、量子计算机的优越性, 从而,不仅在国际上促进了量子计算、量子计算机领域的发展,也促进我们坚定信心,进 行量子软件,特别是量子程序设计语言的研究。 1.2.3南京大学的研究 南京大学计算机软件研究所研究经典软件语言(包含程序设计语言,以及设计级,功 能级,需求级之规约语言)达五十年,曾经设计并实现了多个软件系统,特别是对软件语 言进行了系统研究,相应地开发出多个软件自动化系统,虽然所涉及的语言均为经典语言, 但是,量子语言虽与经典语言有别,但亦有共性,因此,其研究经验与教训对于我们研究 南京大学硕士学位论文第一章引言 量子语言,必将有所借鉴。 1.3如何研究量子程序设计语言 1.3.1学习研讨 由于量子计算是基于量子力学原理的计算,因此,为了研究量子计算、研究量子程序 设计语言,首先,必须学习量子力学,在学习过程中,我们着重学习以下问题。 第一、什么是量子。 迄今关于量子的定义有三: 一是把量子定义为这样的量,即某些物理量(如能量、电荷、角动量等)的取值不是 连续的,而是离散的,其相邻两个离散值之差,即为量子,这一定义的基础是,这些物理 量所取之离散值应为等距。 二是把量子定义为具有波粒二象性的微观客体,所谓波粒二象性是指,这些微观客体 既有波的特性,又有粒子的特性,换言之,即所谓:“运动似波,作用如粒”。但是这里所 谓的波不是经典的波,所指之粒不是经典粒子,其中“似”,“如”均不等于“是”。 三是把量子定义为任何场的基本激发态,把量子定义为物理态。 第二、什么是量子力学 一般认为,量子力学是这样一门学科,旨在研究微观客体的结构、特性和运动规律, 但是,量子力学亦可用来解释宏观客体的某些现象,因此,可以认为,量子力学【】是一 门研究微观客体以及在一定条件下宏观客体的结构、特性和运动规律的学科。 第三、什么是量子力学基本原理 一般认为,可以把上世纪20年代J.von Neumann以四大公设[11]形式陈述的内容作为 量子力学基本原理。 第一公设称作量子态公设,说的是,封闭物理系统对应于一个希氏空间(称作状态空 间),空间的向量表示量子态。 第二公设称作演化公设,内容有二,一是量子态的演化靠酉运算,即将一酉运算作用 于量子态将使之由一量子态改变为另一量子态,反之,欲使一量子态改变为另一量子态, 除施行酉运算外,别无它法。二是量子态随时间而变,相应的量子态函数(即所谓波函数) 遵照SchrOdinger方程,即有 i^铀IX> aI 其中^为Plank常数,H为一确定的Herrmite算子。 第三公设称作测量公设,说的是,量子测量由一组测量算子刻画,它们满足完全性方 南京大学硕士学位论文第一章引言 程x1 >M+mMm=1 其中m对应可能的测量结果,其发生的概率为:P(m)=<xlM+MmIx> lx>为系统紧靠测量前的状态,测量后的状态为: (M。IX>)/ /(<xlM+M。Ix>) 第四公设称作复合系统公设,说的是,复合物理系统的状态空间是相应诸分系统空间 的张量积。即如果有n个分系统,i分系统的状态记为>,则整个复合系统的状态可以 表示为I(P1>圆I‘p2>0…0 第四、什么是量子化量子化指的是某些物理量只能取离散值的特征,量子化一词本义是离散化。 第五.什么是塌缩 量子态受到测量运算的作用,而导致塌缩,其含义是,由量子态塌缩到某一经典态, 从现象上看,塌缩具有四大特征,即随机性、不可逆性、斩断相干性以及空间非定域性。 但是为什么测量会导致塌缩,塌缩为什么有上述四大特征,塌缩是否需要时间等问题,迄 今尚无令人满意的解释,均有待于进一步研究。 第六、什么是纠缠 量子纠缠[12]指的是多个量子系统之间存在非定域、非经典的强关联。 其一,从实验观测角度,纠缠的本质是关联塌缩中的“关联性”,反映非定域性,关联 塌缩是纠缠态存在的标志。 其二、从理论分析角度,纠缠等价于Bell不等式被破坏。 其三、从信息学角度,纠缠的本质在于产生新信息。 但是,为何会发生纠缠,纠缠的物理定义,以及什么才是纠缠的问题核心等问题迄今 均未明朗,有待于进一步研究。 第七、什么是不确定性关系 Heisenberg于1927年提出了如下的不确定性关系(亦称作测不准原理): 粒子在X方向上位置不确定量Ax和在该方向上动量不确定关系Ap满足 一般认为,不确定关系和前述之波粒二象性为量子力学的两大支柱,至于何者更为本质,尚有不同看法,例如: 南京大学硕士学位论文第一章引言 Feynman将不确定关系视为自然界的根本属性,他认为“实际上,所有物质的量子力 学的全部力量都依赖于不确定关系的正确性”。 de Broglie则说“不确定性是物理实质,这样的主张并不完全站得住”。 Dirac则说:“在我看来,我们还是没有量子力学的基本定律”。 其次,我们学习讨论了量子程序设计语言的若干基本文献,主要是几种有代表性的量 子程序设计语言,即前述之“量子伪码”,Qgol、qGCL、QCL、QML等(详见第二章)。 1.3.2设计实现 在学习前人工作的基础上,南京大学计算机软件研究所自2005年起先后设计并实现了 两种量子程序设计语言,NDQJava和NDQFP。前者是命令式的,后者是申述式的,前者 在Java的基础上增添了量子类型,量子变量、量子表达式、量子语句、量子分程序等成分。 后者对FP作了较大改动,如引入类型,模块、异常处理等成分,2009年起,笔者在徐家 福教授的指导下,又设计出量子程序设计语言r《OQJava-2,它是NDQJava的改进版本,主 要是增加了条件构造、循环构造、子程序、模块、异常处理等。 1.4本文的结构 在本章引言中,回答了,什么是量子程序设计语言,为什么要研究量子程序设计语言, 以及如何研究量子程序设计语言三个问题,并给出了本文的结构: 第二章介绍几种有代表性的量子程序设计语言; 第三章讲述了本研究组过去的工作(即NDQJava与NDQFP的设计与实现); 第四章重点介绍了笔者设计之NDQJava-2 第五章是对今后工作的考虑。 南京大学硕士学位论文第二章几种有代表性的量子程序设计语言 第二章几种有代表性的量子程序设计语言 本章综述了量子伪码,QgoI,QCL,qGCL,以及O.ML五种有代表性的量子程序设计语 2.1量子伪码所见的第一篇关于量子程序设计语言的文章是E。Knill[6]的“量子伪码约定”(LANL 报告LAVR-96-2724。1996.6)。 该文引进了若干关于书写量子伪码的约定,作者指出,这些约定尚属初步,欢迎读者提 出意见,以便改正。 l、量子计算 量子计算是基于量子力学基本原理的计算,和经典计算不同,量子计算的计算对象是 量子态,量子态是一种叠加态,即一组基态的复线性组合,计算中所含的基本运算有两类, 一类是酉运算(可逆);另一类是测量运算(不可逆),量子计算的计算过程和经典计算类 似,亦可分为三步,即初化(初态制备),计算(执行一列酉运算),输出(执行测量运算) 使最近的量子态塌缩到某一基态。 2、硬件平台 (1)量子计算机 量子计算机是基于量子力学基本原理而构建的计算机,其合适的体系结构还有待于进 一步研究,目前一般认为,较为可用的结构是:量子计算系统由两部分组成,一部分是经 典机:另一部分是量子设备,或谓量子随机存取机(QRAM)。经典机负责执行经典计算(由 于量子算法中可包括经典计算)以及对量子设备之工作进行控制;量子设备负责执行量子 运算,亦即,执行酉运算与测量运算,量子设备主要由一列量子寄存器组成。 (2)经典计算机 鉴于目前量子计算机尚未问世,量子计算只能在经典机上模拟实现。 3、量子伪码 量子伪码是用以书写量子计算的语言,它是经典伪码在量子计算领域的拓广,其中主要 的拓广涉及量子寄存器。 4、量子寄存器 定义:量子寄存器是未知呈经典态的经典寄存器,换言之,即为呈量子(叠加)态的经 典寄存器。 分组:为使用方便计,可将量子寄存器分组,即分为若干彼此独立(即互不纠缠的)的 南京大学硕士学位论文几种有代表性的量子程序设计语言 量子寄存器组。 引进:量子寄存器的引进方法主要是隐式引进,即对经典寄存器施行酉运算,或调用回 送量子态的子程序,下列中带下划线者表示量子寄存器,不带下划线者表示经典寄存器。 a-05 C:将a转换为量子寄存器,不做任何运算,以后旦之运算仅限于量子运算。d_lO C:将d说明为一个含整数10的经典寄存器 鱼卜UNIFolc5lsUPER。SITl0N(d) C:UNIFOR^ISuPEROsITION(d)取一个经典输入(此时为一整数),并引入了一个量子态 的量子寄存器,其状态和系统中的任何其它量子寄存器无关。 £-MULTIPLY(垃,d) c:这里的子程序MULTIPLY有一个量子输入垃和一个经典输入d,引进一个新的量子寄 存器C,它可能和b是纠缠的。 x-DoSomethingClassical() 墨。DoS0methingClassical(x,d) C:对x加以转换,并/或含于子程序中的量子运算,这一事实由左方带量子标注的赋值 语句显示说明 运算: (1)酉运算,例 给出ll>的相移中。 为受控于旦的}1>的也的受控相移。FOURIER(a,d) 输入:d个量子比特寄存器丑其最高有效量子比特之下标为d一1。 输出:旦之幅度在z2a上进行傅氏变换之结果,输出中的最高有效比特之下标为O。 U_e2inl24 南京大学硕士学位论文几种有代表性的量子程序设计语言 2d--l-1州(c:如果该酉运算中的相位改变比1/n2小得多,则在终态精度内相应小的代价上该运算 便可以忽略,因此,这一过程可以修改成,接受一个精度参数,以减少量子运算之数目。 a-MEASUREFOURIER(丑d)输入:d个量子比特的量子寄存器当其最高有效量子比特之下标为d-1, 输出:Zza上对a之幅度进行傅氏变换并测量,输出的最高有效比特之下标为0,在这 一过程中,输入量子寄存器回到经典态。 U卜e2i.n-/2“ 灭出(aj):If(ai) ai-鱼 巾-(中+aiTr)/2 C:该赋值语句的右方表达式要求ai呈经典态,这是由于它包含了不许对量子寄存 器所进行的运算 (3)赋值语句书写规则 (i)同一个量子寄存器不能出现在赋值语句的双方。 (ii)只在左方出现的寄存器,必须或为经典寄存器(这时原内容已消失),或为以前未曾 说明的寄存器。 (iii)只在右方出现的寄存器在运算中可有副作用,亦即,这里假定,寄存器,特别是, 量子寄存器是按引用传递的,在子程序的输出描述中指明变元寄存器有哪些副作用是一种 好的想法。 (iv)右方以量子形式出现的寄存器,以及左方以经典形式出现的寄存器,在此运算中最 终要被测量(或显式或隐式) 5、元运算 南京大学硕士学位论文几种有代表性的量子程序设计语言 REVERSINGECAMPLE kthenDOSTUFFTO(量) reverse旦-ADD(臣c) (2)条件 tf鱼then(: c_not(垒,旦)(3)经典.可逆 设b卜FUNCTION(a) 为一对输入不具副作用的经典实现中出现之式,则 b卜FUNCTIONR(a) 便表示具有预期结果,且所相应量子寄存器均可逆,回到初态的可逆实现。 2.2 Qgol G.David Baker[13]在一篇题为“一个模拟量子计算的系统”Qgol“:理论、实现与 洞观”的文章中主要论述了量子计算机体系结构、量子计算机的形式描述,通用纯量子计 算机的不存在性,Qgol语言结构,量子计算与函数式语言,以及超光速通信等问题,今简 述如下: 1、量子计算机体系结构 鉴于一般量子计算问题中既包含量子计算也包含经典计算,如所熟知,在经典计算机上 可以模拟进行量子计算,这样做,工作量过大,程序冗长,未能发挥量子计算的优势,另 一方面,如果只考虑着眼于(纯)量子计算的量子设备,计算问题中的经典计算部分就要 在量子设备上进行,致使“量子设备”大材小用,“杀鸡用了牛刀“,显然太不合算,故 而设想量子计算机的体系结构应该由两部分组成,一部分是经典计算机,它负责处理计算 问题中的经典计算部分与控制,另一部分是量子设备,负责处理纯量子计算,两部分之间 既有分工,又有合作,共同完成量子计算问题中的计算。 2、量子计算论域的抽象形式描述 计算论域U为一个四元组(Us,Ua,Uo,U。,) 其中Ua是状态集,Us是稳定状态集, Us_CUa,Uo是Ua上的运算集,运算集对组合而言 是封闭的。U。为观测函数,它是一个二元函数,一元是随机值,另一元是Ua中的元素。 10 南京大学硕士学位论文 几种有代表性的量子程序设计语言 在量子论域Q的情形,有 Qs=整数集的子集: Qa={q;=((x,c;)I Qo={ff为二比特酉运算的有限连接积} Qv=典型观测函数 3、通用量子计算机的不存在性 作者在给出如下定义与定理后,证明了“通用纯量子计算机“是不存在的。 定义1。如果一个本征态经历一次观测,而后被经典地置于新值,并再经历量子计算, 便称该本征态是再循环的。 定理1在计算结束或计算进行中观测的任何不带再循环元素的系统等价于计算结束 时一次观测的系统。 定理2去掉再循环,不会将多项式时间问题变成指数时间问题 定理3任一需要观测中间过程的算法总可以变成一个具同样时间复杂度、而不需要观 测中间过程的算法。 定义2纯通用量子计算机是一组施行酉运算的门所构成的非循环网,它在实施过程中 要经受观测。 据此,可以证明,纯量子网不是通用的,换言之,通用纯量子计算机是不存在的。 4、Qgol语言结构 (1)语言风范 Qgol的模拟程序系统不是基于面向对象的,因为量子系统并不能容易描述成交互对象 的集合,函数式程序设计语言有很多构想可以精确模拟量子理论,这使得设计量子模拟程 序比较容易。 基于面向对象的模型有两个方面:一方面,运算的对象空间,运算是高继承形式,如 两个数的相加是二进制运算的运算子集,而二进制运算集又是经典运算的子集。另一方面, 有非纠缠希氏空间的组合,每一希氏空间是对(幅度,本征)集,每一本征是对(变量名, 量子程序设计语言的实现并不提供自动的无用信息回收功能,因为量子系统不能观测状态,也就不能进行无用信息回收,只有所有的运算都进行完才能进行相关的回收,这里 的观测指的是测量。因此用命令式语言c++来完成检测使用的是否是酉运算,系统不能保 证所有的运算都是酉运算,因为c++语言的每个运算都是一个对象(具有可变的内部状态), 可变的内部状态是基础,但是面向对象的另一个方面:信息传递,在量子级别上,域之间 的信息传递相对于宏观世界要有所改变。面向对象的设计要求系统可以描述为各个子系统 的集合,各个子系统之间按照一定的方式交互信息,这些都不适合量子领域。 南京大学硕士学位论文 几种有代表性的量子程序设计语言 纯函数式程序设计语言并发-Clean[14]是任何惰性求值语言中可以高速运行实现的语 言,在其某些版本中,并行性和线程性也都可用,很易于为开发用户接口提供高层机制。 并发-Clean没有语句,只有引用透明表达式,程序是一组Modula一3风格的模块,每 个模块是函数定义的集合。函数“Start”在主模块中的求值定义了程序的行为。引用透明 性消除了“敌意函数”的问题,没有内部状态,也不会对系统的其它部分产生副作用,也 没有观察和运算行为的不相符问题,也可以简单解决无用信息回收问题,使用的都是惰性 求值机制一系统中的值直到必要时才是确定的(没有函数调用),命令式语言的现代编译 程序都是静态代码分析(不在任何环境下执行或者没有任何影响),而惰性求值只需要对 运行中使用到的一部分求值,不需要检测其它部分,因此可以有效的改进算法,并且具有 一定的灵活性,可以避免命令式语言的编译存在的问题。 作者指出量子算法本质上是申述式的,因为存在不可分解的量子算法,因此不是命令 (2)唯一性类型并发-Clean纯函数式程序设计语言引入了类型这个属性,每一个对象都有一个类型, 这个类型是严格的,唯一的。严格性和惰性求值是相互矛盾的,但也保证了随时都可能进 行求值,但不是必须的。系统类型(编译时刻)可以确保运行时间有一定的内存在适当的 时刻可以自由重用,这样无用信息回收就易于实现。并发Clean中唯一的类型在表达式的 右边至多只出现一次,这也表明如果函数有一个唯一类型的参数,那么内存就可以安全讹 用,没有别的运算去留意它。这样,就有一些模式,可以简单的描述顺序计算: sequential_function::*State-*State sequential_function sl=final_thing where s2=first—operation sl s3=second_operat ion s2: final——thing=last——operation s3 类型系统保证了程序人员不会有下形的无意查错,s3=second_operation sl,因为s1 是唯一类型的缘故。这样的技巧就可以设计出巧妙的系统与windows系统相交互,并且不 失引用透明性。 (3)函数规约 利用并发Clean语言的全部功能,作者只用四行就能提出所有重要函数的定义一一使人 联想到Clean对为解决量子问题提供了一个好的抽象, ::Quantum C定义了一个抽象数据类型“Quantum”,以类型C为参数,C可为任意类型,比如,字符、 南京大学硕士学位论文 几种有代表性的量子程序设计语言 整数表、实数元组或其它的抽象类型。抽象类型Quantum为何和集合、表和字典等属于同 一类?Quantum c是一个系统,它可以是CS的一个叠加态,就如同一个硬币既有head又 有tail,量子硬币可以呈head和tai 1的任何一个叠加态。几个函数规约是: prepare:: c-木(Quantum 定义了一个prepare函数,可以把任意类型的对象转变为一个Quantum抽象类型,“:Ic”表示定义的类型是唯一类型。 observe::木(Quantum c)Real_c Eq c执行observe函数,将量子叠加态转变为单个不同的状态,不幸的是,随机性在引用透明 性系统中是难以表示的,并且函数中必须显式包含一个随机的实数。 Entangle: e)木(Quantumc)木(Quantum d)_枣(Quantum Entangle函数是高阶函数,其第一个变元为函数,并且必须是可逆的,第二个和第三个变元是相互纠缠的量子系统。 由于量子不可克隆原理和海森堡不确定性原理,因此任何量子状态不可复制。在一个 状态非唯一的成员中可以包含复制运算,但是不能复制整个系统。比如状态i ailxi>可以 对xj进行复制为;iiIxi.xi>,但是不能对整个系统进行复制i c【iIxi>0i GiIxi>。定义 的量子类型Quantum是唯一类型,不管其抽象,可以避免忘却不可克隆原理的现象,一旦 忘却就会引起编译时的错误,可以很好的避免这类错误的发生,保证其正确性。 (4)受限参数化 受限参数化是函数式程序设计语言试图引入面向对象程序概念的尝试,Clean和 Hashell用函数规约来表达继承,比如,面向对象的问题:圆、正方形、三角形之间有一 种共性,即都具有颜色、面积等属性,可以将这些共性抽象到一个形的基类中。在函数式 语言中继承用规约表达,利用并发Clean的记法,有 class Shape awhere ColorOf::a_Color Shape aAreaOf:: a_Real Shape a该规约说的是,假定函数ColorOf将类型a的对象给类型为Color的对象,函数AreaOf 将类型a的对象给一个Real数,则a是Shape类型,这种方法可以简单实现可逆,只需 加入一个可逆方法即可创建Shape a:即加入 Oreate::[vertex]_a Shape a对函数限制可以避免编译时的错误。 (5)量子电报 量子通信可能存在超光速的信号传递,称作“量子电报”,这种传递方式是否可能?

http://acetechpng.com/zhichenyuyi/501.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有