量子算法

量子算法目录•量子计算理论•量子神经计算•量子神经网络模型•量子遗传算法绪论通信系统的理论模型信息学理论——研究信息的产生、存储、加工、传播等行为的科学理论编码器信道噪声源译码器信宿干扰消息信号+干扰信号消息信源1.信源—产生消息和消息序列的源2.编码器—把信息转化为信号的设备（1）信源编码器：提高信息传输的效率（2）信道编码器：提高信息传输的可靠性3.信道—通信系统把载荷消息的信号从甲地传输到乙地的媒介4.译码器—对信道输出的编码信号进行逆变换的设备5.信宿—消息传送的对象编码器信道噪声源译码器信宿干扰消息信号+干扰信号消息信源1928年哈特来（R.V.L.Hartley）首先提出了“信息”这一概念。1948年控制论创始人维纳（N.Wiener）指出“信息是信息，不是物质，也不是能量”。1948年香农（C.E.Shannon）对信息及其行为进行了定性和定量的描述。香农给出了两个著名的基本定理：（1）信源编码定理也称无噪编码定理或香农第一编码定理，定量的给出了用于存储从信源发出信息所需要的物理资源；（2）信道编码定理也称含噪编码定理或香农第二编码定理，定量的给出了有噪声的信道能可靠传输信息的量。量子信息学——一门新兴的、以量子力学与经典信息学理论为主干的交叉性学科。信息学量子力学量子信息学量子通信量子计算量子隐形传态量子密钥分发量子计算机量子算法量子信息与量子计算的基本概念§1.1量子信息§1.2经典解读§1.3量子逻辑门（量子逻辑电路）简介§1.4图灵机、经典计算机与量子计算机§1.5有关量子信息编码的基本概念现代物理将微观世界中所有的微观粒子（光子、电子、原子等）统称为量子。量子假说：对于一定频率的电磁辐射，物体只能以此最小单位吸收或发射它，换言之，吸收和发射电磁辐射只能以“量子”方式进行，每个“量子”的能量可以表示为:h1.量子§1.1量子信息一、量子力学基础式中为普朗克常数。h(1.1-1)2.态矢量描述微观粒子在三维空间运动的波函数ψ可以用坐标矢量r=(x,y,z)和时间t的复函数ψ（r,t）来表示。粒子的波函数也叫做几率幅，其模的平方表示在时刻t粒子出现在位置r上的几率密度。2*(,)(,)(,)rtrtrt微观粒子的波函数也可用Dirac符号表示，即复矢量空间的右矢也可用于表示波函数。叫做态矢量，它可以用n维复矢量空间的列矢量表示:12naaa12,,,naaa为坐标矢量r,时间t和自旋S的函数(1.1-2)(1.1-3)利用Dirac符号，两个量子态和的叠加态可以表示为：12cc右矢量的复共轭矢量叫做左矢量，n维左矢量可以表示为：†***12,,,naaa波函数满足归一化条件：1n维矢量空间中单位矩阵可以用任意的、构成完备系的基矢表示：iiIii(1.1-4)(1.1-5)(1.1-6)(1.1-7)从而，态矢量可以表示成基矢的线性组合iiii其中，基矢满足正交、归一条件iijij各种可观测量叫做作用于波函数上的算符。任何一个物理量算符A的期待值或平均值为：*,,AArtArtdr物理量A的测量值必须为实数(1.1-8)(1.1-9)(1.1-10)3.自旋1/2体系的量子态自旋的粒子在z轴方向的投影只有自旋向上和向下两种可能，因此可自旋的粒子的状态可用二分量矢量来表示。朝z轴正向的自旋（自旋向上）态和朝z轴负向的自旋（自旋向下）态可用列矢量表示:12120110(1.1-11)自旋的粒子的自旋角动量算符可以表示为：1212S(1.1-12)因为态矢量和均为二分量，自旋角动量算符应为2×2矩阵。式（1.1-12）中2×2矩阵的x,y,z的分量分别为:0110x00yii1001z(1.1-13)Pauli自旋矩阵【例1.1-1】试用自旋算符，的本征态和表示的本征态。2Szsxs解设的本征值为和的本征态分别记作和，的本征值为和的本征态分别记作和。将用的本征态和展开，则xsxxzszz12121212xzszzxzzaabb(1.1-14)由的归一化条件可得x221xxab(1.1-15)由Pauli矩阵的本征值方程xxxx(1.1-16)即0110ababab(1.1-17)得到ab(1.1-18)再利用式（1.1-15）得到，因此最后得到的自旋向上的本征态：12abxs1()2xzz(1.1-19)对于，利用xxxx(1.1-20)或者0110ababab(1.1-21)得到ab(1.1-22)从而有(1.1-23)由式(1.1-19)和式(1.1-23)很容易验证两个本征矢的正交性0xx(1.1-24)1()2xzz二、量子信息利用微观粒子状态表示的信息称为量子信息量子信息的载体可以是任意两态的微观粒子系统。图1.1－1具有两个电子层面的原子可以表示量子信息Quantumrepresentedbytwoelectroniclevelsinanatom微观粒子系统举例：◆光子具有两个不同的线偏振态或椭圆偏振态；◆恒定磁场中原子核的自旋；◆具有二能级的原子、分子或离子；◆围绕单一原子自旋的电子的两个状态（如图1.1-1）等。三、量子信息的基本存储单元及其特性经典信息的基本存储单元——比特（bit），可以由经典状态1和0（如电压的高低）表示。量子信息的基本存储单元——量子比特(qubit)，一个量子比特的状态是一个二维复数空间的向量，它的两个极化状态和对应于经典状态的0和1。01100011(1.1-25)a01b(1.1-26)n个量子比特的状态：121,2,,nn(1.1-27)一个量子比特能够处于既不是又不是的状态上，而是处于和的一个线性组合的所谓中间状态之上，即处于和的叠加态上。000111利用量子的某一状态表示信息时，我们就说信息量子化了并称为量子信息由于信息载体（量子）的微观特性，量子信息就变的多姿多彩。这些微观特性主要表现在：①量子态相干性：微观系统中量子间相互干涉的现象成为量子信息诸多不可思议特性的重要物理基础；②量子态纠缠性：N(大于1)个量子在特定的(温度、磁场)环境下可以处于较稳定的量子纠缠状态，对其中某个子系统的局域操作会影响到其余子系统的状态；③量子态叠加性：量子状态可以叠加，因此量子信息也是可以叠加的，所以可以同时输入和操作N个量子比特的叠加态；④量子不可克隆定律：量子力学的线性特性确保对任意量子态无法实现精确的复制，量子不可克隆定律和测不准原理构成量子密码术的物理基础。用量子比特存储量子态表示信息是量子信息的出发点。量子力学理论描述量子信息演绎的行为。薛定谔方程制约着量子态信息的每一步演变，线性代数的幺正变换约束着可逆的量子态信息计算；量子信息的传输是由量子通道端点上量子纠缠集合状态的变化（微观客体的关联具有非局域的性质，且可以延伸到很远的距离），结果信息的获取便是在得到输出态之后，量子计算机对输出态进行一定的测量后给出的结果。用量子比特存储量子态表示信息是量子信息的出发点。用量子比特存储量子态表示信息是量子信息的出发点。§1.2经典解读一、薛定谔猫和EPR佯谬1.薛定谔猫薛定谔猫的实验装置巧妙地将微观放射源和宏观的猫联系起来2.EPR佯谬量子力学是否自洽是否完备“EPR佯谬”思想实验爱因斯坦(A.Einstein)波多尔斯基(B.Podolsky)罗森(N.Rosen)玻尔这场争论的本质——真实世界是遵从爱因斯坦的居于实在论，还是玻尔的非局域理论？判定这场战争的依据——基于爱因斯坦的隐参数理论推到得到的贝尔不等式§1.4图灵机、经典计算机与量子计算机一、图灵机与经典计算机经典计算机实际上就是一个通用图灵机（Turing-machine，简称TM）图灵机的基本模型记忆单元：可以想象成一条磁带（Tape）处理单元：可以想象成一个读写头（Head）控制单元Tape0…54321…Head0qTape0…54321…Head0qaTape0…54321…Headb1qTM运算过程TM正式定义：M=(Q,,)有限状态集转移函数有限带符号集磁带上空白用#或B表示转移函数:QQ{L,R,N}二、量子计算机1.量子计算机概念的出现◆量子信息理论的研究起始于二十世纪七十年代的光量子通信研究。◆二十世纪八十年代初，计算机科学的研究领域里就出现了量子计算机的概念。◆在进入九十年代之后由E.Bernstein和U.Vazirani俩位对量子计算机在数学上给予严格的形式化描述2.量子计算机与可逆计算量子计算机——一类遵循量子力学规律存储量子信息、实现量子计算的物理装置。当某个装置处理和计算的是量子信息，运行的是量子算法时，它就是量子计算机。经典计算机特点量子计算机特点（A）量子计算机的输入态和输出态为一般的叠加态，其相互之间通常不正交；（B）量子计算机中的变换为所有可能的幺正变换。得出输出态之后，量子计算机对输出态进行一定的测量，给出计算结果。（A）经典计算机输入态和输出态都是经典信号；（B）经典计算机内部的每一步变换都将正交态演化为正交态。通用图灵机是不可逆的。但Bennett证明了，所有经典不可逆的计算机都可以改造为逆计算机，而不影响其计算能力。量子计算机的概念源于对可逆计算机的研究！！！abababbab图1.4-1不可逆异或门改进为可逆异或门D-WAVE量子计算机量子计算机是一种遵循量子力学规律，进行高速运算、存储及处理量子信息的物理装置，其运行的是量子算法，处理速度惊人，比传统计算机快数十亿倍。囚禁原子是原子物理学的一种新的实验平台，研究人员可以用此方法自由操纵单个原子，此步奏完成后，就可以开始冷却原子。可以说，囚禁原子是量子计算机的通用方案。冷冻原子激光控制原子§2.1经典比特、量子比特及其叠加状态记述经典信息的二进制存储单元称为经典比特(bit)，经典比特由经典状态的1和0表示记述量子信息的基本存储单元称为量子比特(qubit)，一个量子比特的状态是一个二维复数空间的向量，它的两个极化状态和对应于经典状态的0和1。01qubit可以去无限多个值bit只能取0和1值§2.2量子比特的测定如何从一个qubit获得所要的（经典）信息？a01b如何确定的知道a和b的值可以通过一个测定的过程，将一个qubit的状态以概率幅的方式变换成bit信息量子比特将以下列方式被转换，以概率变换成bit022200001aba概率变换成bit122211011abb量子位•量子位（qubit）是量子计算的理论基石。在常规计算机中，信息单元用二进制的1个位来表示，它不是处于“0”态就是处于“1”态.在二进制量子计算机中，信息单元称为量子位，它除了处于“0”态或“1”态外，还可处于叠加态叠加态是“0”态和“1”态的任意线性叠加，它既可以是“0”态又可以是“1”态，“0”态和“1”态各以一定的概率同时存在.通过测量或与其它物体发生相互作用而呈现出“0”态或“1”态.任何两态的量子系统都可用来实现量子位，例如氢原子中的电子的基态（groundstate）和第1激发态（firstexcitedstate)、质子自旋在任意方向的+1/2分量和-1/2分量、圆偏振光的左旋和右旋等。•一个量子系统包含若干粒子，这些粒子按照量子力学的规律运动，称此系统处于态空间的某种量子态.态空间由多个本征态（eigenstate)（即基本的量子态）构成，基本量子态简称基本态（basicstate）或基矢（basicvector).态空间可用Hilbert空间（线性复向量空间）来表述