（计算机软件与理论专业论文）量子神经网络模型及其算法研究.pdf

摘要 量子神经网络是一种崭新的技术理论，是量子计算理论与人工神经网络结合 的产物。量子神经网络兼具两者的优点，同时又能够利用量子态叠加、量子并行 计算和量子纠缠等特性克服传统人工神经网络的某些固有缺陷，极有可能成为未 来信息处理的重要手段。 本文对量子神经网络模型展开研究，给出了量子间隔的更新式的数学推导， 针对量子神经网络模型仍采用b p 算法进行训练因而不能避免b p 算法的某些缺陷 的问题，提出了采用反正切函数作为量子神经网络模型隐含层激活函数，并在权 值修正量中引入假饱和预防函数，提出了改进的量子神经网络模型；在对量子遗 传算法理论分析的基础上，本文将改进的量子遗传算法与b p 算法相结合，提出了 量子遗传神经网络混合算法，进一步改进了量子神经网络模型的收敛性能。本文 所做的主要工作如下： ( 1 ) 概述了量子遗传算法，重点对量子旋转门进行了详细分析，通过动态调 整旋转角的策略，将旋转角视为与当前迭代代数相关的变量，从而加速了收敛； 引入量子交叉和群体灾变操作，提出了改进的量子遗传算法，提高了算法的搜索 能力。 ( 2 ) 分析了多层激活函数的量子神经网络模型，给出了量子神经网络模型的 量子问隔训练算法的详细推导；提出了改进的量子神经网络模型，引进了比 s i g m o i d 函数更为陡峭的反正切函数作为隐含层神经元的激活函数，同时引入了假 饱和预防函数，避免网络陷入饱和状态，提高了模型的收敛速度。 ( 3 ) 提出了量子遗传神经网络混合算法，采用量子遗传算法对量子神经网络 模型的权值和阈值进行优化，将最优解作为量子神经网络模型的初始权值和阈值， 并对算法进行了仿真，将其与现有的量子神经网络模型进行比较，仿真实验结果 证明了改进算法的有效性和可行性。 关键词：量子旋转门，群体灾变，多层激活函数，假饱和预防函数，量子遗传神 经网络混合算法 r e s e a r c ho nq u a n t u mn e u r a ln e t w o r km o d e la n di t s a l g o r i t h m a b s t r a c t a st h ec o m b i n a t i o no fq u a n t u mc o m p u t a t i o nt h e o r ya n da r t i f i c i a ln e u r a ln e t w o r k ， q u a n t u mn e u r a ln e t w o r k i san o v e lt h e o r y i th a st h es t r o n g p o i n to fq u a n t u m c o m p u t a t i o nt h e o r ya n da r t i f i c i a ln e u r a ln e t w o r k a n di t c a nm a k ef u l lu s eo ft h e c h a r a c t e r i s t i c so fq u a n t u mc o m p u t a t i o n ，s u c ha st h es u p e r p o s i t i o no fq u b i t s ，q u a n t u m p a r a l l e lc o m p u t a t i o n ，a n dt h ee n t a n g l e m e n to fq u b i t s ，t oo v e r c o m es o m ei n h e r e n c e b u g so ft r a d i t i o n a la r t i f i c i a l n e u r a ln e t w o r k m o s tp o s s i b l y ，t h eq u a n t u mn e u r a l n e t w o r kw i l lb eav e r yi m p o r t a n tm e a s u r et od e a lw i t hi n f o r m a t i o ni nt h ef u t u r e t h et r a i n i n ga l g o r i t h ma n dt h es t r u c t u r eo fq u a n t u mn e u r a ln e t w o r kt h a tb a s e do n m u l t i l e v e la c t i v a t i o nf u n c t i o na r ep r e s e n t e di nt h i sd i s s e r t a t i o n t h eq u a n t u mn e u r a l n e t w o r km o d e lu s e sb pa l g o r i t h mt om o d i f yt h el i n kw e i g h t sa n dt h r e s h o l d s s o ，s o m e o ft h eb u g so fb pa l g o r i t h ma r ea v o i d l e s sf o rt h eq u a n t u mn e u r a ln e t w o r k a i m i n ga t t h i sp o i n t ，al i n e a rs u p e r p o s i t i o no fa r c t a n g e n tf u n c t i o ni si n t r o d u c e di na sh i d el a y e r a c t i v a t i o nf u n c t i o n ，a n de r r o rs a t u r a t i o np r e v e n t i o nf u n c t i o ni sc o n s t r u c t e dt oi m p r o v e t h ec o n v e r g e n c ep r o p e r t yo fq u a n t u mn e u r a ln e t w o r km o d e l a n dq u a n t u mg e n e t i c a l g o r i t h mi si n t r o d u c e dt od e a lw i t ht h el i n kw e i g h t sa n dt h r e s h o l d so ft h eq u a n t u m n e u r a ln e t w o r k ，s e a r c h i n gf o rt h eb e s tl i n kw e i g h t sa n dt h r e s h o l d st oi n i t i a l i z et h e n e t w o r k i nt h i sw a y , t h ec o n v e r g e n c ep r o p e r t yo fq u a n t u mn e u r a ln e t w o r ki si m p r o v e d m u c hm o r e t h em a i nt a s k st h a th a v e b e e nd o n ei nt h i sd i s s e r t a t i o na r es h o w na s f o l l o w s ( 1 ) t h ec h a r a c t e r i s t i c so ft h eq u a n t u mg e n e t i ca l g o r i t h ma r es u m m a r i z e d a n dt h e q u a n t u mg a t ei sa n a l y z e di nd e t a i l t h ep o l i c yo fd y n a m i ca d j u s t i n gt h eq u a n t u mg a t e i su s e d t h ee i r c u m r o t a t ea n g l eo fq u a n t u mg a t ei sr e g a r d e da st h ev a r ia b l eo ft h e c u r r e n ti t e r a t i v eg e n e r a t i o n s o ，t h ec o n v e r g e n c ep r o p e r t yi si m p r o v e di nt h i sw a y t h e q u a n t u mi n t e r c r o s sa n dc a t a s t r o p h eo p e r a t i o na r ei n t r o d u c e di nt oi m p r o v et h es e a r c h a b i l i t yo ft h ea l g o r i t h m ( 2 ) t h eq u a n t u mn e u r a ln e t w o r km o d e lb a s e do nm u l t i l e v e la c t i v a t i o nf u n c t i o ni s a n a l y z e da n dt h ed e t a i l e dp r o c e s so ft h eq u a n t u mi n t e r v a l st r a i n i n ga l g o r i t h mi sg i v e n al i n e a rs u p e r p o s i t i o no fa r c t a n g e n tf u n c t i o ni si n t r o d u c e di na sh i d el a y e ra c t i v a t i o n f u n c t i o n ，a n d e r r o rs a t u r a t i o n p r e v e n t i o n f u n c t i o ni sc o n s t r u c t e dt oa v o i dt h e p h e n o m e n o no fe r r o rs a t u r a t i o ni nt h et r a i n i n gp r o c e s sa n dt oi m p r o v et h ec o n v e r g e n c e p r o p e r t yo fq u a n t u mn e u r a ln e t w o r km o d e l ( 3 ) t h eq u a n t u mg e n e t i ca n dq u a n t u mn e u r a ln e t w o r kh y b r i da l g o r i t h m i s p r o p o s e d t h eq u a n t u mg e n e t i ca l g o r i t h mi su s e dt oo p t i m i z et h ei n i t i a ll i n kw e i g h t s a n dt h r e s h o l d so ft h eq u a n t u mn e u r a ln e t w o r km o d e l ，t h eb e s tl i n kw e i g h t sa n d t h r e s h o l d sa r eu s e dt oi n i t i a l i z et h em o d e l s i m u l a t i o ne x p e r i m e n t so nt h ei m p r o v e d q u a n t u mn e u r a ln e t w o r km o d e la n dt h ee x i s t i n gm o d e l sa r eo p e r a t e dr e s p e c t i v e l y t h e v a l i d i t ya n df e a s i b i l i t yo ft h ei m p r o v e dm o d e li sp r o v e db yt h er e s u l t s k e yw o r d sq u a n t u mg a t e ，c a t a s t r o p h e ，m u l t i l e v e la c t i v a t i o nf u n c t i o n ，e r r o rs a t u r a t i o n p r e v e n t i o nf u n c t i o n ，q u a n t u mg e n e t i ca n dq u a n t u mn e u r a ln e t w o r kh y b r i da l g o r i t h m 1 1 1 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：当递指导教师签名 叫年月少f 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：j 讧伊 吖年f 月f 日 西北人学硕士学位论文 第一章绪论 人t i , 经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) 是实现并行分布式处理的自然 范例，它具有大规模并行处理、容错性、自组织、自学习和自适应能力以及联想 记忆功能等特点，在模式识别、信号处理、自动控制、决策辅助、人工智能等等 领域都取得了一定意义的成功。尤其是b p 算法的出现，带来了人工神经网络的第 二次研究高潮。b p 算法具有很强的数学基础，结束了多层神经网络没有训练算法 的历史，被视为是多级网络系统的训练方法i 。 经半个多世纪的研究和应用，人工神经网络已经比较成熟并且被广泛应用， 然而同时也显示出许多不足和缺陷。比如，训练速度太慢的问题、算法的收敛性 问题、高维曲面上局部极值问题等等都是困扰人工神经网络的严重问题，尤其是 易陷入局部极小值问题和收敛性问题，在严重的情况下甚至会导致网络训练的失 败2 1 。这些不足和缺陷限制了a n n n 论的发展，但同时也一定程度地推动了a n n 的改进方法以及神经计算与其他理论相结合的交叉科学的研究。 近年来，量子理论的发展引起人们的广泛关注，特别是s h o r 大数质因子分解 算法【3 】和g r o v e r 搜索算法f 4 】的提出，使得量子理论迅速成为研究的热点，推进了量 子计算与各领域研究方法的结合以及各类新算法的研究和应用。其中，量子神经 网络模型【5 】( q u a n t u mn e u r a ln e t w o r k ，q n n ) 是人工神经网络与量子计算理论相 结合而产生的，它能够充分利用量子计算的内在的并行性、态叠加和态纠缠等特 性【6 j ，成为了崭新的研究领域。量子神经网络充分利用了量子计算的特性，能够克 服传统人工神经网络的某些固有缺陷，比如收敛速度慢、易陷入局部极小值等等， 有望成为未来信息处理的重要手段。其中，多层激活函数的量子神经网络模型已 经在语音识别、故障诊断等等模式识别领域取得了许多成功的应用，证明了q n n 在实际应用中的有效性和高效性。因此，对量子神经网络的研究具有非常重要的 理论意义和实用价值。 1 1 选题背景及意义 经众多学者1 0 0 多年的不懈努力，量子理论的研究已经硕果累累。1 9 8 2 年， b e n i o f f 和f e y n m a n 最先将量子力学与推理计算联系起来，提出了将量子力学系统 用于推理计算的可能7 , 8 】；第一个量子计算模型【9 1 则于三年之后在英国皇家学会被 提出。由此开始，量子计算得到了迅速发展，成为了一门引入注目的新学科。1 9 9 4 1 第一章绪论 年，p e t e rs h o r 提出了一个多项式时间的量子算法，用于因式分解和离散对数，即 s h o r 算法【3 l ；1 9 9 6 年，l o vg r o v e r 发现了一个量子搜索算法，即g r o v e r 搜索算法 【4 1 。至今，由这两个算法发展起来的一系列研究已经对原始的算法进行了优化，并 出现了许多新的算法【1 0 】。s h o r 算法和g r o v e r 算法极大的推动了量子计算领域的研 究和发展，随后出现了以量子计算机、量子编码以及量子通讯为代表的量子信息 科学，并促进了量子算法与遗传算法、进化算法、克隆算法、免疫算法相结合而 产生的新算法的相关研究【1 1 , 1 2 】。 美国的k a k 教授于1 9 9 5 年提出了量子神经计算的概念【1 3 l ，自此量子神经计算领 域作为一个崭新的研究领域引起众多研究人员的关注。神经计算与量子理论的结 合可以有多种形式，不同形式的结合产生的计算模型也各有特点f 1 4 】。不论哪种形 式的结合都对人工神经网络向量子神经网络的演变起到了巨大的推进作用，其原 因主要包括：一是量子效应在人脑中存在着，而且对人脑起着重要作用；二是人 工神经网络通过与量子计算的结合，能够被推广到量子研究领域，得到更广泛的 研究和应用。目前常见的量子神经网络模型有基于多层激活函数的量子神经网络 0 5 , 1 6 】、q u b i t 神经元模型【1 7 , 1 8 】、多宇宙的量子神经网络模型【19 1 、d a n 等人的量子联 想记忆模型【2 0 1 、b e h r m a n 等人的时间和空间的量子神经网络模型【2 1 】以及k a k 等关于 脑科学的量子神经网络模型。 量子理论的态叠加原理使量子神经网络具有比传统神经网络更强的并行处理 能力，使其能够处理更大型更复杂的数据集。并行性可以定义为一个量子计算机 同时对多个输入进行操作的能力，是量子计算的实质。根据量子计算原理，一个刀 位量子寄存器可以同时保存少个刀位二进制数。因此，量子计算系统能够利用其并 行性特点，指数级地增加存储能力，而且量子计算机具有同时并行处理一个刀位量 子寄存器的所有少个数的能力。所以常规计算需要次操作才能完成的计算，对一 次运算可以产生少个运算结果的量子计算机来说，仅需一次运算就能完成。量子 神经网络的研究有助于对人脑功能的新的理解，同时有助于创建新的信息处理系 统以解决传统人工神经网络难以解决的问题并提升神经网络的信息处理能力。 本文主要对多层激活函数的量子神经网络模型【1 5 , 1 6 】进行研究。该模型采用传 统网络模型的拓扑结构，而隐含层使用多层激活函数使得q n n 模型具有内在的模 糊特性。目前，量子神经网络模型已在语音识别、手写字识别、故障诊断、表情 识别等模式识别问题上得到成功的应用 2 2 - 2 6 1 ，证明了q n n 在应用中的有效性和高 2 西北大学硕士学位论文 效性。但由于多层激活函数的量子神经网络模型仍采用b p 算法训练网络权值和阈 值，而且其量子间隔的更新算法也是梯度下降法，因而不能完全避免b p 算法的某 些固有缺陷。因此，本文对q n n 模型进行研究和改进，以提高算法的性能及有效 性。 1 2 论文研究内容及主要工作 1 9 9 7 年，k a r a y i a n n i s 等利用量子理论中量子态叠加的思想，提出了基于多层 激活函数的量子神经网络 1 5 , 1 6 j 。q n n 隐含层每个神经元激活函数表示为多个 s i g m o i d 函数的线性叠加，称之为多层激活函数，其中叠加的每一个s i g m o i d i 函数有 不同的量子间隔，对应不同的量子能级，可以通过调节量子间隔使不同类的数据 映射到不同的量子能级上，从而使分类具有更多的自由度。 由于隐含层采用了具有多个量子能级的激活函数的量子神经元，从而使q n n 具有内在的模糊判决特性，无需预先确定一个模糊测量方法，当给定一个适当的 训练算法，样本数据中的不确定性将被自适应的学习并确定。如果特征矢量处于 特征空间多个重叠类的边界，q n n 将把它分部分地指派给所有相关的类；如果不 存在不确定性，q n n 将把它指派给相应的类。所以，q n n 可以有效地解决模糊分 类问题的关键因素是具有多个量子能级的多层激活函数。许多成功的应用实例已 经充分地证明了这一点，同时也证明了使用量子神经网络处理分类问题可以达到 更高的精度。 然而由于q n n 模型网络权值及阈值等参数的更新采用的是b p 算法，因此 q n n 模型也无法避免b p 算法固有的一些缺陷，虽然q n n 模型在许多领域得到了 广泛的应用，而且能有效地解决分类问题，但是其收敛特性尚有待改进。 本文基于陕西省自然科学基金等项目，重点研究了q n n 模型及其混合学习算 法，并对该模型进行了有效地改进。 本文的主要工作是：概述了量子遗传算法及其特性，综述了使用量子编码对 变量个体进行编码的方法和采用量子旋转门对量子比特编码的染色体进行量子遗 传操作，并提出了改进的量子遗传算法，引入了量子交叉和群体灾变方法，以提 高算法的搜索性能；概述了q n n 模型，给出了量子间隔更新算法的数学推导，并 提出了改进的q n n 模型，采用反正切函数作为隐含层的激励函数，引入假饱和预 防函数防止训练过程陷入局部极小值，仿真实验证明了该方法的有效性；提出了 3 第一章绪论 量子遗传神经网络混合算法，即采用量子遗传算法对量子神经网络模型进行优化， 对q n n 网络模型的权值和阈值进行量子比特编码，寻求最优的量子神经网络模型 的初始权值和阈值，提高了量子神经网络模型的收敛特性，最后进行仿真实验， 验证了该算法的有效性和可行性。 1 3 论文组织 第一章概述了论文的研究背景及选题意义，概述了论文的研究内容、主要工 作和论文的结构。 第二章概述了量子计算基础理论、量子计算研究现状，分析归纳了量子遗传 算法和量子神经网络及其研究现状。 第三章对现有的量子遗传算法进行了详细讨论，重点分析了量子旋转门操作， 其旋转角采用动态调整策略，将角步长设定为与当前迭代代数相关的变量的方法， 将量子交叉和群体灾变操作引入量子遗传算法，提出了改进的量子遗传算法。文 中给出了量子遗传算法的算法描述及其部分遗传操作的实现，仿真实验证明了文 中提出的改进算法的有效性。 第四章详细分析了量子神经网络模型，研究了其网络结构，并对量子间隔的 更新算法进行了详细的数学推导：通过引进反正切函数和假饱和预防函数，提出 了改进的q n n 模型，仿真实验表明改进的q n n 模型的有效性，也验证了假饱和 预防函数对量子神经网络收敛速度的改进是可行的。 第五章在分析了b p 算法的固有缺陷及现有的改进方法的基础上，重点介绍了 遗传算法与b p 算法的混合算法，文中基于量子遗传算法优于传统遗传算法的特 性，提出了将量子遗传算法与b p 算法相结合的一种量子遗传神经网络混合算法， 即采用量子遗传算法对量子神经网络的权值和阈值寻优，以提高算法的性能，仿 真实验证明了该算法的有效性和可行性。 最后对文本所做的工作进行了总结，并针对文中算法的局限性，提出了进一 步的工作和研究方向。 4 西北大学硕士学位论文 第二章量子计算概述 自普朗克提出量子的概念，量子力学已经历了百年历程，在此期间，量子力 学给人类的生活带来翻天覆地的变化。在经历了不断的争论和实验后，人们加深 了对这门学科的认识，诞生了后来的量子信息学科。量子信息是量子物理与信息 科学相互融合而产生的交叉学科，它于上个世纪8 0 年代被提出，9 0 年代中期引起 学术界的广泛兴趣，受到各国研究人员的高度重视，并得到迅速发展。量子信息 技术基于量子特性28 1 ，比如量子相干性、非局域性、态叠加性、纠缠性、不可克 隆性等【1 3 】，可以实现传统信息技术极难完成的信息处理，例如，量子计算机可以 加速某些复杂函数的运算速度，量子密码学可提供不可破译不可窃听的保密通信 等。量子信息技术可突破传统信息技术的物理极限，为信息科学技术的发展提供 了新的原理和方法。2 1 世纪信息科学将从“经典”时代跨跃到“量子 时代。 2 1 量子计算基础 ( 1 ) 量子比特 传统信息理论中最基本的信息单元是b i t 。一个b i t 信息可以代表两个值：二 进制0 和1 。所有的经典信息理论都必须以二进制状态进行信息编码、转换和解码。 类似于b i t ，在量子计算理论中有q u b i t ，量子比特。在数学意义上量子比特代表一 个2 一维向量。与经典理论不同，量子比特并不仅限于两个值，事实上，它能表达 “0 和“1 ”之间的无限个中间态。量子态“0 和“1 表现为向量，如式( 2 1 ) 所示，它们形成了量子比特的正规基，任何量子比特的状态可能是这两个基向量 的叠加。 毗) ，1 1 ) = ( 0 ) 汜1 ， 量子比特的状态表达为1 0 ) 和1 1 ) 的线形组合，即： i 甲) = 口l o ) + 1 1 ) ( 2 2 ) 依据量子机制的规则，量子比特有一个奇特行为，即当数据为有规则的，量 子比特可以简单的“折叠”为f o 或f 1 ) 状态，不管在度量以前它是什么状态。折叠 成这两个状态的哪个状态取决于相应矩阵的系数，即度量时该量子比特折叠到这 个状态的概率振幅。所以在上式( 2 2 ) 中，在测量量子比特时获得一个1 1 ) 状态的 5 第二章量子计算概述 概率为例2 。在测量前，量子比特可以“同时为0 和1 ，这个能力叫做叠加。 ( 2 ) 量子逻辑 经典计算机上的计算的执行是通过使用逻辑操作符进行的，这些逻辑操作符 被表达为门【5 1 。常见的经典逻辑门有n o t 、a n d 、o r 、n o r 和x o r 等。在量子 比特上执行简单操作的相应的门称为量子门，被表达为2 2 单位矩阵( 在量子理 论上的线形代数形式) 。其中最简单的是量子非门，即所谓的x 门。这个门的操作 是通过反向获得1 或0 的概率。x 矩阵及其在等式( 2 2 ) 中定义的量子比特上的 操作如下所示： 到目前，已经证明每一个经典门都可以由一个基础量子门派生出来【13 1 。 ( 3 ) 纠缠( e nt | a n g l e m e n t ) 量子机制系统因为纠缠特性而具有很强的相互依存关系【2 9 , 3 0 】。纠缠是一个奇 怪现象，即测量一个系统的状态可以直接地确定另外一个系统的状态，即使在另 一个系统上没有进行任何度量。即使系统在空间上被任意距离隔离着，纠缠都有 效。纠缠是量子计算中的一个最有力的工具。 考虑下面的2 位量子比特状态： h ) = 万1 ( 1 0 0 ) + 1 1 ) ) ( 2 4 ) 式( 2 4 ) 中，乘数1 芝表明j o o 和1 1 1 ) 状态是等概率的( 都为1 2 ) 。如果测量 第一个量子比特的状态为l ，这意味着系统处于1 1 1 ) 状态，则第二个量子比特的状 态也是1 。相应的，如果度量结果是一个0 状态，则第二个量子比特也必定是0 状态。这即是所谓的量子比特的纠缠。 2 2 量子计算研究现状 b e n i o f f 最早提出用量子力学描述可逆计算机【7 1 。f e y n m a n 构造了哈密顿量【8 1 ， 用于对应各种逻辑门。量子图灵机和通用量子计算机的构想被d e u t s c h 提出，利用 量子计算网络构造了两个量子比特的算法【9 1 。b e r n s t e i n 等学者深入研究了量子计 算复杂性理论【3 1 1 ，使用严格的数学形式描述了量子计算机，并给出了量子图灵机 6 叭v 口 + 6 = 矗 + 吣 口 o x 0 ， 一 、t n ，n弋” x x 西北大学硕士学位论文 的计算效率比经典概率图灵机高的更强大的数学证据。 1 9 9 4 年提出的s h o r 算法和19 9 6 年提出的g r o v e r 算法f 4 】是目前已知的晟为 成功的算法。这两个算法极大地促进了量子计算的发展，充分地体现出了量子计 算的独具优势和重要应用前景，以它们为基础发展出许多新的算法和学科。从此， 量子计算研究领域在世界各地众多研究组织的共同努力下取得了许多重大进步， 如j o z s a 的因子分解算法、求中数和平均数的算法、h o g g 的约束满足问题算法等 笔【1 0 1 寸o 量子计算的相关应用主要有以下几个方面： ( 1 ) 解决n p 类问题 大数质因子分解是公认的n p 问题，可以描述为：给定一个足够大的数，找出 其所有因子。利用现有的算法无法在有限时间内找出一个大数的所有因子，只能 做到验证某个数是否是其因子。s h o t 量子算法可以在多项式时间内求出所有的因 子，其实现方法是将大数质因子求解问题转换为p 问题。对于经典算法，这个速 度是不可企及的。量子计算的并行性机制是量子计算能够解决n p 问题的关键，利 用并行性机制，量子算法能够对问题的所有可能解进行并行地搜索，进而在短时 间内得到正确的计算结果。对于不支持并行性的传统算法，对所有可能解进行搜 索可能会花上几年甚至几十年才能完成。该算法激发人们寻找对其他n p 问题可能 存在的量子算法。但是否所有n p 问题都可以利用量子计算转换为p 问题进行求解 还是个未知数。所以这种方法并不能对所有n p 问题都可进行有效解答。寻找n p 问题中有可能存在的更深层结构，使其可以使用量子算法对问题进行快速求解， 是该领域的主要研究内容。 ( 2 ) 量子搜索算法的研究 1 9 9 6 年提出的g r o v e r 算法主要用于搜索非结构化无序数据库问题，通过标注 目标矢量，并放大目标基态概率幅进行求解。该算法掀起了对量子搜索问题的研 究热潮。在众多研究组织的不懈努力，量子搜索问题的研究已经形成了一个完整 的搜索算法体系，能够适应各种不同类型的搜索需求。经典搜索算法的主要问题 是解空间过大，搜索路径过多，其主要工作就是设法减少实际搜索空间。而量子 搜索算法则能充分利用量子并行计算的固有优势，可以在解空间中进行完全搜索， 并将目标振幅放大从而求解。许多问题都可以归结为搜索问题，如数据库搜索问 题、最短路径问题、排序问题、图着色问题和密码学中的穷举攻击等。利用量子 7 第一二章量子计算概述 计算内在的并行性，量子搜索算法可以大大加快这类问题的求解进程。目前，各 种量子搜索算法的研究引起了众多关注，不断在各个领域得到成功地应用。 ( 3 ) 量子密码学的研究 对于以数学难题为安全基础的传统密码学，s h o r 提出的大数质因子分解算法 成为一个巨大的挑战。利用算法的并行性，s h o r 算法使量子计算机具有了轻易破 译r s a 公开密钥体系的能力。量子密码学由此而兴起。1 9 8 3 年发表的w i e s n e r 的 一篇有关共轭编码的文章奠定了量子密码学的基础【3 2 1 。b e n n e t 等人继续该课题的 研究，取得了丰硕的成果3 3 1 。利用h e i s e n b e r g 的不确定性原理，量子密码学原则 上可以提供不可破译、不可窃听的保密通信体系。国内一些学者也在量子密码学 体系的研究上取得了一定的成果。 ( 4 ) 模拟量子系统和量子计算物理实现 模拟量子系统，即量子仿真，是量子计算的另一个重要用途。其目标是对给 出的系统初始状态，通过模拟仿真求解某个时间或位置的系统状态。用经典计算 机模拟量子系统也是有可能的，但当系统复杂性呈指数级增长的时候，经典计算 机将陷入困境。模拟量子系统将成为量子计算的一个主要用途。 与理论方面的飞速进展相比，量子计算的实验进展则慢很多。一般认为，量 子计算的物理实现2 8 1 应至少具有完备的么正操作能力和初态制备能力，而且应为 量子比特提供足够长的相干时间，对量子计算机的终态可以进行有效的量子测量。 目前能够进行这方面实验的体系并不多，有待进一步的研究。 ( 5 ) 量子智能计算 将量子计算的态叠加、态纠缠和内在并行性等特性与传统智能计算相结合， 非常具有发展潜力。这种结合最早开始于专家系统，现在已经在更多智能计算中 得到应用，陆续出现了量子神经网络、量子遗传算法、量子退火算法、量子克隆 算法、量子免疫算法、量子聚类算法以及量子小波算法等。 2 3 量子遗传算法研究现状 作为一种模拟生物进化过程中优胜劣汰规则以及群体内部染色体信息交换机 制的处理复杂优化问题的方法【3 4 1 ，遗传算法( g e n e t i ca l g o r i t h m ，g a ) 具有不受问 题本身的性质、模型结构、优化准则形式、被优化参数个数以及有无约束条件等 的限制等等优点，仅用目标函数在概率准则引导下进行并行的全局自适应搜索， 8 西北大学硕上学位论文 可处理传统优化方法难以解决的各类复杂问题，具有很高的鲁棒性和广泛的适用 性。因而g a 在各个领域都得到了广泛的应用，同时也成为跨学科研究的热点。 但长期而广泛的实验证明，g a 存在一些不足和局限性，如迭代次数多、易陷入局 部极值、收敛速度慢等等。g a 收敛性主要通过选择实现，搜索性则通过遗传交叉 和变异实现。由此可知g a 的收敛速度主要与选择方式有关，“早熟 现象则主要 与交叉和变异方式有关，因此，克服选择操作中的竞争压力、通过交叉和变异操 作保持g a 的种群多样性，进而提高g a 的搜索性能，一直是遗传算法的研究和 应用中要解决的问题。 n a r a y a n a n 等学者首先将遗传算法与量子理论相结合，提出了量子遗传算法【3 5 】 ( q u a n t u mg e n e t i ca l g o r i t h m ，q g a ) 。自此，各国研究人员对量子遗传算法展开研 究，陆续提出了许多新的量子遗传算法以及其改进形式，如多宇宙并行进化方法 优化量子旋转门、采用自适应调整搜索网格的策略对量子旋转门更新、采用混沌 理论更新量子旋转门、采用二相位方案实现量子状态预置等。王凌等人将量子搜 索和传统遗传搜索结合，提出了混合量子遗传算法的框架【3 6 1 ，给出了基于二进制 编码的混合量子遗传算法和基于实数编码的混合量子遗传算法，分别采用量子搜 索空间和遗传码空间混合搜索和量子搜索和遗传搜索的多方位混合，增强了搜索 能力，避免了早熟收敛。周殊等学者提出了一种基于粒子群优化方法的量子遗传 算法【37 1 ，在更新操作中不使用量子遗传算法常用的量子门，而是使用粒子群优化 方法来更新量子状态。王宝伟等提出了一种改进的混合量子遗传算法【3 引，在量子 个体上实施量子交叉，以保留相对较好的基因段，并采用量子比特相位法更新量 子门和自适应调整搜索网格的策略，最后引入拟n e w t o n 算法进行局部搜索操作， 使得种群更具多样性，提高了收敛速度。 量子遗传算法利用量子态叠加、量子纠缠及量子计算内在并行性的特点，其 染色体采用量子比特进行编码。因为量子比特可以表达无限个的中间态，所以一 个量子染色体可表示多个状态的信息，使得种群信息非常丰富，从而保持群体的 多样性。在搜索过程中，量子遗传算法通过选择操作不断增多适应度高的个体， 并根据量子坍塌的机理，随机的产生新个体，以此保持了种群的多样性。量子遗 传算法使用量子变换完成遗传搜索操作，较大程度的提高了算法的搜索性能。 量子遗传算法与传统遗传算法的相应概念的比较如表2 1 所示。 9 第二章量子计算概述 表2 1q g a 与g a 的比较 算法染色体编码方式交叉操作变异操作 g a二进制、实数、符号等两个个体之间随机变换 q g a 量子位种群中所有个体量子门变换等 对量子遗传算法的研究还处于起步阶段，其相关的应用也局限于有限的几个 方面。文【3 9 采用遗传量子算法求解o 1 背包问题，采用1 0 0 个、2 5 0 个和5 0 0 个 物体的标准数据，用遗传量子算法进行优化求解，结果明显优于传统遗传算法， 验证了算法的高效性。文【4 0 】采用量子遗传算法进行函数优化，选取d ej o n g 的单 峰函数和r o s e n b r o c k 多峰函数作为优化的对象，其结果明显优于传统遗传算法和 遗传量子算法。文【4 1 】应用量子遗传算法进行金融信息的数据挖掘，求解时间序列 中频繁模式发现问题，取得了满意效果。文【4 2 1 将量子遗传算法与独立分量分析 ( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ，i c a ) 算法结合，提出基于量子遗传算法的盲 源分离新算法，其仿真结果表明算法运算效率比传统遗传算法高5 至1 5 倍。 由于采用量子比特对染色体进行编码，q g a 的一条染色体可以表示所有状态 的叠加态。因此与g a 相比，q g a 具有更好的种群多样性，这就大大减少了需要 计算的染色体数量，使得q g a 具有更高的搜索效率和收敛速度。由于每个量子位 是由当前最优解的个体的概率幅决定的，量子染色体中的个体之间的联系比较弱， 所以q g a 比g a 更适于并行结构的实现。 理论上，凡是可以采用遗传算法优化求解的领域都是量子遗传算法的应用对 象，因而比起传统遗传算法，量子遗传算法目前的应用范围远远不够。扩大量子 遗传算法的应用范围是当务之急。所以，量子遗传算法进一步的研究内容将主要 在两个方面：求解具有挑战性的计算问题的应用研究和基础理论研究。 ( 1 ) 扩大应用领域是q g a 研究的主要方向。其研究内容应包括：面向具体 的重大挑战问题的算法设计是研究的主流，特别是与并行计算相互结合，具有重 大的现实意义；将q g a 与传统优化算法结合是面向问题的算法设计的有效途径， 可以充分发挥两者的优势，构造出性能更好的算法；与其他学科和技术结合，如 工程学、电子学、机器人学等，有望形成全新的学科领域。 ( 2 ) 量子遗传算法问世不久，还处于初步试探阶段，其理论基础还很薄弱， 1 0 西北大学硕士学位论文 后续的理论研究可能集中在以下几个方面：算法收敛性的分析是理论研究的一个 主要方面，对算法的设计和进步的改进有直接的指导意义；建立q g a 机理分析 的数学模型，是改进收敛性、提高收敛速度分析和对算法各成分进行分析的基础： 理论研究的另一个重要方面是对q g a 的计算复杂性的研究，其目的是对算法的性 能分析提供客观的评价标准；建立量子遗传算法统一的理论基础更是算法理论研 究的重任，是理论研究的根本目标。 2 4 量子神经网络研究现状 美国的k a k 教授最早将量子理论与神经计算相结合，提出量子神经计算的概念 【1 3 】，掀起了量子神经计算领域的研究热潮。目前提出的量子神经网络有着不同的 特点，不同程度地利用了神经网络和量子计算的特性，有的研究推动了量子计算 的进展，有的研究改进神经网络的性能。神经计算与量子理论结合所对应的主要 概念如表2 2 所示。 表2 2 量子理论与神经计算模型的对应概念 量子理论神经计算模型 波函数神经元 态叠加( 相干)内部连接( 连接权) 测量 消相干或坍缩趋向吸引子的演化 态纠缠学习规则 幺正变换增益函数( 变换) 2 4 1 多层激活函数的量子神经网络 k a r a y i a n n i s 等学者于1 9 9 7 年提出多层激活函数的量子神经网络【1 5 ，16 1 ，对该模 型进行了理论分析，并实验验证了它对模式分类问题具有内在模糊性，能够检测 到数据中固有的模糊性和不确定性，特别是对于两类数据有交叉的数据，q n n 模 型能以一定的隶属度将数据同时分在两类中。 多层激活函数的量子神经网络采用传统的三层网络拓扑结构。借鉴了量子态 叠加的思想，其隐含层的量子神经元的激活函数形式表示为多个s i g m o i d 函数的线 性叠加，故称为多层激活函数。所以q n n 模型的隐含层神经元不同于采用单激活 1 1 第二章量子计算概述 函数的b p 网络的隐含层神经元。一个s i g m o i d 函数只能表示两个状态，而具有多个 不同的量子间隔的多层激活函数则能够表达更多的状态。每个量子间隔对应不同 的量子能级，可以分别对应不同的状态，因此通过调整量子间隔，使不同类的数 据映射到不同的量子能级上，使得分类具有更多的自由度。 多层激活函数量子神经网络的学习分为两步：一是对权值的调整，二是对隐 含层量子神经元的量子间隔进行调整。对权值的调整可使输入数据对应到不同类 空间中，而量子间隔则能体现数据的不确定性。q n n 模型具有固有的模糊特性， 已经成功应用于模式分类领域。本文主要对该模型进行研究和改进。 2 4 2 q u b i t 神经元模型 该模型于2 0 0 0 年由日本学者提出 1 7 , 1 8 l ，是利用量子比特表示神经元状态的网 络模型。其网络拓扑结构和传统的神经网络相同，但神经元信息表示方法、权值、 激活函数等都与不同于传统的神经网络。q u b i t 神经元模型采用量子态表示信息， 通过改变量子态可以达到计算的目的。对量子态的相位的旋转变换是通过网络权 值的作用进行的，激活函数的作用则是对相位进行可控非门操作。q u b i t 神经元模 型的输入只能是0 、l 值，输出则是概率幅值，限制了该模型的应用。目前，q u b i t 神经元模型仅在逻辑门操作、奇偶检验等方面进行了实验。 2 4 3 多宇宙的量子神经网络模型 t a m m y 等学者从双缝干涉实验和量子力学中多宇宙观点得到启发，提出了多 宇宙的量子神经网络模型【1 9 】。该