（信号与信息处理专业论文）基于量子遗传算法的mimo信号检测的研究.pdf

南京邮电人学坝上训究生学位沱义 摘望 摘要 量子信息学是一门新兴的交叉学科，它在信息领域中有着独特的性能，在提高运算速 度、确保信息安全、增大信息容量和提高检测精度等方面可突破现有经典信息系统的极限。 特别是近年来，基于量子并行计算的量子智能算法有效地降低了一些经典难解算法的计算 复杂度问题。 在目前很多无线通信系统的标准制定中，多入多出( m i m o ) 技术已经被广泛采用。从 理论上己表明在充分散射的环境中，相对于单入单出( s i s o ) 系统来说，m i m o 系统具有提 高频谱效率和容量的巨大潜力。但由于接收机的高复杂度，标准中所采用的一般还是仅限 于很少的天线数和简单的天线方案。m i m o 系统本身所提供的性能和增益能够有多少被挖 掘出来，和接收机的算法有很大的关系，复杂的接收机检测算法也是影响m i m o 系统大规 模商用的一个原因。本文研究了基于量子并行计算的量子遗传算法并提出了一种基于量子 遗传算法( q g a ) 的m i m o 信号检测方案。仿真结果表明，文中提出的方法在误码率性能 方面明显优于经典遗传算法和传统的m i m o 信号检测器。 本文首先介绍了量子遗传算法的主要思想、机理，并对算法进行了改进且对改进的量 子遗传算法进行了性能测试分析。 其次针对未来大用户量的多用户通信，将量子遗传算法应用到c d m a 多用户检测中 去，设计了一种基于量子遗传算法的多用户检测方案，并对其进行系统仿真，与经典算法 相比，基于量子遗传算法的多用户检测，其抗多址干扰和抗远近效应的能力均优于传统的 多用户检测器和基于经典遗传算法的多用户检测器方法。 最后，针对目前m i m o 检测算法中具有最小差错概率的最大似然检测算法( m l d ) 的计 算复杂度随着发射天线数增长呈指数增长，在常规条件下是一个n p 难解问题，提出了一种 基于量子遗传算法的检测算法，尝试来提高检测性能、降低误码率，并仿真实现了该算法。 仿真结果表明，文中提出的方法在误码率性能方面明显优于经典遗传算法和传统的m i m o 信 号检测器。 关键词：量子计算、量子遗传算法、多用户检测、多输入多输出、信号检测、误码率 南京邮l 也人学坝上赴j | ，t 尘学位论义 摘要 a b s t r a c t q u a n t u mi n f o r m a t i o ns c i e n c ei sar i s i n g c r o s ss u b j e c t d u et o u n i q u ef e a t u r e s i n i n f o r m a t i o nf i e l d ，i tm a yb r e a kt h el i m i t a t i o no fc l a s s i ci n f o r m a t i o ns y s t e m ，c u r r e n t l ya v a i l a b l ei n s e v e r a la s p e c t s ，n a m e l y , s p e e d i n gc o m p u t a t i o n ，e n s u r i n gi n f o r m a t i o ns e c u r i t y , e x p a n d i n gt h e c a p a c i t yo fi n f o r m a t i o n ，i m p r o v i n gt h ea c c u r a c yo fd e t e c t i o n p a r t i c u l a r l yi 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 s ，b a s e d o nt h e p a r a l l e lq u a n t u mc o m p u t a t i o n , s i m p l i f y s o m ec l a s s i c i n f o r m a t i o ns y s t e m sw h i c ha r en o te a s yt os o l v eo nt h eb a c k g r o u n do fc l a s s i cs y s t e m i nt h er e l e a s e ds t a n d a r d so fm a n ym o b i l ec o m m u n i c a t i o ns y s t e m s ，m u l t i p l e i n p u t m u l t i p l e o u t p u t ( m i m o ) t e c h n o l o g yh a sa l r e a d yb e e na p p l i e d t h e o r e t i c a lw o r kh a ss h o w nt h a t i ns u f f i c i e n td c hs c a t t e r i n ge n v i r o n m e n t s ，m i m os y s t e m sh o l dt h ep o t e n t i a lo fe n h a n c i n g s p e c t r a le f f i c i e n c y - h e n c ec a p a c i t yc o m p a r i n gw i t hs i n g l ei n p u ts i n g l eo u t p u t ( s l s o ) s y s t e m s b u t d u ct ot h eh i g l lc o m p l e x i t yo fr e c e i v e r ，t h ep r a c t i c a lm i m os c h e m e sa r es t i l lv e r ys i m p l ew i t ha f e wa n t e n n a s t h ed i s s e r t a t i o nm a k e ss o m er e s e a r c h e so nt h ea p p l i c a t i o n so fq u a n t u mg e n e t i ca l g o r i t h m o nt h eb a s i so fp a r a l l e lq u a n t u mc o m p u t a t i o ni nt h em i m od e c o d i n gs c h e m e f i r s to fa l l ，t h ed i s s e r t a t i o ni n t r o d u c e st h eb a s i cp r i n c i p l eo fq u a n t u mg e n e t i ca l g o r i t h m ， a n dh a sm a d et h ei m p r o v e m e n tt oi t s e c o n d l y , w ep r o p o s e dam u l t i u s e rd e t e c t o rb a s e do nq u a n t u mg e n e t i ca l g o r i t h m c o m p u t e rs i m u l a t i o nr e s u l t ss h o w st h a tt h em e t h o dh a sm o r ep o w e r f u lp r o p e r t i e st h a nt h e d e t e c t o rb a s e do nc l a s s i c a lg e n e t i ca l g o r i t h m sa n dh a sp o w e r f u lp r o p e r t i e si nb i te r r o rr a t e f i n a l l y , f o c u s i n go nt h a tt h ed e g r e eo fc o m p u t a t i o nc o m p l i c a t i o no fm l de m e r g e s e x p o n e n t i a li n c r e a s ei nt h es e n s eo ft h el e a s te r r o rp o s s i b i l i t yi nt h ec u r r e n td e t e c t i o na l g o r i t h m s o fm i m o ，w h i c hi san ph a r dp r o b l e m an e wd e t e c t i o np r o g r a mf o rm i m os y s t e m sb a s e do n q u a n t u mg e n e t i ca l g o r i t h mi sp r o p o s e di nt h i sp a p e r c o m p u t e rs i m u l a t i o nr e s u l t ss h o w st h a t t h em e t h o dh a sm o r ep o w e r f u lp r o p e r t i e st h a nt h ed e t e c t o rb a s e do nc l a s s i c a lg e n e t i ca l g o r i t h m s a n dt r a d i t i o n a ld e t e c t i o nf o rm i m os y s t e m sa n dh a sp o w e r f u lp r o p e r t i e si nb i te r r o rr a t e k e y w o r d s ：q u a n t u mc o m p u t a t i o n ；q u a n t u m g e n e t i ca l g o r i t h m ；m u l t i u s e rd e t e c t i o n ； m u l t i p l e - i n p u tm u l t i p l e - o u t p u t ( m i m o ) ；s i g n a ld e t e c t i o n ；b i te r r o r r a t e i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：醴日期：! 呈竺! ! 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：i 兰! 銎 导师签名：毒符 一日期：! 星，皇：! f 南京邮电人学坝1 ：研，生学位论义笫一章绪论 第一章绪论 我们生活在一个信息时代，信息科学在推动社会文明进步和提高人类生活质量方面发 挥着令人惊叹的作用，这是其他学科多无法比拟的。随着人类社会对于信息的需求日益增 加，人们不断地致力于信息技术的进一步发展。量子信息学正是信息科学发展和变革的产 物，是将量子力学应用于信息科学的一门新兴交叉学科。量子信息学包括量子计算、量子 通信、量子密码等几个方面，近年来在理论和实验上都取得了重大突破。量子信息基于量 子特性而具有独特的信息功能，在提高运算速度、确保信息安全、增大信息容量、和提高 检测精度等方面具有突破现有经典信息系统极限的能力。量子信息的研究与应用，不仅引 起各国政府和科技界的广泛关注，而且受到信息产业界和军事部门的高度重视，已经成为 国际上研究的热点。不可否认，2 1 实际正是信息科学从经典跨越到量子的关键性时期。 1 1 研究背景 近年来，随着移动通信的迅猛发展，在第三代( 3 g ) 移动通信系统步入全面测试以及 逐步商用之时，第四代移动通信( 4 g ) 的研究已是刻不容缓，用户数量的增加己经不再是 其追求的单一目标，与3 g 相比，4 g 系统应具有更高的数据率、更好的业务质量( q o s ) 、 更高的频谱利用率、更高的安全性、智能性、以及更高的传输质量和灵活性。在有限的频 谱资源的情况下实现高速率和大容量是第四代移动通信的一大特点。在分配给4 g 系统频 谱资源有限的情况，要想获得更高容量，必须提高频谱利用率。然而，采用常规发射分集、 接收分集或智能天线技术已不足以解决新一代无线通信系统的大容量与高可靠性需求问 题。可幸的是，结合空时处理的多输入多输出( m i m o ) 技术，提供了解决该问题的新途径【l j 。 采用空时编码的m i m o 系统能使用于i n t e m e t 和多媒体业务，并且可动态增加覆盖范围和 可靠性。 按照s h a n n o n 定理，对于3 g 系统，如果信道带宽为5 m h z ，而数据速率为2 m b s ，则 所需的s n r 为1 2 d b ：而对于4 g 系统，要在5 m h z 的带宽上传输2 0 m b s 的数据，则所需 要的s n r 为1 2 d b 。可见，对于4 g 系统，由于速率很高，因此对接收机的性能要求也要 高得多p j 。的确，m i m o 系统本身所提供的性能和增益能够有多少被挖掘出来，和接收机 的算法有很大的关系，复杂的接收机检测算法也是影响m i m o 系统大规模商用的一个原 因，作为最优解码的最大似然检测( m l d ) 由于复杂度随着发射天线个数成指数性增加， 南尔h 】“ 也人字f i ! j l j 研，生学位论义第一章绪论 限制了它在实际系统中的应用。 与传统的单输入单输出( s i s o ) 系统相比，m i m o 系统接收端接收到的是在时间上和 频率上均相互重叠的多路信号，频率选择性系统中还存在不同时刻信号间的码间干扰， m i m o 信号检测面临着远高于传统s i s o 信号检测的困难和问题。由于信号检测性能的好 坏将直接影响到整个m i m o 系统性能的好坏，设计高性能、低复杂度的m i m o 信号检测 算法已成为m i m o 通信中的一项具有重大意义的关键技术。 量子遗传算法( q g a q u a n t u mg e n e t i ca l g o r i t h m ) l 4 j 】是量子计算与经典遗传算法( g a ) 相结合而产生的一个新的研究领域。算法利用了量子计算的量子并行、量子纠缠特性，采 用了多状态基因量子比特编码方式和量子旋转门更新操作，引入动态和静态调整旋转角机 制和量子变异，使得算法比经典遗传算法具有更强的并行处理能力、更快的收敛速度且比 传统信号检测算法具有更高的效率。 本文主要研究量子遗传算法的机理以及对其进行算法改进，并将改进后的量子遗传算 法应用到现代通信中的多用户检测和m i m o 信号检测中。 1 2 本论文的研究工作 本文将对量子遗传算法进行研究、实现，并对其进行算法改进以及对其特性进行分析。 除此之外要对现有的基于量子遗传算法的应用进行分析和改进，提出了一种量子遗传算法 ( q g a ) 用于m i m o 信号检测的新方案，利用量子计算的一些优点特别是量子并行计算、 量子纠缠特性，使q g a 具有比遗传算法( g a ) 更强的并行处理能力和更快的收敛速度， 使得q g a 具有比传统检测算法更好的检测性能。 本论文结构安排及主要内容如下： 第二章：介绍了量子信息理论的基本概念，包括量子态及其表示、量子力学基本特性、 量子逻辑门等内容。 第三章：介绍了经典遗传算法( g a ) 和量子遗传算法( q g a ) 的主要思想、算法的流程、 机理，详细介绍了量子比特的染色体编码及旋转门策略，并对算法进行了改进且进行了性 能测试分析，通过实验测试可知，改进的量子遗传算法比量子遗传算法要具有更好的收敛 效果、更快的收敛速度，能够更快的接近目标值。 第四章：介绍了经典多用户检测的基本理论，给出了多用户检测的信号模型，设计了 基于量子遗传算法的多用户检测模型并进行了系统仿真和性能分析，从仿真结果可知，基 于量子遗传算法的多用户检测方法，其抗多址干扰和抗远近效应的能力均优于传统的多用 2 南京邮电人学坝_ 【：乜圩究生学位论义第一荦绪论 户检测器和基于经典遗传算法的多用户检测器方法。 第五章：介绍了m i m o 系统的基本原理、系统模型、信道容量以及m i m o 系统常用 的信号检测算法并对其进行了系统仿真和性能分析。研究及设计了基于遗传算法和量子遗 传算法的m i m o 信号检测模型并进行了系统仿真和性能分析。通过仿真结果可知，基于量 子遗传算法的m i m o 信号检测方法检测性能明显由于传统检测器。 第六章：工作总结，指出可进一步研究的问题。 南京邮电人学硕上 究生学位论义第二章量了信息处理基础 第二章量子信息处理基础 量子信息是信息科学与量子力学相结合的新兴交叉学科，开拓了量子力学应用的新天 地，为2 1 世纪信息科学的发展提供了新的原理和方法。 2 1 量子态空间及量子比特 著名物理学家费恩曼( f e y n m a n ) 哲指出：量子力学的精妙之处在于引入几率幅( a p 量子 态) 的概念。事实上，量子世界的千奇百怪的特性正是起源于这个量子态。而量子理论的长 期激烈争论的焦点也在于这个量子态。任何一个量子态罗可以表示成h i l b e r t 空间( 完备内 积空间) 的一个矢量，称为态矢量，h i l b e r t 空间就是态矢量张起的空间，称为态矢空间【o j 。 态矢空间由多个基本量子态即本征态构成，基本量子态又称基本态或基矢。对于量子计算 和量子信息处理而言，只需考虑有限量子系统和有限维h i l b e r t 空间。 量子态及作用在该量子态上的变换可用h i l b e r t 空间的矢量和矩阵描述，或用更简洁的 d i r a c 左右矢符号表示。右矢i x 表示列矢量，用于描述x 代表的量子态，左矢 的共轭转置，是行矢量。例如，在二维h i l b e r t 空间中，- o ( o l ，( ? ) 可分别用右 矢 10 ，l1 ) 表示，其任意复线性组合a10 ) + 6i1 即代表列矢量( 口，6 ) r 。 符号伍iy 表示两个态矢量的内积，它是一个标量，如 ( 0 10 = ( 1 0 ) m ， c 。i ) = ( 。) ( ：) ；。， 驴( o l 将 帖( 0 l 将。 ( 2 1 ) 符号i x ) 或1 ( 即1 1 ) 外，还可以取0 和1 的任意线性叠加，如口lo + 6l1 ，即 q u b i t 可处于叠加态，在此，a 和b 为复数且la1 2 + lb1 2 = 1 ，即q u b i t 是归一化的。一个q u b i t 南京邮电人学坝h 卅，生学位论义第二章量r 信息处理基础 的态可用二维h i l b c r t 空间的单位矢量描述，即 i 妙 = a 10 + 6 i l ( 2 3 ) 若a = 1 ，b = 0 或a = o ，b = 1 ，则q u b i t 处于10 态或i1 态；若a ，6 取一般复数值，则q u b i t 处于叠加态i 沙 = 口io + 6i1 。这说明，q u b i t 的态不是如经典b i t 那样确定性的非o 即1 ， 而是概率性( p r o b a b i l i s t i c ) 的，它为i o 和1 1 的概率分别是i 口1 2 和i b l 2 。 2 2 量子态的叠加、相干和消相干 量子计算的基本特征是量子态的叠加性。线性叠加概念与矢量的线性组合有关，若 i 仍) 为2 ”维h i l b e r t 空间的一组基态，由于h i l b e r t 空间的完备性，由基态组合所得到的任 2 ”一l 一线性叠加ly = c ii 仍 也是该h i l b e r t 空间中的一个矢量。所以，若量子系统可能处在 一组 l 仍 ) 描述中，则其线性叠加态i 也是该量子系统的一个可能态，量子系统这一性质 被称为态叠加原理。 量子态i 是所有基态 i 仍 ) 的一个线性叠加，从概率意义上说可以认为该量子态同 时存在于所有基态之中。系数q 为量子基态i 仍 的概率幅，q 为复数且满足归一化条件 ic t1 2 = l 。概率幅q 的模平方iq1 2 表示对该量子态iy 进行测量时测量结果为量子基态 l = o i 仍 的概率。 相干( c o h e r e n c e ) 和消相干( d e c o h e r e n e e ) 是与线性叠加的概念紧密相关的。如果 一个量子系统处于基态的线性叠加之中，那么就称此量子系统是相干的；但是当一个相干 的量子系统以某种方式与它所处的环境发生相互作用( 例如对处于叠加态的量子位进行观 察和测量) 时，叠加态将受到干扰并发生变化，线性叠加将被破坏，由此所引起的相干的 损失就称为消相干或坍缩( c o l l a p s e ) 。量子态i 少 坍缩到基态i 仍 的概率为l q1 2 ，由于l 缈 描述了一个真实的物理系统，它必定完全坍缩到某一个基态，所以由各c 决定的概率之和 一定等于1 ，这个约束条件即归一化条件l q1 2 = 1 。 5 南尿邮【也人学坝上训夕生学位论义 第一章量r 信息处理基础 例如，最简单的电子自旋转系统，它是一个双态量子系统，其基态通常表示为1 个 ( 自 旋向上) 和一 ( 自旋向下) ，而相干态i 缈 是1 个 态和i j ， 态的线性叠加。这样一个双态自 旋系统可作为量子计算的基本单元q u b i t ，如用io ) 和il 分别表示1 个 和陆 ，则q u b i t 的态 可用二维h i l b e r t 空间的单位矢量iy = a10 + 6 l1 描述。若lai _ l ，6 = 0 或口= 0 ，lbi - 1 ，则i ) y gio 态或i1 态( 相当于经典b i t 取。或1 ) ，即i 处于基态，此时执行一个投影到基 lo ) ，il 上的测量，其中任何一个或者以概率1 出现或根本不出现，测量并不会改变这个态。但当 口，6 取其它值时， 如i少：口io)+b11)l-g ：昙l o + 华1 1 ) ，q u b i t 处于相干叠加态，只要系统 口，6 取其它值时， 如少 = 口 + = 詈l o + 半1 1 ， 处于相干叠加态，只要系统 保持其量子相干性，它就不能说是处在自旋向上态或是自旋向下态，应该是同时处在这两 种态之中。此时若执行投影到基 io ，i1 ) 上的测量，该系统将发生消相干，可能的结果是 以万4 的概率坍缩到io 态( 1 个 态) 或以吾的概率坍缩到态( 陆 态) 。假设初次测量的结 果是i 1 ，则得到这个结果的概率为万5 ，再次以同样的基矢进行测量将以概率1 ( 即1 0 0 ) 得到i1 ，因此，测量将相干叠加态iy 改变为结果态l1 ，系统发生了消相干。 2 3 量子并行和量子纠缠 在量子计算机中，处于叠加态的n 位量子寄存器可同时存储从0 到2 ”一l 的所有2 ”个 数，它们各以一定的概率同时存在，在经典电子计算机中，1 个n 位寄存器只能存储1 个 n 位二进制数；而在量子计算机中，1 个n 位量子寄存器可以以一定的概率同时存储2 ”个n 位二进制数。这样，作用于量子寄存器上的任意变换器都是同时对所有2 ”个数进行操作， 2 。一l 相当于对叠加态i 沙 = qi 仍 中的每一个量子基态i 仍 同时进行计算，得到的计算结果是 一个新的叠加态，并保存在n 位量子寄存器中，此即量子并行( q u a n t u mp a r a l l e l i s m ) 。因 而量子计算机的一次运算可产生2 ”个运算结果，相当于经典电子计算机2 ”次操作，或者同 时使用2 ”个处理器的并行操作。所以量子计算机可达到经典计算机不能达到的解题速度， 还可以解决经典计算机不能解决的某些计算复杂度很高的问题，如大数的质因子分解这一 n p 难解问题1 8 - 1 0 1 。 6 南京邮电大学硕士研究生学位论义第二章量子信息处理基础 发生相互作用的两个或多个子系统构成的复合系统的态，如果不能表示为其子系统态 的张量积的形式，则称这个复合系统处于纠缠态( e n t a n g l e ds t a t e ) 【7 1 。例如，有两个双态 量子系统a 和b ，其状态分别为 i = q1 0 ) + a 21 1 ( 2 4 ) i = 岛i o + 6 2i l ( 2 5 ) 当两个子系统相互独立时，复合系统的态是两子系态的张量积，即 i 杪) 爿 爿虬 oi = ( q10 a + 口2ii a ) ( 6 l10 b + 吃i1 口 ) ，1 、 l z o ， = 口l 岛io a o 日 + q 魄io a l b + 口2 岛i1 一o 嚣 + 口2 乞i1 1 占 但是，若两个子系统发生相互作用，系统的自由度将受到一些限制，此时便存在一些 态，如 = 击io a o b + 击i 1 a 1 b ( 2 7 ) = 击lo a l b ) + 击i 1 , t o s ( 2 8 ) 它们并不能表示为两个子系统态的张量积，这样的态就称为纠缠态。而 = 击io a o b + 去lo x l b ) 0 , 4 。击( io b + 1 1 劫 ( 2 9 ) 可以表示成两个子系统态的张量积，则式( 2 9 ) 所表示的态是非纠缠态。 纠缠显示了经典力学所不能解释的量子态的关联特性，当量子系统处于如式( 2 7 ) 所 示的纠缠态时，如果对其测量所得到的结果是系统a 处于10 态，那么能精确知道系统b 一定处于10 ) 态，这个过程不需要任何时间，也就是说，系统b 的演变与对系统a 的测量 同时发生，信息的传递是瞬时的。但当量子系统处于式( 2 9 ) 所示的非纠缠态时，不管对 系统b 的测量结果如何，系统a 始终处于1 0 态。 量子态的纠缠是量子信息的关键，涉及量子隐形传态( q u a n t u mt e l e p o r t a t i o n ) 、量子 编码、量子密钥分配等多方面，像能量和熵一样，是一种有用的信息资源。 2 4 量子逻辑门与量子门组网络 量子计算过程是对量子态的幺正演化过程，量子过程中的一切逻辑操作必须执行幺正 操作。完成最基本的幺正操作的量子装置称为量子逻辑门，简称量子门( q u a n t u mg a t e ) 。 7 南京邮电人学坝1 j 形 夕生学位论义第二章量了信息处理基础 卸耿o i 一( 眨 j l ，= 岩! 口i 。，+ ，h i - ，= 口( ：三 ( 三) + 6 ( ? 三) ( ? ) 。2 。2 ， = 口( ：) + 6 ( 三) = 口i ，+ 6 i 。， 疗= 铷二，) 旺 疗l 。 = 击( i o ) + 1 1 i ) ) 印 = 击( i o ) 一1 1 ) ) ( 2 1 4 8 南京邮电大学硕一：研究生学位论文第一二章量子信息处理基础 | | 日10 ) 一 图2 1 疗i o 和疗l l 的图示 l1 有( 2 1 4 ) 式可知，h 门( 即算子疗) 作用于1 0 态将产生叠加态i 1 ( 1 0 ) + 1 1 ) 。若将 v 二 算子疗分别作用于厅个i o 态q u b i t ( 疗。疗p o g r ) l0 0 o 、广_ - 一、，一 月个月个 = 专( ( i 。 + l l ) 。( 协1 1 ) ) 融一圆( 1 0 ) + l l ) ) ( 2 1 5 ) 1 2 4 1 2 方善旧 则产生了2 ”个量子基态 i 仍 ) ( f = 0 , 1 ，2 “一1 ) 的叠加。所以，当量子寄存器中的n 个 原始数位全为0 时，对每一位分别进行h 变换可产生2 ”个基本态的叠加，即产生从0 到 2 一一1 的所有二进制数，它们同时存在，存在的概率均为1 歹。( 2 1 5 ) 式所示变换即w a l s h 变换，或称w a l s h - h a d a m a r d 变换，它是量子并行( q u a n t u mp a r a l l e l i s m ) 计算的基础。 ( 3 ) 相移门( p 门) 户爿。 _ lo ，611 ) = p 口i1 ( 2 1 7 ) 算子户改变了两个基矢io - 与11 ) 的相对位相，所以称p 门( 或算子户) 为相移门。 南京t i l l s l 也人学坝上研究生学位论文 第二章量子信息处理基础 ( 4 ) 控t l e f - j ( c n o t 门) 或量子异或( x o r ) 门 c 删爿o 态时，才取第二量子位的逻辑非。第一量子位控制了第二 量子位的取值，称第一量子位为控制位。控制位对第二量子位作用? 或者j ，决定于控制 位是处于l0 态还是l1 态。 从式( 2 1 9 ) 中第二量子位的取值可以看出，算子e 讲实现了两个q u b i t 的异或( x o r ) 操作，因而又称控非门为量子异或门，可以用图2 2 表示。 ix ) 厂。、 图2 2 量子异或门 lx o y 图中，ix 和lj ， 为输入，输出为ix ) 和ix oy ) ，lx 为控制位的态，第二量子位的输出为x 和y 的异或( 模2 加) x oy 。 ( 5 ) 控控非门( c c n o t 门) 或t o f f o l i ( t 门) l o 9z 够d d 殄 优 叭 m 1 厂1 广1 r 1 厂d 吣d唧吣埘m 口 d a o 南京邮电人学坝上研究生学位论义 第一章量j i 忆总处理基础 c c 叫= o ( o i o ， ，+ l l ( 1 i o = l0 ol o 0 oo o o o o 0 o o0 00 0o l0 o1 o0 oo oo 00 0o 0o 0o o o l0 ol o 0 o0 0 o oo 0 o 0 o o 0 0 o 01 lo ( 2 2 0 ) 控控非门( c o n t r o l l e d c o n t r o l l e d - n o tf 1 ) c ( 是作用在3 个q u b i t 上的幺正操作， 其作用过程为 c ( io o o ) = io o o ，c ( 乙10 0 1 ) 爿0 0 1 ) c c 叫f o l o ) 爿0 1 0 ，c c o , 1 0 1 l 爿0 1 l c c o , i1 0 0 ) 爿l o o ) ，c g 讲i1 0 1 ) = i1 0 1 ) c c 。，i11 0 ) 爿111 ) ，c c o , i111 ) ： 11 0 ) ( 2 2 1 ) 当且仅当第一、二量子位均处于ll 态时，才取第三量子位的逻辑非，因而称为控控非门 ( c c - n o t ) ，又称t o f f o l i 门，可以用图2 3 表示。 y 厂 、 l夕 图2 3 量子t o f f o l i 门 jx i ( x 八y ) o z 图中，ix 、iy 、iz 为输入，输出为ix 、iy 和i ( xa y ) oz ，第三量子位的输出表示x 与y 相与( x ay ) 后再与z 异或( 模2 加) 。 t 门可以实现多种逻辑操作，例如量子与门。在式( 2 2 1 ) 所示变换中，如果第三量 子位为10 ，则有 南泉邮电人学坝上研，生学位论义第一二章量了信息处埋皋础 a 1 0 0 0 ) 刊0 0 0 ) c i o l 0 ) 4 0 l o ) ( 2 2 2 ) c i l l o o ) 刊1 0 0 ) c i l l o ) 爿1 1 1 可以看出，第三量子位的输出是第一、二量子位相与的结果，实现了量子与门的操作， 可以用图2 4 表示。 iy 0 厂 、 t 图2 4 量子与门 lx i 力 i xa y 除上述5 种特殊的量子门外，还可以构造量子通用门【1 1 1 ，量子通用门是能实现任意幺 正变换的量子门。1 9 8 9 年d e u t s c h 将经典t o f f o l i 门推广到量子领域得到了d e u t s c h 门，并 证明任意n 位h i l b e r t 空间的所有幺正变换，其计算网络都可以由d e u t s c h 门重复使用构造 出来【l ，所以d e u t s c h 门是量子计算的通用门。 量子门组网络【1 1 】由多个量子通用门组成，这些量子门的操作在时间上同步，可实现任 意n 维h i l b e r t 空间的所有幺正变换，即与经典计算机的逻辑门组网络在算法控制下可实 现经典计算一样，量子门组网络在算法控制下可实现量子计算。量子计算机的门组网络模 型可描述如下： 量子计算机的存储器由按一定次序排列的双态量子系统( 即q u b i t ) 组成，n 个q u b i t 的2 ”维h i l b e r t 空间用来编码要处理的信息。量子计算由对编码量子态的幺正演化完成， 而幺正演化由量子门组网络在算法控制下实现。量子门组网络按算法逻辑要求构造，不同 的q u b i t 通过不同的门组网络，经过算法要求的逻辑门的作用，完成计算操作。与经典计 算机一样，量子计算机也需要输入、输出设备，量子计算机的输入是在量子存储器中制备 初始量子态对应输入信息，量子计算机的输出设备由量子测量仪器构成，通过对计算 末态的测量输出计算结果。 1 2 南京邮电人学坝上研究生学位论义 第二辛量j “。总处j 坐蛙础 2 5 本章小结 本章简要介绍了量子信息处理研究中涉及到的一些主要概念和基本知识，包括描述量 子态的态空间和左右矢符号、单量子比特( q u b i t ) 和多量子比特( 量子寄存器q r e g i s t e r ) 、 量子态的叠加原理和量子态的相干与消相干、量子并行和量子纠缠特性、几个重要的量子 逻辑门及由量子门构成的量子门组网络等。 1 3 第_ 二章量j ，遗传算法及j 改进 3 1 引言 第三章量子遗传算法及其改进 量子遗传算法( q u a n t u mg e n e t i ca l g o r i t h m ，q g a ) 是量子计算与遗传算法相结合的 产物。它建立在量子的态矢量表述基础上，将量子比特的几率幅表示应用于染色体的编码， 使得一条染色体可以表达多个态的叠加，并利用量子旋转门或量子非门实现染色体的更新 操作，从而实现了目标的优化求解。目前，这一领域的研究主要集中在量子模型上：一是 n a r a y a n a n 和m o o r e 等人于1 9 9 6 年将量子多宇宙的概念引入遗传算法提出的量子衍生遗 传算法( q u a n t u mi n s p i r e dg e n e t i ca l g o r i t h m ) b 2 i ；二是h a m 与k j m 等人在2 0 0 0 年提出 的基于量子比特和量子态叠加特性的遗传量子算法( g e n e t i cq u a n t u ma l g o r i t h m ) 和并行 量子遗传算法【1 3 , 1 4 。前者被成功地用于解决t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 问题，后 者被成功地用于实现0 1 背包问题的求解，并且性能均明显优于经典g a 。 本章是在综述经典遗传算法的基础上介绍量子遗传算法，首先给出量子遗传算法中的 几个基本概念，然后详细地介绍量子遗传算法的实现步骤，最后通过分析量子遗传算法已 取得的研究成果，并且针对其不足，对该算法进行改进。改进量子遗传算法主要是针对量 子遗传操作进行改进，使其能够适合连续函数的寻优计算，在算法中针对具体问题引入不 同的量子交叉操作和量子变异策略，使其能够充分利用所有的染色体信息以产生更多的新 模式，大大提高了算法的搜索能力。因此，改进的量子遗传算法既具有较好的种群多样性， 又具有更好的全局搜索能力。 3 2 经典遗传算法的原理及应用 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 起源于对生物系统所进行的计算机模拟研究，是 模拟自然界生物进化机制的一种算法，即遵循适者生存、优胜劣汰的法则，也就是寻优过 程中有用的保留，无用的则去除。在科学和生产实践中表现为，在所有可能的解决方法中 找出最符合该问题所要求的条件的解决方法，即找出一个最优解。这种算法是1 9 6 0 年由 h o l l a n d 提出来的。其最初的目的是研究自然系统的自适应行为，并设计具有自适应功能的 软件系统。它的特点是对参数进行编码运算，不需要有关体系的任何先验知识，沿多种路 线进行平行搜索，不会落入局部较优的陷阱，能在许多局部较优中找到全局最优点，是一 种全局最优化方法。近年来，遗传算法已经在国际上许多领域得到了应用。1 9 8 5 年召开了 1 4 南尿i | 【；哇三人学坝上饼，t 生学位论义 第= 江量j i 遗传黄。上及j 0 改进 第l 届有关遗传算法的国际会议，第l 部关于这方面的专著在1 9 8 9 年问世，遗传算法是一种 有广泛应用前景的算法。 3 2 1 遗传算法的基本原理 遗传算法是一种随机全局搜索算法，它对目标空间进行随机搜索。它将问题域中的可 能解看作是群体的一个个体或染色体，并对每一个个体用二进制表示法或浮点数表示法进 行编码，实现模型的参数化，把代表模型集参数空间中的每一点都一一映射到染色体空间 的染色体上，对群体反复进行基于遗传学的操作，根据预定的目标函数对每个个体进行评 价，经过基本的遗传操作过程，并反复迭代不断优化繁殖以产生新的一代，不断得到更优 的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。 在很多情况下，我们解决一个问题就是从一大堆的数据中寻找一个解，而通常这个解 都是混杂在数据中的。所有可行解组成的空间称之为搜索空间( 也称为状态空间) 。搜索 空间中的每一个点都是一个可行解，每一个可行解都可以被它的函数值或是它的适应度所 标记。问题的解就是搜索空间中的一个点，于是我们就是要从搜索空间中找到这个点。这 样，求解问题就可以转化为在搜索空间中寻找极值点。搜索空间在求解问题时可能是完全 已知的，但一般来说我们只知道一些孤立的点，然后我们逐渐地生成其它点。可能这个搜 索过程会很复杂，甚至于我们不知道该去哪里搜索或者该从什么地方开始搜索，有很多寻 找合适解的方法，比如说爬山法( h i l lc l i m b i n g ) 、模拟退火算法( s i m u l a t e da n n e a l i n g ) 以及遗传算法等等。用遗传算法求解出来的解一般被认为是一个比较好的解。 遗传算法的几个基本概念： 染色体( c h r o m o s o m e ) ：在使用g a 时，需要把问题解编成具有固定结构的符号串， 它的每一位代表一个基因。一个染色体就代表问题的一个解，每个染色体称为一个个体。 群体( p o p u l a t i o n ) ：每代所产生的染色体总数。一个群体包含了该问题在这一代的一 些解的集合。 适应度( f i t n e s s ) ；每个个体对应一个具体问题的解，每个解对应的函数值即为适应 函数，它是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数。 简单遗传算法( s i m p l eg e n e t i ca l g o r i t h m s ，s g a ) 是所有遗传算法的基础，也是研究各 种遗传算法性能和优缺点的对象。虽然在一般的应用中不会直接应用简单的遗传算法，但 对它的深入了解对我们掌握遗传算法的基本思想有重要的意义。遗传算法的基本流程如图 3 1 所示。 1 5 南京邮电人学坝上刨f 究生学位论义第一二草量j i 遗1 0 算泫及具改进 图3 1 遗传算法流程图 简单遗传算法的基本步骤如下： s t e p l ：对所涉及问题的可能解进行染色体( c h r o m o s o m e ) 编码； s t e p 2 ：针对问题，寻找一个客观的适应度函数( f i t n e s sf u n c t i o n ) ； s t e p 3 ：生成满足所有约束条件的初始种群( i n i t i a lp o p u l a t i o n ) ； s t e p 4 ：计算种群中每个染色体的适应度( f i t n e s sc o r e ) ： s t e p 5 ：若满足停机条件，退出循环，输出最优解；否则，继续向下执行； s t e p 6 ：根据每个染色体的适应度，产生新的种群，即进行选择操作； s t e p 7 ：进行交叉操作和变异操作。 s t e p 8 ：返回s t e p 4 进行计算 3 2 2 遗传算法常见编码方法和基本操作 编码是应用遗