当前位置：文档库 › 量子算法报告

量子算法报告

量子算法

学院：

专业：智能科学与技术

姓名：

学号：

（一）引言

目前，国内外提出了大量的进化算法，如遗传算法、免疫算法、粒子群优化算法、差异进化算法、量子算法等智能计算优化算法。其中，量子遗传算法是量子计算与遗传算法相结合的产物。最近这一领域的研究主要集中在两类模型上：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法(Quantum Inspired Genetic Algorithm)，另一类是基于量子比特和量子叠加特性的遗传量子算法。前者的贡献在于将量子多宇宙的概念引入遗传算法，利用多个宇宙的并行搜索，增大搜索范围，利用宇宙之间的联合交叉，实现信息的交流，从而整体上提高了算法的搜索效率。但算法中的多宇宙是通过分别产生多个种群获得的，并没有利用量子态，因而仍属于常规遗传算法。后者将量子的态矢量表达引入遗传编码，利用量子旋转门实现染色体的演化，实现了比常规遗传算法更好的效果。但该算法主要用来解决0-1背包问题。不过，编码方案和量子旋转门的演化策略不具有通用性，尤其是由于所有个体都朝一个目标演化，如果没有交叉操作，极有可能陷入局部最优。

（二）算法介绍

2.1算法原理

量子遗传算法的提出基于量子理论的基本量子位和量子叠加态的概念。量子位或量子比特是量子计算中的最小信息单位，一个量子位可以有三种状态，即|0>态、|1>态、以及|0>与|1>之间的叠加态。因此任何一个量子比特的状态可以描述为|ψ>=α|0>+ β|1>,其中α、β称为量子位对应态的概率幅，且满足归一条件|α|2+|β|2=1

量子遗传算法中采用基于量子位的编码方式。一个量子位可由其概率幅定义

为[α

β]。同理，m个量子位可以定义为

α1α2?αm

β1β2?βm，其中

αi2+ βi2=1,i=1,2,…,m。这种描述的优点在于可以表达任意量子叠加态。

由于量子系统能够描述叠加态，因此基于量子位编码的进化算法，比传统算法具有更好的种群多样性，因为其一条染色体可以利用叠加态描述多个状态。当αi2和 βi2趋近于0或1时，多样性将逐渐消失，量子染色体会收敛到一个确定的状态。

2.2算法结构

量子遗传算法的伪代码如下：

Procedure QGA

Begin

t=0

Initialize Q(t)

Make P(t) by observing Q(t) states

Evaluate P(t)

Store the best solution among P(t)

While(not termination-condition) do

Begin

t=t+1

make p(t) by observing Q(t) states

evaluate P(t)

update Q(t) using quantum gate U(t)

store the best solution among P(t)

End

与遗传算法相似，QGA也是一种概率搜索算法，拥有一个量子种群Q（t）={ q t1，q t1，…q t n},其中n表示种群规模，t表示遗传代数，q t j表示一条量子染

色体，其定义为q j t=α1tα2t?αm t

β1tβ2t?βm t

，其中m是量子位数，即量子染色体的长

度，j=1,2，…，n。

具体步骤如下：

首先，将种群初始化（initialize Q(t)）,即将全部n条染色体的2mn个概率幅都初始化为

，它表示在t=0代，每条染色体以相同的概率处于所有可能状态的叠加态。其次，通过观察Q（t）的状态来生成二进制解集p（t）=x1t x2t?x n t,每个解x j t为一个长度为m的二进制串。然后，计算P（t）中每个解的适应度，存储最优解。

在循环中，首先通过观察种群Q（t-1）的状态，获得二进制解集P（t），计算每个解的适应度。之后，为了获得更加优良的染色体，通过将二进制解集P （t）与当前存储的最优解比较，用适当的量子门U（t）更新种群Q（t）。量子

门可根据实际问题具体设计，通常采用的量子门定义为U（θ）=cosθ?sinθsinθcosθ

，

其中θ是旋转角度。最后选择P（t）中的当前最优解，若该最优解优于目前存储的最优解，则用该最优解将其替换。

（三）算法研究进展

1996年，Narayanan和Moore等人将量子多宇宙的概念最先引入遗传算法，提出了Quantum Inspired Genetic Algorithm，并成功的用其解决了TSP问题，开创了量子计算与进化计算融合的研究方向。从算法机理上看，它与一种隔离小生境的遗传算法很相似，即利用多个种群的并行搜索，增大搜索范围，利用种群之间的联合交叉，实现种群之间的信息交流，将多个种群之间各自分散的搜索联系起来，从整体上提高了算法搜索的效率。

2000年，K．H．Han等人提出了一种量子遗传算法（Quantum Genetic Algorithm,QGA）,该方法将量子的态矢量引入遗传编码，利用量子的旋转门实现染色体基因的调整，使得该方法将来可以在量子计算机上执行，并且给出了一种基因调整策略。

2002年，K．H．Han在之前的基础上，引入了种群迁徙机制，并把算法更名为量子衍化进化算法。与传统进化算法相比，他最大的优点是具有更好的保持种群多样性的能力。

2004，Hichem等人提出了一种新的量子衍生遗传算法用于优化求解旅行商问题。该方法通过将量子计算的一些概念和原理引入普通遗传算法中，使新的量子遗传算法性能明显优于普通遗传算法。

2005年，Khorsand等人提出了一种多目标遗传算法，该方法对很多优化问题具有很好的适应性。特别是该方法构造了两层QGA，底层用于优化Dejong,Peak,Easoms和Griewank四种类型函数；高层用于确定算法的参数，通过与普通遗传算法相比，这种在寻优过程中能同时优化自身参数的方法具有明显的优势。同年，Moore等人提出一种用于优化组合逻辑电路的量子粒子群算法，该方法使用量子优化和局部量子群优化相组合的方法，并通过使用多目标函数以获得具有最少门电路的线路设计方案。实验表明，这种量子进化和粒子群混合优化的方法比单纯使用粒子群算法或其他进化算法更为优越。

2006年，Mikki等人针对电磁方面的优化问题，基于量子力学提出了一种量子粒子群算法，并将该算法应用于线阵天线，通过与一种改进的经典粒子群算法比较，在收敛速度和优化结果两方面明显优于经典粒子群算法。

目前，量子计算与进化算法的融合点主要集中在种群编码方式和进化策略

的构造上。在量子进化算法中，个体用量子位的概率幅编码，用基于量子门的量子比特相位旋转实现个体进化，用量子非门实现个体变异以增加种群的多样性。

（四）算法应用

背包问题是一类典型的组合优化问题，经常用于考察各类优化算法的性能。背包问题是指：在背包容量一定的情况下，如何从若干问题物品中，选出不同价值的适量物品，使其总价值最大。这个问题可以描述为：对m 个价值为p i 、体积为c i 的物品，如何将它们装入总体积为C 的背包中，使得所选物品的总价值最大。令X=（x 1，x 2，?x m ），x i =0,1。其中x i =1表示第i 件物品被选中，否则表示未被选中。

所以上述问题可以归纳为，选择适当的X ，当满足 c i x i m i=1≤?时，使得f （x ）= p i x i m i=1有最大值。

下面是量子遗传算法对于此问题的求解过程： Proceduce QGA Begin

Initialize Q(t)

Make P(t) by observing Q(t) states Repair P(t) Evaluate P(t)

Store the best solution among P(t) While(t

make p(t) by observing Q(t) states

repair P(t) evaluate P(t) update Q(t)

store the best solution among P(t)

End End

在QGA 中，每个染色体包含m 个量子比特，表示背包问题的一个可行解，其中m 是全部物品的数量。第i 件物品的选择概率是 βi 2或是1- αi 2。令X ∈P

（t ）为染色体q ∈Q （t ）的观测结果，观测流程如下：

Procedure make (X) Begin i=0

While (i

if random[0,1]>|a i |2 then x i =1 else x i =0 End End

修正算法的伪代码如下：

Procedure repair(X) Begin

Knapsack-overfilled=false

if c i x i m i=1>? then Knapsack-overfilled=True While (Knapsack-overfilled) do Begin

Select an i-th item from the knapsack X i =0

If c i x i m i=1≤? then Knapsack-overfilled=false End

While (Not Knapsack-overfilled) do Begin

Select a j-th item from the knapsack X j =1

If c i x i m i=1>? then Knapsack-overfilled=True End X j =0

End

量子染色体q j的更新是通过量子门来实现的，其中第i个量子位（αi，βi）

的更新过程为αi

βi=

cosθi?sinθi

sinθi cosθi

αi

βi。其中θi=s（αiβi）?θi，和?θi和θi=s（αiβi）

的取值如下表：

上述表中f（x）是目标函数；s（αiβi）是θi的符号；b i和x i分别是最优解和当前解中的第i个值。实际上，该表给出的是一种收敛策略。

染色体更新的伪代码如下：

Procedure update Q(t)

Begin

i=0

While (i

Begin

i=i+1

Determine θi with the lookup table

Obtain (αi,βi) as (αi,βi)= U(θi)(αi,βi)

End

经过试验论证，QGA在优化结果和运行时间两方面均优于普通GA。

（五）总结

时至今日，有关量子的知识还没有完全为人们所理解和掌握，量子的很多特性仍然不可解释，不过，这并不妨碍人们对已知知识的使用，量子遗传算法就是一个很好的例子。

从背包问题可以看出，该算法具有运行时间快速，结果优化度高等不可忽视优势，但与此同时，也暴露了一些缺陷，比如染色体更新所使用的量子旋转门不具有通用性，直接使用随机函数具有较高的盲目性等缺点。而且，就目前的研究进展，量子遗传算法所使用的范围比较有限,虽然适合于某些优化问题（如背包问题、旅行商问题等）但对于数值优化问题（如函数极值问题、神经网络权值优化问题等）由于需要频繁编码解码，加大了计算量。不过，相信通过继续发掘有关量子的知识，并将其新特性逐渐用到算法中来，并与其他智能算法相融合，量子遗传算法会日益完善，优势更加鲜明。

按照科学家的设想，通过量子计算机才可以充分发挥量子计算的并行计算优势。不过时至今日，量子计算机还没有完全走出实验室的大门。在这种情况下，深入研究量子算法及其他科学技术之间的相互作用，不断产生具有重要意义的概念和方法，并形成良好的工具也就成为量子信息处理领域的主要发展方向。

致力于经典信息处理研究的科技工作者们也应该开阔思维，毕竟，量子计算是一种与经典计算完全不同的全新的计算模式，它的很多特性还有待开发和应用。相信随着相关知识的挖掘，量子算法有着越加美好的未来。

（六）参考文献

[1] Kuk-Hyun Han,Jong-Hwan Kim.Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization

[2] 李士勇，李盼池. 《量子计算与量子优化算法》.哈尔滨工业大学出版社2009

[3] 焦李成，公茂果等. 《自然计算、机器学习与图像理解前沿》.西安电子科技大学出版社 2008

量子计算论文

量子计算在大三的第二学期我们学习了量子计算这门课程，初步了解了量子计算的一些方面，在下面的论文里将会简要的介绍量子计算的含义及其相关的知识。一．量子计算的含义量子计算是一种依照量子力学理论进行的新型计算,量子计算的基础和原理以及重要量子算法为在计算速度上超越图灵机模型提供了可能。量子计算(quantum co mputation) 的概念最早由IBM的科学家R. Landauer及C. Bennett于70年代提出。他们主要探讨的是计算过程中诸如自由能(free energy)、信息(informations)与可逆性(reversibility)之间的关系。80年代初期，阿岗国家实验室的P. Benioff首先提出二能阶的量子系统可以用来仿真数字计算；稍后费因曼也对这个问题产生兴趣而着手研究，并在1981年于麻省理工学院举行的First Conference on Physics of Comput ation中给了一场演讲，勾勒出以量子现象实现计算的愿景。1985年，牛津大学的D. Deutsch提出量子图林机(quantum Turing machine)的概念，量子计算才开始具备了数学的基本型式。然而上述的量子计算研究多半局限于探讨计算的物理本质，还停留在相当抽象的层次，尚未进一步跨入发展算法的阶段。 1994年，贝尔实验室的应用数学家P. Shor指出，相对于传统电子计算器，利用量子计算可以在更短的时间内将一个很大的整数分解成质因子的乘积。这个结论开启量子计算的一个新阶段：有别于传统计算法则的量子算法(quantum algorithm)确实有其实用性，绝非科学家口袋中的戏法。自此之后，新的量子算法陆续的被提出来，而物理学家接下来所面临的重要的课题之一，就是如何去建造一部真正的量子计算器，来执行这些量子算法。许多量子系统都曾被点名做为量子计算器的基础架构，例如光子的偏振(photon polarization)、空腔量子电动力学(cavity quantum electrodyn amics, CQED)、离子阱(ion trap)以及核磁共振(nuclear magnetic resonance, NM R)等等。量子计算将有可能使计算机的计算能力大大超过今天的计算机，但仍然存在很多障碍。大规模量子计算所存在的一个问题是，提高所需量子装置的准确性有困难。二．量子计算的发展史 1.梦想与惊喜始自第一个电子计算机开始运转,构想能够超越传统所谓Turing Machines 的计算模型,便是许多科学家努力的梦想.美国阿冈国家实验室的Paul Benioff是第一位提出概念,认为利用量子物理的二态系统模拟数位0与1,可以设计出更有效能的计算工具.此概念稍后又经Feynman的引申,使得有更多的物理学家注意到量子力学与计算科学之间可能的关联.直到1985年,在英国牛津的物理学家David Deutsch发表的一篇论文里,所谓Quantum Church-Turing Machines才正式开始略具数学雏型,但此论文中所提示的量子计算范例则过於简易.目前在美国,欧洲,日本以及中国大陆,已经有许多专为此新领域而成立的研究团队或研究机构。

量子化学计算方法试验

量子化学计算方法试验 1. 应用量子化学计算方法进行计算的意义化学是一门基础学科，具有坚实的理论基础，化学已经发展为实验和理论并重的科学。理论化学和实验化学的主要区别在于，实验化学要求把各种具体的化学物质放在一起做试验，看会产生什么新的物质，而理论化学则是通过物理学的规律来预测、计算它可能产生的结果，这种计算和预测主要借助计算机的模拟。也就是说，理论化学可以更深刻地揭示实验结果的本质并阐述规律，还可以对物质的结构和性能预测从而促进科学的发展。特别是近几年来，随着分子电子结构、动力学理论研究的不断深入以及计算机的飞速发展，理论与计算化学已经发展成为化学、生物化学及相关领域中不可缺少的重要方向。目前，已有多种成熟的计算化学程序和商业软件可以方便地用于定量研究分子的各种物理化学性质，是对化学实验的重要的补充，不仅如此，理论计算与模拟还是药物、功能材料研发环境科学的领域的重要实用工具。理论化学运用非实验的推算来解释或预测化合物的各种现象。理论化学主要包括量子化学，（quantum chemistry）是应用量子力学的基本原理和方法研究化学问题的一门基础科学。研究范围包括稳定和不稳定分子的结构、性能及其结构与性能之间的关系；分子与分子之间的相互作用；分子与分子之间的相互碰撞和相互反应等问题。量子化学可分基础研究和应用研究两大类，基础研究主要是寻求量子化学中的自身规律，建立量子化学的多体方法和计算方法等，多体方法包括化学键理论、密度矩阵理论和传播子理论，以及多级微扰理论、群论和图论在量子化学中的应用等。理论与计算化学的巨大进展，正使化学学科经历着革命性的变化。今天的理论与计算化学几乎渗透到现代一切科技领域，与材料、生物、能源、信息和环保尤为密切，理论化学的应用范围将越来越广。理论与计算化学逐步发展成为一门实用、高效、富有创造性的基础科学，在化学、生物学等领域的影响越来越显著，且与日剧增。 2. 应用量子化学计算方法进行计算的目的（1）了解量子化学计算的用途。（2）了解量子化学计算的原理、方法和步骤。（3）通过一两个计算实例进行量子化学计算的上机操作试验。（4）学会简单的分析和应用计算结果。 3. 量子化学计算试验的原理

差分进化算法-入门

基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法过两个父代个体的交叉产生两个子个体，而在差分进化算法过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。变异是DE 算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作设当前进化代数为t ，群体规模为NP ，空间维数为D ，当前种群为 {}12(),, ,t t t NP X t x x x =，()12,, ,T t t t t i i i iD x x x x =为种群中的第i 个个体。在进化过程中，对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作对于每个个体t i x 按下式产生变异个体12(,, ,)t t t t T i i i iD v v v v =，则 123() 1,2, ,D t t t t ij r j r j r j v x F x x j =+-= (1) 其中111112(,,,)t t t t T r r r r D x x x x =，222212(,,,)t t t t T r r r r D x x x x =和333312(,, ,)t t t t T r r r r D x x x x =是群体中随机选择的三个个体，并且123r r r i ≠≠≠；1t r j x ，2t r j x 和3t r j x 分别为个体1r ，2r 和3r 的第j 维分量；F 为变异因子，一般取值于[0,2]。这样就得到了变异个体t i v 。

量子计算的发展讲解学习

量子计算的发展

量子计算的发展摘要：量子计算是量子力学的新进展,它是一种和传统的计算方式迥然不同的新型计算.其概念是全新的,它将使计算技术进入一种前所未有的新境界。对于某些问题,量子计算机可以达到常规计算机不能达到的解题速度.量子计算机可以解决常规计算机不能解决的某些问题量子计算由于其强大的并行计算能力和可以有效的模拟量子行为的能力而日益受到人们的关注。本文介绍了量子计算的含义及其基本原理，以及对于未来量子计算的发展前景。关键词：量子计算；量子计算机；量子位

目录引言 (4) 1基本概念 (4) 1.1量子计算 (4) 1.2量子计算机 (4) 1.3量子位 (5) 2.量子计算的原理 (6) 2.1量子叠加性 (6) 2.2量子纠缠 (7) 3.量子计算的发展 (7) 3.1中期发展 (7) 3.2发展前景 (8)

量子计算的发展引言自MaxPlanck在1900年提出量子假说以来,量子力学给人类生活带来翻天覆地的变化,改变了经典物理学对世界的认知方式。量子计算和量子计算机概念起源于著名物理学家Feynman，是他在1982年研究用经典计算机模拟量子力学系统时提出的。1985年Deutsch提出第一个量子计算模型即图灵机，量子计算才开始具备了数学的基本型式。由此,量子计算迅速吸引了全世界研究者的注意并成为一门具有巨大潜力的新学科。 1. 基本概念 1.1量子计算量子计算是应用量子力学原理来进行有效计算的新颖计算模式,它利用量子叠加性、纠缠性和量子的相干性实现量子的并行计算。量子计算从本质上改变了传统的计算理念。 1.2.量子计算机