（计算机软件与理论专业论文）基于量子可逆计算线路模型的量子线路仿真.pdf

东南大学硕士学位论文 摘要 - 上世纪中叶，人们发现能耗会导致计算机中的芯片发热，极大地影响了芯片的集成度， 限制了计算机韵运行速度。研究发现，能耗来源于计算过程中的不可逆操作。量子计算机的 概念就源于为解决计算机能耗问题而开展的可逆计算机的研究，即能否为经典计算机找到一 种对应的不影响运算能力的可逆计算机。 量子计算机不仅能够模拟量子系统，而且能够利用量子并行计算的优势为经典计算机中 的n p 问题设计多项式时间的算法。本文采用量子计算研究中最具代表性的电路模型模拟量 子计算过程，构建了量子信息与计算的仿真平台雏形。实验平台采用新的量子寄存器结构作 为存储媒介，在空间性能上优于早先的矩阵存储形式：将量子逻辑门对量子基矢的作用直接 映射为位之间的逻辑关系，避免了大量乘法运算的时间。平台的首要目的是模拟两个重要的 量子算法_ d e u t s e h 算法和量子f o u r i e r 变换的演算，并利用量子f o u r i e r 变换的结果来实 行大数因式分解。通过实验及仿真结果说明了基于逻辑位的操作优于基于矩阵运算。平台的 第= 目的是进行量子布尔电路的规范形式化简，根据规范形式量子布尔电路的定义，引入了 化简规则，改进了电路规范化简算法，降低了电路的规模。 关键诃：量子计算，d e u t s c h 算法，量子f o u r i e r 变换，量子布尔电路，规范化筒 东南大学硕士学位论文 a b s t r a c t i nt h em i d d l eo fl a s tc e n t u t mi tw a sf o u n dt h a tt h ee n e r g yc o n s u m i n gm a d et h ec h i p si nt h e c o m p u t e rf e v e rw h i c hi n f l u e n c e dt h ei n t e g r a t i o nd e g r e eo f o h i p sg r e a t l ya n dr e s t r i c t e dt h ef u n c t i o n s p e e do f t h ec o m p u t e r s r e s e a r c h e ss h o w e dt h a tt h ee n e r g yc o n s u m i n gc f l m af r o mt h ei r r e v e r s i b l e o p e r a t i o n sd u r i n gt h ec o m p u t i n gp r o c e s s e s t h ec o n c e p to fq u a n t u mc o m p u t e rr o o t e di nt h e i n v e s t i g a t i o n so fr e v e r s i b l ec o m p u t e r sf o rr e s o l v i n gt h ee n e r g yc o n s u m i n gp r o b l e m s n a m e l y w h e t h e rw ec o u l df i n dak i n do fc o r r e s p o n d i n gr e v e r s i b l ec o m p u t e rt h a td o e s n ta f f e c tc o m p u t i n g a b i l i t i e so rn o t q u a n t u mc o m p u t e r sa r ec a p a b l eo fn o to n l ys i m u l a t i n gt 1 1 eq u a n t u ms y s t e m b u ta l s ou s i n g t h ea d v a n t a g eo f q u a n t u mp a r a l l e l i s m t o d e s i g np o l y n o m i a l t i m e a l g o r i t h m s f o rt h e n o n - d e t e r m i n i s t i cp o l y n o m i a lp r o b l e m so fc l a s s i cc o m p u t e r s t h i sa r t i c l ea d o p t e dt h ec i r c u i t m o d e l - 地m o s tr e p r e s e n t a t i v em o d e li nq u a n t u mc o m p u t a t i o nr e s e a r c h e s - t os i m u l a t et h e q u a n t u mc o m p u t a t i o np r o c e s s e s c o n s t r u c t e dt h er u d i m e n ts i m u l a t i o np l a t f o r mo fq u a n k n n i n f o r m a t i o na n dc o m p u t a t i o n t h e e x p e r i m e n t a lp l a t f o r r i li n t r o d u c e dt h eq u a n t u mr e g i s t e r s t r u c t u r et ob et h es t o r a g em e d i u m ，w h i c hi sb e t l e rt h a l lt h ee a r l yf o r n lo fm a t r i xi ns p a c ea n d m a p p i n gt h ef u n o t i o nt oq u a n t u mb a s es t a t e so f 血eq u a n t u m1 0 9 i cg a t e sd i r e c t l yt ot h el o g i c a l r e l a t i o n s h i p sb e t w e e nb i t s ，w h i c ha v o i d s 恤em a s st i m ef o rm a t r i xm u l t i p l i c a t i o n s t h em a i n p u r p o s eo ft h ep l a t f o r i l li st os i m u l a t et w oi m p o r t a n tq u a n t u ma l g o r i t h m s _ m ed e u t s c h s a l g o r i t h ma n dt h eq u a n b a mf o u r i e rt r a d s f o r i n 一a n du s et h er e s u l t so fo u a n i n l mf o u r i e r t r a n s f o r mt oc a r r yo u tf a c t o r i n g t h ee x p e r i m e n t sa n dt h er e s u l t ss h o w e dt h a tt h eo p e r a t i o nb a s e d o nl o g i c a lb i t sw e r eb e t t e rt h a nt h em a t t i xo p e r a t i o n t h es e c o n dp u r p o s eo f 也ep l a t f o r mi st o p r e d i g e s tt h ec r i t e r i o nf o r mo fq u a n t u mb o o l e a nc k c u i t s a c c o r d i n gt 0t h ed e f i n i t i o no ft h e c r i t e r i o nf o r mo fq u a n t u mb o o l e a nc i r c u i m ，w ei n t r o d u c e dt h ep r e d i g e s tr u l e s ，i m p r o v e dt h e a l g o r i t h r no f c r i t e r i o np r e d i g e s to f c i r c u i t sa n dr e d u c e d t h es c a l eo f o u a n t u m b o o l e a n c i r c u h s k e yw o r d s ：q u a n t u mc o m p u t i n g , d e u t s c h sa l g o r i t h m ，q u a n t u mf o u r i e rt r a n s f o r m ，q u a n t u m b o o l e a nc i r c u i t s ，c r i t e r i o np r e d i g e s t 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他入已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：至筐焦e t 期：丝! z ：! 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 随乡 期： 第一章引言 i 1 研究背景 第一章引言 现代计算机早期是由电子管和继电器组成的大型物理设备，其执行运算的速度仅比人类 快几倍。之后，数字计算机使用晶体管和集成电路工艺，显著降低了电路的体积和能耗，大 幅度提高了运算速度。随着工业技术的日益发展和工艺水平的不断提高，大规模集成电路和 超大规模集成电路应用到现代计算机中，使得每一块集成电路上晶体管的数量按m o o r e 律 急剧增长。集成度若按此速率持续增长，那么在不久的将来晶体管的尺寸将从微米级降到纳 米级；科学家们预计到2 0 1 0 年晶体管的尺寸将降至7 0 纳米左右。实际上，c m o s 技术的 极限是2 0 纳米，一旦低于该界限，c m o s 晶体管将不会按照当初设计时所预计的方式工作， 电路中的电子将遵循量子力学原理表现为波，干涉和叠加效应将成为主导h j 。量子计算机是 现代计算机小型化的趋势，它的设备足够小，行为由量子力学支配。较之经典的数字计算机， 量子计算机在计算能力、存储能力、和现实世界的仿真能力上将有更加出色的表现【2 i 。 自八十年代始，开展了许多关于量子计算机的研究。1 9 8 2 年，r i c h a r df c y n m 锄9 】观察到 在经典计算机硬件上模拟量子过程似乎需要超指数级的存储空间和运行时间。因此， f e y n m a n 提了量子计算，这是一种涉及到量子力学状态的计算途径，原则上可以更有效地 模拟其他量子系统。因此，量子仿真成了实现量子计算机的第一步。1 9 8 5 年，d a v i dd e u t s c h t q 将量子计算机的高处理能力与经典计算机比较，他通过量子电路和通用量子计算机( 量子图 灵机) 的开发，描述了量子计算机的一般模型，发展了量子计算理论。d e u t s c h 和其他一些 物理学家认识到，一个数学问题的算法复杂性的p 与 i p 分类( 多项式时间算法与非多项式时问 算法) 没有绝对性i ，j ，而在此之前人们一直认为这种分类不依赖具体使用的计算系统。正是 这个发现，使得量子计算的研究开始受到关注1 9 9 4 年，s h o r l 6 发布了他在多项式时问内解 决大数因式分解问题的量子算法，彻底打破了量子计算的僵局，从此，量子计算的研究进入 了高潮，许多量子算法接踵而至，比如g r o v e 一”的非结构化数据库的信息搜索算蝴s h o r 的量子纠错算法p 1 等。科学家和研究机构就量子信息技术的各个方面做了各种探索 1 2 研究现状 现今，世界各地的大型科研机构对量子计算机的研究投入了极大的热情。i b m 研制出了 核磁共振量子计算机，并正致力于j o s e p h s o nj u n c t i o n 量子设备的研究。n e c 实验室也制 成了量子计算机的基本电路，利用氧化铝置备电路，在近于绝对零度的极低温条件下，控制 处于超导状态的电子，成功完成了预定运算程序。同时，以c a m b r i d g e 和m a s s a c h u s e t t s 为 基础的技术小组开发了世界首个量子密钥分发( q k d ) 网，提供量子密码系统；n t t 实验室 专注于量子密码系统协议的研究”。 加拿大的d - w a v es y s t e m s 为量子最优化算法和量子物理仿真建造了超导可编程的定制 集成电路，主要用于密码分析、军事后勤、复杂生物资料分析及其他，该集成电路为量子计 算系统提供更强更快的传送和执行。l o sa l a m o s 国家实验室正在研究量子光学远距离可靠 通信和卫星通信的o k d ，同时还领导量子纠错，脱散、量子隐形传态和量子信息处理的n m 啾 技术改进等工作。研究小组还致力于信息处理中的纳米级量子光学；无线和光通讯超导数字 电路的研发；用于量子信息处理的验证、精确测量、动态过程控制和纳米技术的量子比特处 东南大学硕士学位论文 理器原形等的研究 现今的量子物理技术和计算机技术要能够构造处理足够多位量子比特的应用层面的量 子计算机还存在不小难度，虽然可以利用已经研制出的量子计算机雏形运行g o v e r 算法和二 比特的d e u t s e h 算法，但其他问题，比如可量测性、脱散和可控性等还未根本解决，量子计 算机仅能在实验室环境下工作。正因为实现量子计算机困难重重，而量子计算机的实现必将 为信息科学与通信技术带来革命性的突破，所以有关量子计算的模拟以及量子计算机的模拟 研究应势而生。构造模拟器的主要任务是建造物理系统的模型，在系统的数理描述层面上模 仿计算机的操作脚【6 lc 7 】。 对国内外现存的几十种量子计算模拟器的研究及综合分析可知，模拟器的基本目的都是 为量子计算建模，仿真一种或几种己知的量子算法。但是模拟器还有其重要的第二目的，例 如，q u a n t u mf o g 也着眼于显示量子b a y e s i a n 网络的应用；q c l 尝试为量子计算机写一个高 级的系统结构独立的编程语言；q c d k 提供了一个与硬件无关的、通用且完备的量子算法开 发平台；f s m 研究有限状态机在量子计算机中的有效性；p a r a l l e lq u a n t u mc o m p u t e r 模拟器 针对冷离子阱模型研究了量子计算中可能发生的错误；o p e n q u b i t 厕j 着眼于证明s i l o r 的因式 分解算法和它在量子计算机上的性能，然后将代码扩展到更通用的允许其它量子算法实现的 a p i 上；l g f 2 和量子计算机模拟器研究专门用于发现优于经典的量子算法的遗传编程系统 ( l g p 几g p 2 ) ，用来评价进化的量子算法的合适性，并通过自动编程技术自动生成新的算 法：等等。决大多数的模拟器都仿真了s h o r 算法，有少数仿真了g l - o v e r 算法或是单从硬件角 度模拟电路及量子逻辑门的构造。其中值得一提的是功能较完整的m a t h e m a t i e an o t e b o o k 模 拟器，它使用直观的量子系统和d i r a c 表示法工具，具有r s a 公共密钥密码系统，分析了干 涉作用，仿真了量子纠错雨q f e y n m a n 量子计算机，以及量子隐形传态，对因式分解的困难性 作了举例证明【l o i 。 1 3 研究目标与内容 本文的目标是建立一个基于电路模型的量子计算仿真平台，模拟d e u t s e h 算法和量子 f o u r i e r 变换，同时，建立仿真平台的第二目的是对量子布尔电路进行规范形式的化简，电 路的自动生成与模板匹配。本人的主要工作是仿真平台的设计，包括量子态的存储、表示和 演化，在量子态上施加量子逻辑门变换的可视化，量子f o u r i e r 变换的实现及其与近似量子 f o u r i e r 变换的对比分析，量子f o u r i e r 变换应用于特定数的因式分解模拟，d e u t s e h 算法 的实现以及量子布尔电路的规范形式化简。平台在量子状态表示和逻辑门的运算上具有一定 的优势。 本文主要阐述基于电路模型的量子计算仿真平台的设计与算法仿真。全文共分为五章。 第一章介绍研究背景及量子计算机的研究现状；第二章介绍基于电路模型的量子计算中著名 的d e u t s e h 算法和大数因式分解算法，其中量子f o u r i e r 变换是因式分解这一经典n p 问题 有多项式时间解法的关键技术；第三章介绍量子布尔电路的规范形式化简，并改进了算法， 降低了化简过程中的电路规模；第四章对量子计算仿真平台的设计思路和算法作了详细阐 述；第五章给出了仿真d e u t s e h 算法，量子f o u r i e r 变换，特定数因式分解和布尔电路化简 的实验结果与分析；第六章对本文的工作进行总结并对未来的研究工作提出展望。 第二章量子计算和算法 第二章量子计算和算法 本章介绍基于电路模型的量子算法。d e u t s c h 算法和大数因式分解是量子计算研究领域 的两个重要里程碑，其中解决因式分解问题的一项关键技术一量子f o u r i e r 交换是部分经 典n p 问题在多项式时间内可解的核心。 2 1 概述 经典计算机求一个函数的值：n - b i t 的输入产生由输入难一决定的m - b i t 的输出，即对特 定的n - b i t 参数求解，： o 1 4 寸 o ，l 。一个有m - b i t 值的函数等价于m 个函数，每个函数 有一个比特的值，所以计算机的基本任务就是求解，： o ，1 1 专 0 , i 。该函数有2 打个输入， 2 种可能的输出，所以将n 比特映射为l 比特有2 7 个函数。将输入表示成二进制形式 j = 玉南焉毛，如果j 使( x ) = 1 ，那么，的补集使例( x ) = 0 。 函数，( x ) 的计算用到了基本逻辑运算o r ，a n d ，n o t ，同时还隐式用到了 c o p y ：j 斗“运算。为了缩小逻辑集合，定义了n a n d ( n o ta n d ) 运算 x 个y f x y 1 = f 曲v ( y 1 ，那么利用c o p y 和n a n d 就可以执行n o t ，o r ，a n d 操 作，所以n a n d 和c o p y 对任何函数都是完备的 我们应用n a n d n o t 门可以对任意的函数： o ，1 4 一 0 , i 求值。这一结论产生了计 算的电路模型。计算是一串确定的逻辑操作，如c o p y ，n o t 、a n d 、o r 的序列( 称为电 路) 作用于特定的输入比特串的行为。计算的结果是所有基本操作执行完后剩余比特的最终 状态。在经典电路中，逻辑操作用逻辑门来表示，它负责处理信息，把信息从一种状态变换 到另一种状态，是不可逆的变换，而不可逆的逻辑操作会消耗信息，所以不可避免的有能耗 支出。 在量子电路中，量子逻辑门对任意函数的求值为：，： o ，1 斗 o ，l r ，每一个输出都有 唯一的输入与之对应，因此可以从输出逆推到输入。经典电路与量子电路存在本质上的区别： 首先，量子电路不允许出现回路，即量子电路是无反馈的；其次，经典电路允许连线汇合， 即扇入操作，导致单连线包括所有输入位的按位或，这是不可逆的操作，因此不是酉操作， 所以量子电路中不允许出现扇入；最后，由单连线到多连线的操作，扇出，即产生一比特的 多个拷贝也是量子电路不允许的。 2 2 量子计算 经典计算机是由包含连线和逻辑门的线路建造的，类似地，量子计算机是由连线和量子 逻辑门的组合捧列而形成的处理量子信息的量子线路建造的，量子计算研究中最具代表性的 模型之电路模型就是基于这样的量子线路基础。 东南大学硕士学位论文 2 2 1 量子状态信息表示法 在经典计算机中，二进制信息以比特( b i t ) 形式存储，物理上是一个在电晶体电子电路 中的电压信号；数学上，一个b i t 表示成一个布尔值或变量。在量子领域，二进制信息以量 子状态形式存贮，比如光子的偏振( 水平的垂直的) 、围绕单个原子的电子的两种状态( 基 态激发态) 或均匀电磁场中电子原子核的自旋( 向上向下) 【“】不同于经典b i t ，一个量 子比特或者说q u b i t 能够以其经典b i t 的一个叠加态的形式存在，任何外界刺激都会扰乱该 叠加态，大多数情况是破坏该状态( 典型的破坏如测量操作) 。 经典比特的状态是两态系统，即要么是0 要么是l ；在d i r a c 符号系统中，量子状态表 示成i o ) 和1 1 ) ，它们是两个独立的极化状态，以这两个独立态为基矢，张起一个二维复矢量 空间。与经典信息的状态必不会在0 、1 之外不同，量子比特的状态能够落在l o ) 和1 1 ) 之外， 由一个二元向量形式的线性组合 i ) = 口l o ) + 卢1 1 ) ( 2 1 ) 来代表，称为叠加态，其中口和是复数且满足归一化条件蚓2 + i 矧2 = 1 ，一个q u b i t 就是 一个二维h i l b e t t 空间。我们无法通过测量手段确定一个q u b i t 的状态，也就是无法得到口和 3 的值，我们只能得到量子状态的有限信息，即测得0 的概率是l a f ，测得l 的概率是l 所。 一个量子比特( 如等式( 2 1 ) 所示) 也可改写为 od、 i y ) = i s 詈l o ) + s i n 詈卢1 1 ) i ( 2 2 ) 二 其中不具有可观测性，因此可以略去，由p 和矿定义了三维单位球面上的一个点。这个 球面通常被称为b l o c h 球面，这种直观的想象仅限于单比特而已，如何将b l o o h 球面推广到 多量子比特目前尚无人知晓。 假如有两个量子比特，对应于经典态的0 0 、0 l 、l o 和1 1 ，这个双量子比特有四个基矢： 1 0 0 ) 、1 0 1 ) 、1 1 0 ) 和1 1 1 ) ，同时它也可以处于这四个基矢的叠加，该量子状态包含相应基矢 的复系数，也称为概率幅，双量子比特的状态向量为 l y ) = 岛i o o ) + q 1 0 1 ) + 岛i l o ) 十c 3 1 1 1 ) ( 2 3 ) 量子力学的基本原理指出这些单独的状态向量可以通过张量积的形式和其他状态向量结合 起来。通过张量运算的q u b i t 状态本身就蕴涵了一种大规模并行计算的方法，因为叠加态允 许一个n 量子比特的状态 i 力= 二1 c f1 4 ，。岛，：，6 f 。)( 2 4 ) 同时存储r 个二进制数，每一个q 都是一个复数且满足条件：? kj 2 = 1 ，并且 6 f ，。岛，- 2 ，是i 的二进制展开”“ 2 2 2 量子逻辑门 逻辑门负责信息处理，把信息从一种形式转换为另一种形式。酉性是量子逻辑门的惟一 限制，每个酉矩阵都定义一个有效的量子门f 1 2 】。基本的量子门按涉及到的比特数分为两类： 单比特量子门和多比特量子门。我们在后续的讨论中涉及到的单比特量子门是h a d a m a r d 门 和p h a s es h i f t 门( 用足来代表) ；多比特量子门是c o n l r o l l v d - n o t 门，c o n l r o l l c d - p h a s es h m 门、s w a p 门和t o 伽门删门的作用是把i o 变换到l 。) 和1 1 ) 的中间状态也学， 第二章量子计算和算法 而把1 1 ) 同样变换到j 0 ) 和1 1 ) 的中问状态监 ；盥，我们把地i d m a r d 门认为是d r ，但 、，2 h 2 = j 而不是n o t 门。p h a s es h m 门和c o n t r o n e d - p l s es h i f t 门的作用都是使量子态的相 位偏转，不同的是后者要求控制比特为1 1 ) 。c o n t r o u e d - n o t 门是控制反转门，即当控制i t ；特 为1 1 ) 是，受控比特的状态由1 1 ) 反转到i o ) 或由1 0 ) 反转到1 1 ) ；而s w a p 门则是由三个 c o n t r o l l e d - n o t 门组成的，其作用是交换两量子比特的状态。t o f f o l i 门的一般形式是m 个控 制比特端控制n 个受控比特端，但常用形式则是两个控制端控制一个受控端的形式。部分逻 辑门的酉矩阵及对应的图符号如表2 1 所示： 表2 1 逻辑门及相应的电路图符号表示 - - e f - 日= 铷1 。 j 1 00 0 = 0 。01 匝卜_ 墨= 如 0 oo j r l 0 00 r l 0 0 0 五c = 蚓主 脚= l ：? 。1 ：j 【0 01 0 j l o 0 0 1 j 对于任意的状态l 刁陟) l z ) 分别使用日门、最门、c p 门、c 门、s w a p 门和t o f f o l i 门 分别得到： 2 3d e u t s c h 算法 茗) 屿击( ( 一l + 1 1 一对) 刁j q p 舻i 对 寸i 力! 垒斗印加”i 动l 力 圳) ，) j o 俐y o z ) 刁i 力斗i 力i 刁 圳圳z ) 盟- 俐) ，) k o 功 ( 2 5 ) 量子计算机可以等效为一个量子图灵机。量子图灵机是一个抽象的数学模型，理论上已 证明，量子图灵机可以等价为一个量子逻辑电路 4 1 。因此可以通过量子逻辑门的级联和组合 构成量子计算机。d e u t s e h 深入研究了量子电路与量子图灵机，发展了量子计算理论，实现 了第一个量子算法峨解决了如下的d e u t s e h 命题：“对一给定的函数，( 石) ，通过执行最少 的计算次数来判断该函数是常值函数( 1 ( o ) = ( 1 ) ) 还是平衡函数( ( o ) f ( 1 ) ) ”在经 典模式下至少需要计算两次，而在量子计算机上仅需计算一次 东南大学硕士学位论文 对 a ) 砷 口o ，( 力) 倒2 id e u t s c h 算痃逻辑不慈图 d e u t s e h 算法将量子并行性和干涉结合了起来，图2 i 所示的量子电路是d e u t s c h 算法的 核心，它操作b ) i 口) ，保持卜) 不变，而另一f n ) 变化到a 与厂( x ) 的模2 的和 蚓。) j - 俐a o ( 刁) ( 2 6 ) 令l 口) = 百1 ( 1 0 ) - 1 1 ) ) ，则 v z u ：i j ) 击( i o ) - - 1 1 ) 叫工) 击0 0 ( 9 ，( 坳一i l 。，( z ) ) ) 叫x ) 击2 2 ( i f ( x ) ) - 1 1 ( 9 厂( 勘) 如果( 功= o ，则去0 ，【刁卜i l o 厂【坳) = 去( i o ) - 1 1 ) ) v 如果( 功= 1 ，则老o ，( x ) 卜i i ( 9 八力) ) 2 万1 ( 1 1 - - i o ) = 一a ( 1 0 ) - 1 1 ) )二v 删朋 i x ) - 去2 2 ( i o ) - 1 1 ) ) - ( - 1 ) “1 d 击印) 删 令i 曲= 西10 。睁1 1 ) ) ，则 u 击( i 啪1 1 ) ) 击( i 。卜| 1 ) ) 斗击( ( _ 1 ) “1 0 ) + ( _ 1 ) “1 ) 1 1 ) 击o o 卜1 1 ) ) 对( ( 一1 ) 巾io ) + ( 一1 ) ，1 i1 ) ) 进行一组测量，将其投影到基上 若i + ) = 击。昕| 1 ) ) ， 若l - ) = - - 去2 ( 1 0 ) - 1 1 ) ) ， 比较知，( o ) = ( 1 ) 比较知，( o ) ( 1 ) 图2 2d e u t s c h 算法的量子电路 据此我们可以得到如图2 2 所示的d e u t s c h 算法的量子电路。 计算初始时，量子寄存器内状态设置为i o ) 1 1 ) ；经过h a d a m a r d 门后量子处于了叠加态 d 与阳 陪 然后采用i j 运算( 在我们的模拟平台中目前利用的是c n 门具体实现u 运算) ，得到 隧 陪 一 再对高位应用砘吐吼a r d 门， 如果( o ) = ，( 1 ) ，那么 士 警 警 ( 彩 硼) 士l i l o 压- i i 铡舯堋) 第二章量子计算和算法 警 警 与圳， 警 如果，( o ) ( 1 ) ，那么 士0 ) - 1 ) 警 与堋， 警 最后，我们测量两位量子比特的高位，若厂( o ) = ，( 1 ) 则结果为1 0 ) ，若，( o ) ，( 1 ) ，则 结果为1 1 ) 。 2 4 量子f o u r i e r 变换 考虑解决个复杂问题，最重要的方法之一是把复杂问题分解或变形为多个其他解法已 知的问题离散f o u r i e r 变换就是其中之一。d f t 以一个复向量而，却一lh 输x ，输出为 ，妇一- ：儿；而in 刍- i 刁矿彬胁 ( 2 7 ) 量子f o u r i e r 变换就是由此演化而来。 2 4 1 完全量子f o u r i e r 变换 量子f o u r i e r 变换定义为在一组标准正交基i o ) ，i n 一1 ) 上的一个线性算子，作用 于基矢的变换为i l w ： q f t n ：i ，) _ 专e 2 “朋i 磅 ( 2 8 ) 等价地，作用于任意矢的变换为： 瞩：_ i ) 寸1 导_ 口埘舯i 七) = 导儿i 七) ( 2 9 ) i - 0 vt l o t - o胛- o q f l r 是h i l b c r t 洲酉变换，是量子算法解决相位估计【“、求阶问题嘲、离散对数【l q 、 因式分解【1 q 和隐含子群【1 7 l 等问题的关键。我们在构建量子电路实施q f r 时，需要两种形式 的基本量子逻辑门：一是h a d a m e r d 门，日，表示将该h 门作用于着耵位量子比特；二是 c o n t r o l l e dp h a s e ：s h i f t f l ( c 表示第k 位量子比特作用于鳓位上，让第，位的相位发生偏 转) ，也可以用受控酉门冠表示( 矩阵表示见表2 1 ) 令n = 丁，”是线路的量子比特数， x 口q f t n 中的，卅州7 项进行分析，e 2 a # 2 是关硼期变化的，周期为丁， 钌，礴换为二 进制数形式【1 4 1 ： j = j j ：五= ( r 4 + 五2 。- 2 + + 五2 0 ) ( 2 1 0 ) j | = 皇吒屯= ( 毛2 “+ 如2 ”2 + + 毛2 0 ) ( 2 1 1 ) 筹；吉【毛- 2 ( 2 矗- l + 五2 神+ + 厶) + 屯2 - 2 ( 五2 - t + 矗2 扩2 + + ) + + ( 丁4 + 五2 “+ + ) 】 ( 2 1 2 ) = 毛( 誓) + 乞( 参+ 等) + ( 多+ 争+ 鲁) + 掣 当善月时，( p 2 舻r = 1 ，o ( 2 1 项对变换不起作用。 东南大学硕士学位论文 引入符号皇一。以，参+ l 笋- - - , o j j 一t ，争+ 等+ 等- , o l l t 如， ：售= k j 3 + k ：译文j o + - - - + k 文j 。秘 2 专钆k = 0 2 础附2 古p 刎珊砒( o 舶卜吨( o 撕n 旧 亿埘 = 专p 2 蚋i 毛) 9 p 2 啦0 抽j 屯) 。固口2 吨山”i 毛) 其中每个z ，与可取值。或l ， 当局= o 时，“q o 抽”山川o ) = i o ) 当毛= 1 时，e 2 m 巾批”锄= f 砷舶“锄) 1 1 ) 最终我们得到q f 瓦( n = 2 4 ) 的展开式： q ：= 专( f o ) + e 训1 1 ) ) ( f 0 ) + 4 批) f i ) ) ( f o ) + 卿撕1 1 ) ) ( 2 1 4 ) 图2 3 所示的就是n 位量子比特的q 刀；，它按照 ( q 是r ) ( 也是r 。) ( 风。恐) ( 珥) ( 2 1 5 ) 的序列构建，每个括号内的符号序列表示该位的逻辑门阵列i 五) 经过7 k l + c o n t r o l l e d p h a * s h m f ( 即受控墨门) 和一个m d a n l a r d 门，i 五) 经过了 o 个受控墨f l 和- - + h a d a m a r d 门，i 工) 经过了一个h a d 锄a r d 门，所以图2 3 所示的q 变换电路共用了 。+ n - 1 ) + + 1 ：! 尘竽个量子逻辑门，而q f 乃变化后还需要有2 l 詈1 个s w a p 门用于电路 重排，故共应用了! 掣+ 2 l ；1 个量子逻辑门，复杂度为d ( 一z ) | o ) + ，“i i ) l o ) + ，“吣 i o ) + ，“f 1 ) j o ) + ，讯“l 磅 图2 3啦量子比特q f t n 电路逻辑图，没有给出电路末端逆转量子比特顺序的 钿a p 门和输出的l 压归一化因子 2 4 。2 近似量子f o u r i e r 交换 我们 钐啵写成如下形式，同样的，o ( 2 4 ) 项不对变换起作用 业5 箩+ ( 肌t + 抽唑1 + ( ，鼍+ l - b + 山毛) 幽+ ( 2 1 5 ) j + 五4 如+ + 五 j r + o t 2 j 。j 重! 隅中的p 2 枷归项表示成了 f 2 利，= p 2 啪归e 2 州粕+ 从归”，嘶蝴肚垆 ( 2 。1 观察上式等号右侧，从右向左指数上的系数越来越小，在一个带整数参数m 的近似q f 瓦( 即 s - 第二章量子计算和算法 a p p r o x i m a m q u a n t u m f o u r i e r t r a n s f o r m ) 中，最小的1 2 - m 项被忽略，余下的指数参数是2 石2 一 的倍数。带整数参数m 能j x q f t , 指的是忽略当1 s r a 一时，相位偏移以= - ( 七一j ) z r 的那些c p 门( 即受控置门) ，它的电路逻辑图与图2 3 类似，只是c p 门的个数减少了。以” 量子比特a q 脚目例，它使用了扑h a d 锄a r d 门和坚竺! ! 竖! 坐个c p 门，对参数m 满足 m ) ( 2 1 8 ) 情况l ，假设恰好有t 比特的二进制小数展开，那么就可以对上面电路图的输出应用逆 量子f o 晡e r 变换，将相位状态变换为i 识，珐，谚) ，则矿就确定了。 情况2 ，如果庐不能展开为t 比特的= 进制小数形式，那么假设我们能够以1 一e 的概率得 到矿的t 比特近似展开相位估计第一阶段电路的输出是：_ 7 导矿州。i x ) ，逆q f 瓦后状态 变换为丢窆。2 “争2 础i ) ，) ，因此测量得至咿的概率是： 州班窿一娜h 薹世吓 亿埘 求和后得到p f ( 力= 歹1，其中，= ? t 扣 当矿参时，假设矿的最接近的t 比特 p l 是复平面上l 的弦长，劣弧对弦长的比不大于詈，即罱s 争也就是 卜7 i 4 占2 f ，因为复平面上l 孙的弦长卜i ，其劣弧对弦长的蛭少为1 州2 ：a 9 1 ， 所以 n 专饼= 争 亿z 。， 由公式( 2 2 0 ) 可知得到正确解的概率大于一个固定常数概率。更进一步，得到错误输出的概 率为纠 嘉，由1 1 一，i s 2 和i l 一，i 4 万，得到 。 n ( 艿) 方裔 2 埘) 如果万= 可c ，那么p r ( c ) s 万i ，可知，当离正确值越来越远时得到错误近似值的概率就会 降低。令q 是l p + y ) ( m o d 2 ) ) 的幅度，则q = 专薹( e 2 叫槲下，于是 = 爿蓦= h 2 ( 型i - e z 叫s - e ) c z z z ， 哆2 歹 i 孑巧虿而可j 。一j 眨2 2 设最终输出的结果为m ，对满足= m - b l e 的m 的概率给出估计，p 是容许误差的一个正整数， 观察到m 的概率为 p ( 川 e ) - 一邑枷蚶+ + ，荟。蚶杀可 组z s ) 矿叫“+ 0i ，_ io 一1 ， 1 0 第二章量子计算和算法 到n 比特，得到，选择，= ”+ 0 9 ( z + 去) 1 量子比特。 2 6 因式分解 整数的因式分解问题对经典计算机是n p 问题，迄今为止还没有经典的多项式时间的算 法可以来解这一问题，已知的最好的经典算法来求1 1 比特整数的素因子分解需要扩蜡9 砷 个操作。1 9 9 4 年，p e t e rs h o t 6 发现了一种在多项式时间内因式分解整数的量子算法，将操 作降到了o ( n 2 l o g n l o g l o g n l 次，其核心思想主要是利用数论中的一些定理，将问题转化为 求某个函数的周期。而求周期问题又可以由相位估计和求阶问题解决，所以求阶问题就成了 解决因式分解的关键。 引入数论【l ”中一概念，两个整数的最大公因子( g r e a tc o m m o nd i v i s o r ) 。a 和b 的最大公 因子是，同时为a 和b 因子的整数中最大的一个，记作g e d ( a , b 1 。利用e u c l i d 算法可以有效计 算出g e d ( a , b 1 - 设n 是一个正整数，x 与n 互质，1 x 一 【，c l 】【f 2 ，c 2 】 添加的门 i 门l f v 2 【v 2 ，r 、口2 厂、a l a y c 。扣 、6 十b 。， l i 一亿 ( a ) 规则3 的左部( b ) 规贝归的右部 图3 2 规则( 3 ) 的变换电路示意图 “) 当c 2 且f 2 正c 1 时，“，c 1 】【f 2 ，c 2 】 f 2 ，c l uc 2 一“ 【，2 ，c 2 】【 ，c l 】。规则( 3 ) 和“) 恰好是相反的，规则( 4 ) 电路如图3 3 所示； 矗鱼爪6 ， y l c ： 珥，、如l 啦 p 一 添加的门 i 一1 一 i v 1 j v l 毛，一、6 2 t 、6 j h + 1 并且 f l ， q 之前没有任何c n o 王门时， ，1 ，如 f 2 ，c 2 u c l 营 ， c l f 2 ，c 2 u “ ； 干干 _ 旷争 i o ) # 莅i o ) 司卜司卜 。 、 辅助位 图3 4规则( 5 ) 的变换电路示意图 ( 6 ) 如果有一整数f e c ，f ”+ 1 并且p ，c 】之前无c n 0 1 ；门，那么【f ，c 】占。 3 3 2 规则集的等价性 引理l t z z l 规则( 1 ) 到规则( 6 ) 的使用