2.4 量子进化算法

量子力学和信息学看似是两个相隔遥远的学科，但它们的结合却产生了一个可能在根本上影响人类未来发展的交叉学科——量子信息学。二十世纪后半叶，人类进入信息时代，计算机的发展日新月异。但随着计算机芯片的集成度越来越高，元件越做越小，集成电路技术现在正逼近其极限，尽管计算机的运行速度与日俱增，但是有一些难题是现有计算机根本无法解决的，例如大数的因式分解等。几十年前，该领域的一些先驱者，如美国IBM公司的Charles H.Bennett等人就开始研究信息处理电路未来的去向问题，他们指出，当计算机元件的尺寸变得非常小时，我们不得不面对一个严峻的事实：现有经典的描述不再适用，必须用量子力学来对它们进行描述。

2.4.1 量子计算概念的产生和发展

量子计算（Quantum Computation，QC）的概念起源于对可逆计算机的研究，最早由诺贝尔物理学奖获得者Feynman在1982年提出，量子计算是相对于经典意义上的计算而言，它是基于量子力学而非经典物理学的思想进行计算的。1985年，牛津大学的Deutsch在他的论文中提出了任何物理过程原则上都能很好地被量子计算机模拟的方案，他的这种方案被普遍认为是量子计算机的第一个蓝图，他的工作在量子计算机发展中具有里程碑式的意义。Deutsch建立了量子网络和量子逻辑门的概念，对后来研究量子计算有着非常重要的意义。1992年，Deutsch在量子力学迭加原理的基础上提出了D-J算法。到二十世纪九十年代初期，人们开始寻找能够发挥量子计算机优点的途径，1994年，美国贝尔实验室的Shor设计了一个具体的量子算法，这个算法在设想的量子计算机中竟然能有效地进行大数的质因式分解。这意味着以大数质因式分解算法为依据的电子银行、网络等领域的RSA公开密钥密码体系将在量子计算机面前不堪一击。Shor算法的提出使量子计算和量子计算机的研究有了实际应用背景，因而也获得了新的推动力。几年后，Grover又发现了未加整理的数据库搜索Grover迭代算法——量子搜寻算法。利用这种算法，在量子计算机上可以实现对未加整理数据库量级加速搜索，而且用这种加速搜索有可能解决经典的所谓的NP问题，可以破译DES密码体系。1996年，Lloyd S证明了Feynman的猜想，他指出模拟量子系统的演化将成为量子计算机的一个重要用途，量子计算机可以建立在量子图灵机的基础上。由于量子计算机具有巨大的应用前景和市场潜力，于是各国政府纷纷投入大量的资金和科研力量进行量子计算机的研究。近几年，量子计算和量子计算机的理论和实验研究都呈现出迅猛发展的势头，已经从最初仅是学术上感兴趣的对象，变成对计算机科学、密码科学、通信技术及国家安全和商业应用都有潜在重大影响的领域，从而引起广泛的关注。如今这一领域已经形成一门新的学科——量子信息学。

2.4.2 量子计算的物理原理

从物理的观点看，计算机是一个物理系统，计算则是这个系统演化的物理过程。经典信息系统以一个位或比特（bit）作为信息单元，一个比特是一个有两个状态的物理系统，它可以制备为两个可识别状态中的一个，如是或非，真或假，0或1。在数字计算机中，一个电容器极板之间的电压可表示为信息比特，有电荷代表1，无电荷代表0。在量子信息系统中，常用量子位或量子比特（qubit）表示信息单元。量子计算机是用二态的量子力学系统来描述两位信息的，这里的二态是指两个线性独立的态，例如两种偏振态的光子（水平和垂直偏振）、磁场中自旋为1/2的粒子（自旋向上和向下）、两能级的原子或离子（基态和激发态）及量子系统的空间模式（例如光子）等。对于半自旋粒子系统（如电子），这两个独立态常记为|0＞和|1＞（|0＞表示自旋向上态，|1＞表示自旋向下态）。以这两个独立态为基矢，张起一个二维复矢量空间，所以也可以说一个qubit就是一个二维Hilbert空间，1个量子比特就是这个二维希尔伯特空间的单位矢量。因此，也可以用1个单位球面上的点（见图2.4）表示1个量子比特的纯态，由欧拉（Euler）角θ和φ决定（整体的相因子通常可以忽略）点的位置，这个球被称为布洛赫（Bloch）球。经典比特可看成量子比特的特例（令α=0或β=0），对应于布洛赫球上的两个极点，1量子比特信息包含了1比特的信息，同时连续变化，可以覆盖整个球面，所以1量子比特可以运载更多的信息量。

一个量子比特可以处于两个逻辑态0和1的任意叠加，。态的线性叠加是理解量子计算机运作的关键。这种线性化特征意味着对叠加态的任一操作都产生对各个态单独操作的叠加。在经典计算机中不存在类似的原理，这也是量子计算机超出经典计算机的一个重要因素。同时，叠加性也允许一种奇特现象的存在，即量子纠缠（entanglement）。所谓量子纠缠就是一个完整的量子系统的态不能用单个的量子位的态来描述。用量子力学的测量理论也可解释为两个量子位是纠缠的，当且仅当对一个量子位的测量影响了另一个量子位的态。

量子系统的态演化遵从Schrodinger方程。为了保证系统的总概率不变，演化算子必须是幺正算子。一些常见的幺正算子有：

其中，I是恒等算子，X是非算子，Z是相位移动算子。另外一个非常重要的变换是Walsh-Hadamard变换，定义为：

这个算子作用到，产生一个叠加态。作用到的n位寄存器上，结果是：

由于可以制备经典的不同态的叠加态，量子计算机对叠加态的演化就是对其中各个叠加成分的演化，即同时沿着经典上互不相同的路径计算，这就是所谓的量子并行（Quantum Parallelism），量子计算机具有的超出经典计算机信息处理能力，就源于它的这种高度并行计算能力。

量子寄存器的态由测量确定。一旦测量完成，系统就坍缩（Collapse）到所测量到的态，而所有其他信息都丢失了。这种测量坍缩过程是随机的、不可逆的、斩断相干的和非定域性的。由于测量量子计算结果输出的不唯一性，因此在计算过程中，只有充分利用概率幅的相长或相消干涉，尽可能地增大需要结果出现的概率，同时减小不需要结果出现的概率，以最大的概率得到需要的结果，完成量子计算的过程。

2.4.3 量子计算与经典计算相比的重要特点

量子算法是相对于经典算法而言的，它最本质的特征就是利用了量子态的叠加性和相干性，以及量子比特之间的纠缠性，是量子力学直接进入算法领域的产物，它和其他经典算法最本质的区别就在于它具有量子并行性。我们也可以通过概率算法去认识量子算法。在概率算法中，系统不再处于一个固定的状态，而是对应于各个可能状态各有一个概率，即状态概率矢量。如果知道初始状态概率矢量和状态转移矩阵，通过状态概率矢量和状态转移矩阵相乘可以得到任何时刻的概率矢量。量子算法与此类似，只不过需要考虑量子态的概率幅度，因为它们是平方归一的，所以概率幅度相对于经典概率有了倍的放大，状态转移矩阵则用Walsh-Hadamard变换、旋转相位操作等幺正变换实现。量子算法作为控制量子计算机运行的程序，显示出高效的运算能力。

1．状态的叠加

在经典数字计算机中，信息被编码为位（Bit）链。1比特信息就是两种可能情况中的一种，0或1，假或真，对或错。在量子计算机中，基本的存储单元是一个量子位（Q-bit）。一个简单的量子位是一个双态系统。例如半自旋或两能级原子，自旋向上表示0，自旋向下表示1，或者基态代表0，激发态代表1。不同的是，一个量子位除了可以处于0态和1态之外，还可以处于它们的叠加态。为了便于表示和运算，Dirac提出用符号|x＞来表示量子态。一个量子位的叠加态可用二维Hilbert空间（二维复向量空间）的单位向量|ψ＞来描述，|ψ＞=α|0＞+β|1＞，|α|²+|β|²=1，其中α、β为代表相应状态出现概率的两个复数，|α|²、|β|²分别表示量子比特处于状态0和状态1的概率。一个n位的普通寄存器处于唯一的状态中，而根据量子力学的基本假设，一个m位的量子寄存器可处于2^m个基态的相干叠加状态|ψ＞中，即可以同时表示2^m个数。叠加态和基态的关系可以表示为：

其中，C_k为|ψ＞在受到量子计算机系统和纠缠的测量仪器观测时坍塌到基态|S_k＞的概率，满足归一化条件|C₁|²+|C₂|²+…+|C₂^m|²=1。

2．状态的相干

量子计算的一个主要原理就是使构成叠加态的各个基态通过量子门的作用发生干涉，从而改变它们之间的相对相位。如一个叠加态为，设量子门作用在其上，结果为，可以看到基态|0＞的概率幅度增大，而|1＞的概率幅度减小。若量子系统|ψ＞处于基态的线性叠加的状态，我们称系统为相干的。当一个相干的系统和它周围的环境发生相互作用（测量）时，线性叠加就会消失，具体坍塌到某个基态|S_k＞的概率由|C_k|²决定。如对于上面的|ψ＞进行测量，其坍塌到|0＞的概率为0.9，这个过程称为消相干。

3．状态的纠缠

量子计算另一个重要的机制是量子纠缠态，但它违背我们的直觉。对于发生相互作用的两个子系统中所存在的一些态，若不能表示成两个子系统态的张量积，则这样的态就被称为纠缠态。对处于纠缠态的量子位的某几位进行操作，不但会改变这些量子位的状态，还会改变与它们相纠缠的其他量子位的状态。量子计算能够充分实现也是利用了量子态的纠缠特性。

4．量子态随时间演化的幺正性

孤立量子系统的态矢量|ψ＞随时间的演化遵从Schrodinger方程：。

5．量子态不可克隆性

量子力学的线性特性禁止对一个未知的量子态进行精确的复制（克隆）。

6．量子测量公设

量子一经测量，系统就坍缩到所测量到的态。这种测量坍缩过程是随机的、不可逆的、斩断相干的和非定域性的。由于测量量子计算结果输出的不唯一性，因此在计算过程中，只有充分利用概率幅度的相长或相消干涉，尽可能增大需要结果出现的概率，同时减小不需要结果出现的概率，使对计算末态的测量以最大的概率得到需要的结果，完成量子计算的过程。

7．量子隐形传态

量子隐形传态应用了量子特性来实现信息的传送和处理。其信息容量大，可靠性高。这种方法能完成纯经典方法或纯量子方法所无法做到的量子态传送。

但是到目前为止，人们还没有制造出一台实际运作的量子计算机，实现量子计算机的困难在于量子系统既要有效地被外界控制，又要与环境很好地隔离。科学技术的发展过程充满了偶然和未知，就算是物理学泰斗爱因斯坦也决不会想到，为了批判量子力学而假想出来的EPR态，在六十多年后不仅被证明是存在的，而且还被用在量子信息中。相信随着技术的进步和量子计算机结构设计上的发展，实用量子计算机会被建造出来，并像现在的经典计算机一样无处不在，给我们的生活带来巨大的影响。

2.4.4 量子进化算法的数学描述

前面我们提到，进化算法是模拟自然进化过程的一类随机搜索和优化技术。虽然同传统的优化方法相比（例如基于微积分的方法和穷举法），进化算法是鲁棒的、全局的和不依赖问题知识的，但是这类方法本身也存在着不足，比如对开发（Exploitation）和探寻（Exploration）的平衡能力较差，换句话说，群体的多样性（Population Diversity）和选择性压力（Selective Pressure）不容易同时实现——强的选择性压力导致搜索过早收敛，弱的选择性压力使搜索毫无效率。另一方面，算法对进化个体过去的历史信息没有加以利用，于是，人们提出了各种各样的改进方法。量子驱动的进化算法（简称为量子进化算法，Quantum-inspired Evolutionary Algorithm，QEA）是新近发展起来的一种概率进化算法，是量子计算与进化计算理论相结合的产物。它以量子计算的一些概念和理论为基础，用量子位编码表示染色体，通过量子门更新种群来完成进化搜索，与传统进化算法相比，能够更容易地在探索与开发之间取得平衡，具有种群规模小、收敛速度较快、全局寻优能力强等特点。

1．染色体表示

在进化算法中，可以使用许多不同的表示方法把解编码为染色体，经典的编码方式有二进制、十进制和符号编码。在量子进化算法中，可以使用一种新颖的基于量子比特的编码方式，即用一对复数定义一个量子比特位。一个具有m个量子比特位的系统可以描述为：

其中，|α_i|²+|β_i|²=1，i=1，2，…，m，0≤|α_i|≤1，0≤|β_i|≤1。这种表示方法具有能够表征叠加态的优点，例如一个具有如下概率幅度的3个量子比特系统：

则系统的状态可以表示为：

上面结果表示态|000＞、|001＞、|010＞、|011＞、|100＞、|101＞、|110＞和|111＞，出现的概率分别为、、、、、、和。因此，式（2-17）这个3个量子比特的系统包含了8个态的信息。

由于使用量子比特染色体能够表征叠加态，因此，具有量子比特表示的进化算法比经典的进化算法具有更好的多样性。如在上例中，一个量子比特染色体足以表示8个态，而在经典进化算法中至少需要8个染色体（000）、（001）、（010）、（01l）、（100）、（101）、（110）和（111）来表示。由此可知，如果有m位的量子比特系统，可同时表示2^m种状态（即2^m种基态），并且量子状态由2^m个幅度所确定。因而在对量子比特计算时，一次运算相当于对2^m种状态同时操作，这就是量子并行性的由来。所以一个量子比特所包含的信息要比经典的比特多。同时，量子进化算法也具有良好的收敛性，随着|α_i|²或|β_i|²趋于1或0，量子比特染色体收敛到单个态，这时多样性逐渐消失，算法收敛。因此，量子染色体表示同时具有开发和探测两种特性。

2．算法描述

量子进化算法的基本结构描述如下。

QEA是一种与进化算法类似的概率算法。在第t代，量子染色体的群体为，其中n为群体规模，而定义为如下的染色体：

其中，m为量子比特的数目，即量子染色体的长度；j=1，2，…，n。

在初始化群体Q（t）中，所有中的和可都被初始化为。这意味着一个量子染色体以下列相同的概率表示了所有可能的线性叠加态，可表示为：

其中，S_k是用二进制串（x₁，x₂，…，x_m）表示的第k个状态。x_i（i=1，2，…，m）为0或者为1。在“由Q（t）生成P（t）”这一步中，通过观察Q（t）的状态，产生一组二进制解的集合P（t），其中在第t代中，，每个二进制解是长度为m的二进制串，其中的每一位是通过使用量子比特的概率，即中或得到的，具体过程为：生成一个[0，1]内的随机数r，如果r＞|α_i|²，则x_i取值为1，否则取值为0。接下来对每个解进行评价，得到其适应度值，然后在初始的二进制解集P（t）中选择最优解，并保存下来。

在while循环中，步骤“更新Q（t）”的目的是使量子染色体具有适应度更好的态。同前面描述的步骤一样，通过观察Q（t-1）的状态，产生一组二进制解集P（t），对每个二进制解进行评价，得到其适应度值。在接下来的“更新Q（t）”这一步中，使用某些合适的量子门U（t），对量子染色体群体Q（t）进行更新，其中的量子门是通过利用二进制解P（t）和所保存的最优解形成的。通常情况下，量子门都是根据实际的问题来设计的。需要指出的是：由于概率归一化条件的要求，量子门变换矩阵必须是可逆的归一化矩阵——幺正矩阵，满足U^*U=UU^*（U^*为U的共轭转置矩阵）条件。常用的量子门有旋转门、异或门、受控的异或门和Hadamard变换门等，其中旋转门可表示为：

其中，θ为旋转角度，在下一步中，选择P（t）中的最优解，如果这个解比所保存的最优解好，就用它取代所保存的最优解。循环结束后，保存下来的最优解就是最后希望得到的解。

从上面列出的量子进化算法的基本结构可以看出，量子进化算法采用量子门变异来进化种群，通过观察量子染色体的状态来生成所需要的二进制解，尽管量子门U（t）的选取是基于局部最优解的，但这依然是一个概率操作过程，具有很大的随机性，因此个体在进化的同时，也不可避免地产生退化的可能。