（计算机科学与技术专业论文）量子计算机体系结构及模拟技术的研究与实现.pdf

一= 星些些型堇垒墼塑兰垒墼些垒一 摘要 计算机的发明为人类探索世界提供了有利的支持。随着科学技术的发展，人们对计算 机处理信息能力的要求愈来愈高，但是传统的计算机体系结构由于其自身内在的限制显得 力不从心。人类在不断提出各种新型体系结构的计算机，以实现更高、更快、更强的追求 目标。量子计算机由于利用量子力学系统的本质特性而具有极高的计算性能，是未来计算 机发展的一个方向。 量子计算的研究主要集中在三个方面：量子计算基础理论研究、量子计算应用研究和 量子计算机实现技术研究。做为一种新型信息处理方法，其研究在近几年取得了引人注目 的进展。量子算法的研究在1 9 9 4 年后取得了长足的进步，显示量子计算在未来信息处理 中的强大能力。量子计算机的实现技术也在不断发展。已经提出了多种量子计算机的物理 实现技术，如核磁共振、离子阱等。目前在实验室中已经研制出了7 位量子计算机原型系 统，量子计算机的可行性问题已经解决。研究量子计算机体系结构，探索如何利用现有的 技术来构造高性价比的量子计算机系统具有重要意义。但目前这方面的研究还比较少。对 于我们来说是一种挑战也是一个机遇。 针对这种情况，通过对量子计算技术的深入研究，全面剖析现有量子计算系统，借鉴 经典计算机中的研究成果，作者提出了协同量子计算机体系结构方案，在该方案中，使用 经典计算机完成量子程序中的常规数据处理和程序逻辑控制，而将量子计算部件做为协处 理器，只负责完成量子计算。与纯量子计算机结构相比，该方案具有性能相当，实现简单 的优点。该方案中使用了量子指令动态调度技术，有效提高了量子计算处理器的执行效率。 借鉴量子纠错编码的研究成果，提出了自纠错的可靠量子存储系统方案，为协同量子计算 机提供了可靠的存储系统。 由于量子指令的动态调度能在出现数据相关时尽量减少量子协处理器空转，但是不能 消除数据相关。在量子网络计算模型的基础上，深入分析了量子网络中存在的并行性，提 出了并行量子计算模型，研究了开发量子网络并行性的方法，提出了量子网络并行化重构 算法。该技术可以提高量子网络的并行性，可以用于量子计算程序的编译优化。 结合量子计算需求，作者设计了一种面向对象量子计算编程语言q j a v a ，它对标准j a v a 编程语言进行了量子计算扩充，具有面向对象特点和较强的量子计算描述和计算能力。利 用该语言开发和实现量子计算算法的编程方便简洁。 作者总结分析了现有的量子计算软件模拟系统，确定了软件模拟量子计算系统的需求 以及设计中要解决的若干关键问题。结合量子计算机体系结构的研究，设计实现了一个量 子计算软件模拟系统q c d k 。该系统是个集成开发环境，便于用户设计、调试和运行量 子程序，同时也能支持对量子计算机体系结构的研究和模拟。该系统具有较好的可扩充性 和可移植性。 为了提高在经典计算机上进行量子计算模拟的性能，研究了使用向量处理部件提高模 拟性能的技术。由于量子计算过程可以使用向量计算模拟，因此适合具有向量处理的微处 理器。研究结果表明向量处理技术对提高量子算法软件模拟系统的性能具有重要意义。 第1 页 国防科学技术大学研究生院学位论文 作者针对g r o v e r 量子搜索算法存在的不足进行了改进和完善，使其在任何条件下都能 够有效地进行搜索。提出了搜索列表极小值的量子算法，它具有d ( 05 ) 的时间复杂度，n 为列表个数。在经典二分法的基础上，提出了二分法量子搜索算法，它的时间复杂度为 o ( ( 1 0 9 n ) o5 ) 。这些算法对于在量子计算机上求解p 问题具有重要意义。 关键字：量子计算机，计算机体系结构，计算机模拟，量子算法 a b s t r a c t c o m p u t e ri sav e r yp o w e r f u lt o o lf o rh u m a nb e i n g s t oe x p l o r et h ew o r l d w i t ht h ef a s t d e v e l o p m e n to f s c i e n c ea n dt e c h n o l o g y , m o r ea n dm o r ei n f o r m a t i o np r o c e s s i n ga b i l i t i e so f c o m p u t e ra r er e q u i r e d m a n yn e wc o m p u t e ra r c h i t e c t u r e sh a v eb e e nd e v e l o p e d t oa r c h i v et h e h i g h e r , f a s t e ra n dm o r ep o w e r f u lt a r g e t t h eq u a n t u mc o m p u t e rh a sm u c hm o r ec o m p u t i n g p o w e r t h a nc l a s s i cc o m p u t e r i ti san e wd i r e c t i o nf o rt h ef u t u r ec o m p u t e r t h e r ea r et h r e em a j o rf i e l d si nq u a n t u mc o m p u t i n gr e s e a r c h t h e ya r eq u a n t u mc o m p u t i n g t h e o r y , q u a n t u mc o m p u t i n ga p p l i c a t i o na n d t h ei m p l e m e n t a t i o no f q u a n t u mc o m p u t e r a san e w k i n do f i n f o r m a t i o np r o c e s s i n gt e c h n o l o g y , t h eq u a n t u mc o m p u t i n gr e s e a r c hh a sm a d em a n y s p e c t a c u l a ra c h i e v e m e n t si nr e c e n ty e a r s q u a n t u ma l g o r i t h m sr e s e a r c hh a sb e e nd e v e l o p e d s i n c e1 9 9 4 ，a n dh a sp r o v e dt h a tt h eq u a n t u mc o m p u t e rh a sg r e a t e rc o m p u t i n gp o w e rt h a nc l a s s i c c o m p u t e r t h et e c h n o l o g i e so f q u a n t u mc o m p u t e ri m p l e m e n t a t i o n h a v eb e e nb e c o m i n gp e r f e c t g r a d u a l l y r e s e a r c h e r sh a v ep r o p o s e dm a n yi m p l e m e n t a t i o nt e c h n o l o g i e ss u c ha sn m r ( n u c l e a r m a g n e t i cr e s o n a n c e ) ，i o nt r a pe t c t h e5q u b i t sa n d 7q u b i t sq u a n t u mc o m p u t e rh a v eb e e nb u i l t i nl a b o r a t o r y s oi ti sf e a s i b l et om a k eq u a n t u mc o m p u t e r i ti sm o r ei m p o r t a n tt or e s e a r c ht h e q u a n t u mc o m p u t e ra r c h i t e c t u r ea n dh u ev a r i o u st e c h n i q u e si ne x i s t e n c et ob u i l daq u a n t u m c o m p u t e rw i t hh i g hp e r f o r m a n c ea n dl o wp r i c e e m p i r i c a ls t u d i e so f p r a c t i c a lq u a n t u mc o m p u t e r a r c h i t e c t u r e sa r e j h u tb e g i n n i n gt oa p p e a ri nt h el i t e r a t u r e i ti sac h a l l e n g eb u ta l s oag r e a t o p p o r t u n i t yf o ru s b a s e do nt h et h e o r ym o d e lo f q u a n t u mc o m p u t i n ga n dt h eq u a n t u mc o m p u t i n gt e c h n i q u ei n e x i s t e n c e ，w eh a v ep r o p o s e dt h ec o o p e r a t i n ga r c h i t e c t u r eo f q u a n t u mc o m p u t e r i nt h i s a r c h i t e c t u r e ，i tu s e st h ec l a s s i cp r o c e s s o ra si t sc o n t r o lu n i t ，a n dh u et h eq u a n t u ma r i t h m e t i c l o g i c a lu n i ta n dq u a n t u mm e m o r yu n i ta si t sc o - p r o c e s su n i t t h i sa r c h i t e c t u r ei sm u c hs i m p l e r t h a np u r eq u a n t u mc o m p u t e r , a n dh a se q u i v a l e n tp e r f o r m a n c e t oe n h a n c et h eq u a n t u m c o - p r o c e s su n i t se x e c u t i n ge f f i c i e n c y , w eh a v ep r o p o s e dt h ed y n a m i cs c h e d u l et e c h n i q u eo f q u a n t u mi n s t r u c t i o n ，w h i c hr e f e r e n c e st h ei d e ai nc l a s s i cp r o c e s s o lt h i st e c h n i q u ec a ne n h a n c e t h ec o m p u t i n gp e r f o r m a n c eg r e a t l y w ea l s op r o p o s e das e l f - e r r o r - c o r r e c t i o nq u a n t u ms t o r a g e a r c h i t e c t u r e i tr e f e r e n c e st h er e s e a r c ho nq u a n t u me r r o r - c o r r e c t i o nc o d e ，a n dc a l lb u i l dar e l i a b l e s t o r a g es y s t e m b e c a u s et h ed y n a m i cs c h e d u l et e c h n i q u ec a n n o te l i m i n a t et h ed a t ad e p e n d e n c ei nq u a n t u m i n s t r u c t i o n s ，w eh a v ep r o p o s e dap a r a l l e lq u a n t u mc o m p u t i n gm o d e l ( p q c m ) b a s e do nq u a n t u m n e t w o r km o d e lt or e s o l v et h i sp r o b l e m w ea l s oa n a l y z e dt h ep a r a l l e l i s mi nq u a n t u mn e t w o r k ， a n dg i v et h ea n a l y z i n ga n dr e c o m p o s i n ga l g o r i t h m t h i st e c h n i q u ec a ni m p r o v et h ep a r a l l e l i s m i nq u a n t u mn e t w o r ka n dh u ef o rt h ec o m p i l e ro fq u a n t u mp r o g r a m w ep r o p o s e da l lo b j e c t o r i e n t e dq u a n t u mc o m p u t i n gl a n g u a g eq j a v aw h i c hi sb a s e do n j a v a t h el a n g u a g ep r o v i d e sp o w e r f u lc o m p u t i n ga n d d e s c r i p t i o na b i l i t yf o rq u a n t u mc o m p u t i n g 第1 i i 页 国防科学技术大学研究生院学位论文 a l g o r i t h m i ts a t i s f i e st h er e q u i r e m e n t so f q u a n t u mc o m p u t i n g i ti sv e r ye a s yt ou s eq j a v a t o p r o g r a m a c c o r d i n gt ot h ei m p l e m e n t a t i o no f m a n yt y p e so f q u a n t u mc o m p u t i n gs i m u l a t i o ns o f t w a r e s y s t e ma n di t ss t a t i s t i c a lr e s u l t s ，w eh a v es u m m a r i z e dt h er e q u i r e m e n to f s i m u l a t i n gq u a n t u m c o m p u t i n ga n dt h ep r i m a r yt e c h n i q u ei ns y s t e md e s i g n w ed e s i g n e da n dr e a l i z e daq u a n t u m c o m p u t i n gs i m u l a t i o ns o f t w a r es y s t e mq c d k i ti sm u c hm o r ec o n v e n i e n c ef o ru s e rt op r o g r a m ， d e b u g a n dr u nt h eq u a n t u mp r o g r a m i ta l s oc a nb eu s e dt or e s e a r c ha n ds i m u l a t eo nq u a n t u m a r c h i t e c t u r e i nq u a n t u mm e c h a n i c s ，w ec a nu s et h ev e c t o ra n dm a t r i xo p e r a t i o nt oe x p r e s st h es t a t ea n d r e v o l u t i o n t oe n h a n c et h ee f f i c i e n c ya n dp e r f o r m a n c eo f t h es i m u l a t i o n ，w es t u d i e dt h e t e c h n i q u ew h i c hu s e sv e c t o rp r o c e s s i n gt oi m p r o v ei t w ef o u n dt h a tt h ev e c t o rp r o c e s s i n g a c t u a l l ye n h a n c e st h ep e r f o r m a n c ee f f i c i e n t l y d u r i n gt h er e s e a r c h ，w ea l s os t u d i e dt h eq u a n t u ma l g o r i t h m s w ef o u n dt h a tt h e r ea r es o m e p r o b l e m si ng - r o v e r sq u a n t u ms e a r c ha l g o r i t h m ，a n dp r o p o s e da ni m p r o v e dq u a n t u ms e a r c h a l g o r i t h mt or e s o l v et h e m o nt h eb a s i so f t h ei m p r o v e da l g o r i t h m ，w ep r o p o s e dan e w a l g o r i t h m t os e a r c ht h em i n i m u mi nal i s t t h i sa l g o r i t h m st i m ec o m p l e x i t yi sd ( o 5 ) ni st h en u m b e ro f l i s t w ea l s op r o p o s e das e a r c ha l g o r i t h mw i t hd i c h o t o m y t h i sa l g o r i t h mi sm u c h p o w e r f u l i t s t i m ec o m p l e x i t yi so ( ( 1 0 9 n ) o 。) t h e s ea l g o r i t h m sa r es i g n i f i c a n tt or e s o l v et h en p p r o b l e m k e y w o r d s ：q u a n t u mc o m p u t e r c o m p u t e r a r c h i t e c t u r e s i m u l a t i o n q u a n t u ma l g o d t h m ：一：丝些鲨壁垒垒些垡些箜塑鎏一 第一章引言 1 1 研究背景 计算机作为二十世纪最重大的发明之一，充分显示了人类智慧的力量，给世界带来了 巨大的变化。随着计算机应用的发展，人类在不断研究获得更高计算能力的技术，并提出 各种与物理实现紧密相关的新型计算机结构和理论。由于量子计算利用量子系统的本质特 征，与经典计算机技术相比具有很高的计算性能，所以近十年来，它引起了各国的重视。 量子计算的研究主要集中在三个方面：量子计算基础理论研究、量子计算应用研究和 量子计算机实现技术研究。量子计算基础理论研究是整个量子计算研究的基础，它为量子 计算应用和量子计算机实现技术提供依据和指导：量子计算应用研究则为量子计算基础理 论和量子计算机实现技术研究提出了新的要求，推动量子计算基础理论及量子计算机实现 技术的发展。而量子计算机的实现技术为量子计算理论及应用研究提供物质手段。 1 9 9 4 年是量子计算技术发展的重要转折点。在这一年，美国科学家p e t e rs h o r 提出分 解大数质因子分解的量子并行算法n 】，证明了利用量子计算机能够轻易破解现在广泛使用 的公开密钥体系( r s a ) 2 1 ，该算法的速度相对现有经典算法具有指数级的提高。这个重 要成果使量子计算的研究走出低谷，成为国际上科学研究的一个热点。近年来科学家们在 理论和实验上不断取得重大突破，每年 s c i e n c e ) ) 和 n a t u r e 上都有许多重要研究成果 报道。 鉴于量子计算技术的巨大潜力，特别是关系到国家信息安全重大问题，各国政府对其 发展十分关注。美国和欧盟均投入大量人力物力，开展了相关研究工作，如：在美国国防 部门支持下，加卅l 理工大学、m i t 联合南加州大学成立了量子信息和计算研究所1 3 】，其长 远目标是实现量子计算机，近期规划以量子算法、量子网络设计、量子编程、量子模拟的 理论和试验为主；在美国l o sa l a m o s 国家实验室开展了网络量子密码和空闲空间量子密码 传输以及离子阱量子计算等研究工作【4 j ：美国标准和技术研究所( n i s t ) 开展了量子逻辑 门和制备薛定谔量子态的研究【5 j ：s t a n f o r d 大学和i b m 公司合作进行用核磁共振实现量子 计算机的研究 6 1 ；欧盟支持六个国家成立量子信息的研究群体【7 1 ，致力于量子计算、量子 通讯和量子密码的研究。这是继欧盟核子中心和航天技术的国际合作之后，又一规模可观、 针对科技重大问题的国际合作。此外，加拿大、澳大利亚、荷兰、日本等也积极从事这个 领域的研究。更值得注意的是国防部门的高度重视，美国军队研究部门翻r m y r e s e a r c h q 卵c e ) 、英国国防部研究局、北大西洋公约组织都直接支持这个领域的研究。 量子算法的研究做为量子计算应用研究中的一个重要方向，也得到广泛的重视。除了 s h o r 大数质因子分解算法之外，g - r o v e r 又提出了量子搜索算法【8 】等，极大地推动了量子计 算应用技术的发展。从经典计算机的发展过程可以看到，算法和软件技术的研究发展程度 对计算机技术的发展和应用至关重要。 要更好地支持量子计算研究，需要积极开展量子计算机实现技术研究，并针对各种应 第1 页 国防科学技术大学研究生院学位论文 用开展相关的算法研究。 量子计算机的硬件实现目前已有多种方案，比较著名的有离子阱( i o n 砸p ) 方案p 1 u “j 、 腔量子电动力学( c q e d ) 方案 1 2 , 1 3 , 1 4 1 、核磁共振( n m r ) 方案 1 5 , 1 6 和量子点( q u a n t u md o t ) 方案【1 7 】。目前已经实验实现的有前三种。至于是那种方案更有效更适合构造量子计算机， 目前还处于探索中，并没有定论。 离子阱最早是由j i c i r a e 和p z o l l e r 9 在1 9 9 5 年提出的，s t e a n e 1 0 l 在1 9 9 7 年的一篇文 章中作了详细的描述。其结构为：在四根电极上加射频电压，两个端帽上加静电场，在复 合电场作用下，一串( 个) 离子被限制在高真空的线性势阱中，沿阱轴排列。在超低温 条件下，离子的运动可以化为轴向的一维运动处理。选择每个离子的两个内部低位能级提 供一个物理量子位。这样囚禁在阱内的个离子提供了个量子位。对离子态的演化操作 由被分束器和声光调节器分成细束的激光束提供。每一对束照射到一个离子上，控制激光 频率和脉冲持续时间，驱动离子内部态的跃迁，实现对单个量子位的转动变换。当激光束 和第x 个离子( 量子位) 作用时，不仅可能引起这个粒子内部态的跃迁，而且由于将一定 动量转移给这个离子，有可能激发离子串集体振动的声子态。通过选择适当的激光频率、 照射角度和脉冲持续时间，可以选择只激发一个质心模态。这个质心运动就可以充当“公 共汽车”角色，在各离子间传递相互作用，从而实现任意两量子位之间的控制转动操作。 它主要优点是阱中的超冷离子处于一个几乎与外界隔绝的空间中，由环境引起的消相 干主要来源于离子串和电极噪声电压之间的耦合引起运动产生热量，这种效应通常很小。 主要缺点是时钟速度太慢，用数目极大的激光束脉冲操作各个离子执行逻辑运算时，计算 速度难以提高。此外，虽然现在激光技术已经可以把少数离子冷却到超低温下，但要把大 量粒子冷却在阱中也不是很容易做到的事情。 腔量子电动力学方案是在1 9 9 5 年由b a r e n c o 陉】和s l e a t o r l l 3 】等人同时提出的。在s l e a t o r 等人的方案中，量子位由高q 微波腔内的量子化电磁场和两能级原子充当。方案由微波腔 r a m s e y 区和2 能级原子构成。假设腔中最多只能有一个光子，腔场中的态可以由j 0 ) 、1 ) 描述，前者是没有光子的态，后者表示有一个光子的态。原子的两个态可以分别取为b ) 和 i p ，前者表示基态，后者则表示在计算中选用的原子某一激发态。当原子通过腔场时，取 决于腔场的态以及原子运动速度( 决定了原子和腔场作用时间) ，原子态可以发生有条件 的改变，从而实现量子计算需要的条件动力学作用。方案中的r a m s e y 区由经典辐射场组 成，当使用适当场频率和振幅，它可以产生原子两能级系统的任意转动。 腔量子电动力学方案的主要优点是两个量子位之间相互作用的时间尺度远小于离子 阱方案，这样在单位时间内可能完成的操作步骤可以更多。此外方案中描述的原子或离子 与单模腔场的耦合，可以在离子或原子与腔场之间施加量子门运算，从而实现在空间中远 远分离开的量子位之间传递量子信息，这可以用于量子通信中。 量子点方案的原理可简单描述如下：两个量子点分开距离r 并嵌埋在半导体中，取每 个点的基态和第一激发态作为计算基，记为1 0 ) 和1 1 。这两个量子点可以是两个自旋粒子通 过此偶极互相作用：可以是两个电子通过电偶极互相作用，实现量子逻辑门操作。 迄今关于量子点方案的实验进展不如离子阱和腔q e d 方案。目前尚未见到实现两个 量子点之间的控制转动操作的报道，但这个方案明显的优点是量子位可以是嵌入在固体材 料中的固态量子器件，它的设计很容易使人联想到现代经典计算机的大规模集成电路技 第2 页 国防科学技术大学研究生院学位论文 术。 核磁共振方案是由i b m 的i s a a cc h u a n g 、m i t 的n e i lg e r s h e n f e l d 等研究人员在9 0 年 代中期提出的，并在1 9 9 8 年研制了世界上第一台两位量子计算机，2 0 0 0 年研制出了5 位 量子计算机n 8 i ，在2 0 0 1 年底，i b m 发布了研制成功7 位的量子计算机【1 9 1 。7 位量子计算 机采用了含有5 个氟原子的分子c 。h ，e o ：f e ，每个氟原子代表一个量子位。我国的中科院 武汉物理与数学所、中国科技大学在2 0 0 0 年1 0 月实现了基于核磁共振的4 位量子计算机 原型 2 0 1 。 目前的研究情况显示，量子技术具有很大的扩展性 2 1 2 2 。更重要的是，量子纠错编码 技术已经发展得比较成熟 2 3 】，可以使用容错部件将每个量子操作的错误出现概率降到非常 低的水平比如o 0 0 0 1 ，这样在容错部件的基础上，就可以构造可靠的量子计算机。可以说， 实现量子计算机已经没有原理上的障碍了，所要做的就是如何做的更好。 目前的量子计算机研究还主要集中在量子计算机的量子器件实现。要制造出具有高性 价比的量子计算机系统，除了对量子计算机的器件实现技术进行研究外，还需要对量子计 算机体系结构展开研究，并根据量子计算的特点和目前实现技术，采用各种合理方法，尽 可能提高其性能。现在针对量子计算机体系结构的研究还刚刚开始 2 4 , 2 5 ，关于这方面的文 献还很少。 由于目前量子器件实现技术还处于实验研究阶段，因此对量子计算的研究很多都是通 过在传统计算机上通过软件模拟环境进行。这种软件模拟环境可以支持用户进行新的量子 计算模型和量子计算算法研究以及解决多种应用问题。缺点是运行速度慢，对程序运行空 间要求高。但是这种软件模拟虚拟量子计算机通用性好，因而成为量子计算机研究初期能 迅速推广的产品。美国国防部开展了通过并行计算技术实现虚拟量子计算【2 6 1 ，日本东京大 学【”1 等都开展了在经典计算机上进行量子计算的模拟技术。这种软件模拟虚拟量子计算有 代表性产品有；q d d 2 引、q c l l 2 9 1 、m a t h e m a t i c a ln o t e b o o ks i m u l a t i o n 3 0 1 、e q c s 3 ”、u n i v e r s a l q u a n t u mc o m p u t a t i o n 3 2 1 、q u b i t e r t 3 3 1 、p a r a l l e lq u a n t u mc o m p u t e rs i m u l a t o r 3 4 1 、f s m 3 5 等系 统。作者在博士课题研究中，设计并开发了通用量子计算软件开发模拟系统q c d k 。 为了解决软件模拟量子计算处理速度慢、运行空间大的问题，一种实现方法就是构造 量子计算专用并行处理机系统。由于量子门操作之间具有较好的并行性，利用大规模并行 处理系统特有的计算特点，其计算能力比单机软件模拟量子计算机有了明显提高。 另外一种方案就是利用量子计算的特点，结合经典计算机中德向量处理技术，提高量 子计算软件模拟系统的性能。 针对量子计算机体系结构的研究还处于起步阶段，这对我们来说是有利的，在重视各 种基础技术研究的同时，进行量子计算机体系结构的研究，为下一步量子计算机物理实现 打下基础和获取经验，使得一旦量子计算机能够达到实用，就能立即将成果用于其上。 本课题的研究工作正是在这样的背景下提出和展开的。 第3 页 1 2 研究目标 我们的研究目标主要包括以下几个方面： 研究量子计算机的体系结构。在量子计算模型的基础上，研究量子计算机的体系 结构实现方案，分析量子计算机功能部件对量子计算机性能的影响，寻求提高量子计算机 性能的方法。 研究量子计算模拟技术。在经典计算机上用软件模拟量子计算，在量子计算模型 和量子计算机体系结构研究的基础上，研究提高量子计算软件模拟技术的方法。 研究量子算法。研究和开发新的量子算法，为量子计算应用奠定基础。 1 3 研究意义 量子计算机是一种新型计算技术，具有强大的计算能力，有着良好的发展前景。积极 开展量子计算机体系结构的研究具有很重要的意义：首先，量子计算机体系结构研究在国 际上刚刚开始，如果能够找到较好的设计方案，就能在这一领域中处理领先地位，对我国 量子计算机领域的发展具有重要意义。 其次，如果能够有效地提高量子计算软件模拟技术，使之能够满足量子计算研究的需 要，就能够将量子计算机的研究与实际应用结合起来，探讨这项研究的实际应用价值，加 速量子计算机技术的发展。 此外，研究新的量子算法，不断发现量子计算的应用前景，能够推动量子计算的发展。 1 4 主要研究内容 本课题的研究内容主要有： 深入掌握量子计算 为了研究量子计算机体系结构，必须研究已有量子算法，掌握量子计算模型，结合现 有的一些实现技术，提出量子计算机体系结构方案。 研究量子计算机系统体系结构 根据第一阶段提出的量子计算体系结构的方案，分析其各个组成部分对量子计算机性 能的影响，对如何克服量子计算指令相关性、发现量子计算并行性技术进行研究，探索构 造可靠存储系统的方法，分析量子存储系统对量子计算机性能的影响。结合体系结构的研 究结果，确定高级量子计算编程语言，探索量子计算程序的编译优化技术。 设计和实现量子计算模拟系统 研究量子计算模拟方法，分析现有的量子计算软件模拟系统，确定通用量子计算软件 开发模拟系统的技术要求和实现方案，设计一个高效的量子计算程序集成开发环境，并能 够用它进行量子计算体系结构的模拟验证。探索提高量子计算软件模拟技术性能的方法。 研究新的量子算法 第4 页 丝竺墼垒查垒些兰些鲨丝垒一 1 5 主要研究成果 通过对本课题的研究，取得以下主要成果： 提出了协同量子计算机体系结构方案，该方案将经典计算机作为整个系统盼控制 核心，而将量子计算部件作为量子计算协处理器，只负责完成量子计算。在该方案中 借鉴经典处理器中指令并行技术，在量子计算协处理器增加了量子指令动态调度技术； 借鉴量子纠错编码技术，提出了构造可靠的可伸缩量子存储系统的方案。该体系结构 方案增加了量子计算机的指令并行性，并充分考虑了现有实现技术，在保证计算性能 的同时，降低了量子计算机的实现难度。 提出了并行量子计算模型。在量子网络计算模型的基础上，深入分析了最子网络 中存在的并行性，提出了并行量子计算模型，研究了开发量子网络并行性的方法，提 出了量子网络并行化重构算法。该技术可以提高量子网络的并行性，可以用于量子计 算程序的编译优化。 设计了通用量子计算软件开发模拟系统。该系统是一个集开发调试运行为一体的 集成开发环境( i d e ) 。它还能用于量子计算机体系结构技术的研究。具有较好的可扩充 性和可移植性。 为了提高在经典计算机上进行量子计算模拟的性能，研究了使用向量处理部件提 高模拟性能的技术。由于量子计算过程可以使用向量计算模拟，因此适合具有向量处 理的微处理器。研究结果表明该技术可以有效地改进模拟性能。 针对g r o v e r 量子搜索算法存在的不足进行了改进和完善，使其在任何条件下都能 够有效地进行搜索。提出了搜索列表极小值的量子算法，它具有d c 05 ) 的时间复杂度， 为列表个数。在经典二分法的基础上，提出了二分法量子搜索算法，它的时间复杂 度为o ( ( 1 0 9 s ) ”) 。这些算法对于在量子计算机上求解p 问题具有重要意义。 1 6 论文组织 本文共分十一章，具体介绍了本课题的研究背景，涉及的主要研究内容及结论，文章 的组织结构如下： 本章首先简单介绍了量子计算的国内外研究情况，指出了目前量子计算机体系结构研 究面临的问题和前景；讨论模拟技术在量子计算研究中的意义；最后对本课题的研究目标、 意义、研究内容进行了简要的说明，并介绍了论文的组织结构。 第= 章简单介绍了量子计算中所涉及的量子力学基础理论：阐述了量子计算中的基本 概念，如量子位及其特点、量子态的演化和量子门等；介绍了量子计算的向量表示方法； 然后简单说明了一个量子计算模型量子网络模型。 第三章中首先分析了量子计算基本过程和量子计算中程序的控制流程；提出了协同量 子计算机体系结构方案，介绍了它的各个功能部件的构成和主要功能，给出量子计算基本 指令集；探讨了该体系结构方案的物理实现基础：介绍了该方案中的编程语言和编译器； 最后对量子计算中的典型算法进行了模拟分析，分析比较了该方案与其它实现方案的性能 第5 页 国防科学技术大学研究生院学位论文 与特色，证明了该方案的可行性和有效性。 第四章在协同量子计算机体系结构方案的基础上，分析了量子计算程序中存在的指令 相关性及其对计算机性能的影响；借鉴经典处理器中解决指令相关性的技术，结合量子计 算指令的特点，提出了量子指令动态调度技术。给出了具体的实现方案：最后对量子计算 中典型算法进行了模拟分析，结果表明该技术可以有效提高量子计算机的性能。 第五章中研究了量子网络中量子门之间的并行性。首先利用量子计算中纠缠态的概 念，提出了量子网络并行化的三个定理：然后在量子网络模型基础上，研究了其中存在的 相关性和并行性，提出了并行量子计算模型p q c m ，并给出了从一般量子网络中开发量子 并行性的算法；最后对量子计算中典型算法进行了模拟分析，结果采用该算法可以有效地 提高量子网络中量子门之间的并行性，从而提高量子计算程序的性能。该技术可以用于量 子计算程序的编译优化，为量子计算静态调度奠定了基础。 第六章介绍了量子系统中可能发生的错误类型和量子纠错技术，借鉴经典计算机存储 系统中存储单元的设计思想，提出了在协同量子计算机体系结构中构造可靠的可伸缩量子 存储系统方案，并介绍了该方案中各个功能部件的工作原理和流程。研究分析了提高量子 存储系统的可靠性的方法以及由此对计算机系统带来了性能影响。 第七章在分析量子计算特点和已有量子计算语言的基础上，总结了量子计算编程语言 设计需求，结合j a v a 编程语言，提出了一个面向对象量子计算编程语言q j a v a ：讨论了该 语言对量子计算的支持，介绍了用该语言进行量子计算编程的方法。最后还初步探讨了量 子计算语言编译的一些问题。 第八章中广泛分析了现有的量子计算软件模拟系统的设计目的和特点，总结了量子计 算软件模拟系统的需求，探讨了构造通用量子计算软件模拟系统的需求和技术方案。在分 析总结的基础上，设计实现了通用量子计算软件开发模拟系统q c d k ；介绍了该系统的总 体结构和设计方案。最后简单介绍了其功能实现。 第九章介绍了经典计算机中的向量处理技术，结合量子计算与向量运算之间的关系， 研究了向量处理部件对量子计算模拟系统的支持。最后结合国防科技大学计算机学院设计 的带向量处理功能的微处理器银河t s 1 ，针对典型的量子计算算法，模拟分析了向量处理 技术对模拟量子计算的性能影响。 第十章介绍量子计算中的典型算法_ g r o v e r 量子搜索算法，分析了其存在的不足之 处：然后针对这些不足，提出了改进的量子搜索算法，并对其进行了性能分析：在改进搜 索算法的基础上，提出了求列表极小值的量子算法，分析了该算法的时间复杂度：在已有 量子搜索算法的基础上，借鉴传统的二分法思想，提出了二分法量子搜索算法，分析了该 算法的时阃复杂度和空间复杂度，证明了该算法的性能相比原有的算法具有极大的提高。 第十一章总结了本文的全部工作，归纳了本研究的主要贡献，指出了现有工作中存在 的主要问题，并对下一步工作进行了说明。 第6 页 第二章量子计算基本概念 在本章中，首先简要介绍了量子计算中用到的量子力学基本原理，正是这些量子力学 原理使得量子计算具有强大的计算能力。随后介绍量子计算中的一些基本概念3 6 l ，包括量 子位、量子门等。由于量子力学中可以使用h i l b e r t 空间描述量子系统状态和演化，所以还 介绍用h i l b e r t 空间描述量子计算的基本概念和方法。 2 1 量子力学基本原理 量子力学是一门相当成熟的学科，已经形成了完整系统的理论。它的全部内容可以从 少数几个基本原理出发，用逻辑推理的方法推演出来，而这些内容被公认是为正确、无可 怀疑的。下面介绍几个基本原理【3 刀。 【原理1 】描写微观系统状态的数学量是h u b e r t 空间中的矢量相差一个复数因子的 两个矢量，描写同一状态 量子力学中通常用归一化的右矢l 泖或者左矢( 纠描写系统的状态，称此状态为状态妒 而表示量子态的矢量f 协一u 、y 1 1 3 8 】称为态矢( s t a t ev e c t o r ) 。符号f ) 是d i r a c 符号。h i l b e r t 空间 就是态矢张起的空间，在量子力学中称为态矢空间。 由于在量子力学中，与粒子相伴的波函数的模平方具有概率密度的意义，波函数本身 并不表示概率，而且由于它是复函数，它不表示任何物理量。在量子力学中引入了概率幅 ( p r o b a b i l i t ya m p l i t u d e ) 使量子力学根本上区别于任何经典统计。著名物理学家f e y n m a n 称概率幅的概念是量子力学中最基本的概念之一1 3 。通常采用复数表示概率幅。它的实部 和虚部的平方和，也就是模的平方，就是概率。 态矢的物理意义就在于能对它描述的系统实施测量的结果概率分布做出预言。一方面 态矢记录了系统制备的信息，使不同的态对测量结果作出不同的响应。另一方面，不同态 对测量结果作出不同的响应，说明不同的态具有不同的物理性质，一个态物理性质的辨认 需要多次重复测量实现。测量过程将引起态的不可逆变化，它实质上是新态的制备过程。 只有对相同态的多次重复测量，得到力学量可能值的概率分布，才能描述态的物理性质。 态矢中包含着一个或几个力学量实现某些特定值潜在可能性的全部信息。在这个意义上， 态矢完全描述了量子系统。 【原理2 】态叠加原理( p r i n c i p l e o f s u p e r p o s i t i o n ) - 若量子力学系统可能处在i 狮 和i 忱 描述的态中，线性叠加态f 伊c l i 惭 忉2 i 忱) 也是系统的一个可能态，其中c l ，c 2 是复数 量子力学态叠加原理与经典物理中的波叠加原理虽然形式相同，但二者意义有