初识量子算法

初识量子计算——宋红芳摘要：量子计算是利用量子力学原理实现的一种新型计算。量子力学特性使得该算法相比于经典算法具有极大的优势，作为一个量子计算的初学者，作者将借由本文从量子比特出发简单介绍量子线路、量子算法的实现机制并引几个例子加强理解，同时介绍一下量子算法比经典算法快得多的原因。关键词：量子计算量子比特量子逻辑门量子线路量子并行性引言量子计算在70年代由IBM的科学家R.Landauer及C.Bennett提出以后就引起了科研人士广泛的兴趣，40年来该领域有了一定的发展，但是离人们的期望——实现大规模量子计算还有着很大的距离。那么，量子计算是如何利用量子力学知识实现的呢？能够实现的量子计算有哪些？量子计算与经典计算有什么区别？为什么比经典算法有绝对的优势？我们通过此文给出简要的回答。1.量子比特1.1量子比特的概念比特（bit）是经典计算与经典信息的基本概念，相应的，在量子计算与量子信息中也有类似的概念，称为量子比特（quantumbit或qubit）。就像经典比特有两个可能状态（0态或1态）一样，量子比特也有两个可能状态，分别记为|0态和|1态。那么，量子比特究竟是一个什么样的概念呢？它和经典比特一样，真实存在吗？实验证明，量子比特是真实存在的，并且可以用很多不同的物理系统实现。只要这个物理系统有两个不相干的状态，就可以用来表征量子比特的两个不同状态，比如：光子的两个不同的极化，均匀电磁场中核自旋的取向等。1.2量子比特与经典比特的区别我们知道经典计算机中的比特只能处于0态和1态中的一个，不是处于0态就是处于1态，而量子比特的状态可以落在｜0和｜1之外，处于二者的线性叠加态上：|Ψ=α|0+β|1，其中α和β是复数并满足|α|2+|β|2=1，也就是说量子比特的状态是二维复向量空间中的向量，而这个向量的基底是｜0和｜1态。在经典计算机中，我们可以通过检查知道比特是处于0还是处于1，但是却不可以通过测量得到量子比特所处的状态。由量子力学知识知道，如果我们测量状态|Ψ，那么我们有|α|2的概率得到|0态，|β|2的概率得到|1态，并且在我们测到结果的时候叠加态就坍缩到与测量结果相容的状态上了，我们测到的是状态|0或|1而无法知道分别处于这两个态的概率是多少，因而量子比特具有不可测量性。1.3量子比特的几何表示因为|α|2+|β|2=1，所以叠加态可以改写为|Ψ=𝑐𝑜𝑠θ2|0+eiφsinθ2|1(1.3.1),其中的ϕ和θ定义了单位球面上的一个点，这个球称为Bloch球，如下图所示：图1.1量子比特的Bloch球表示每取一对ϕ和θ值就对应着球面上的一个点，连接原点与该点就可以得到一个向量，这个向量就表征着一个量子比特，也就是说球面上的每一个点都对应着一个量子比特。将这个向量与z轴的夹角θ，其在x-y平面内投影与x轴的夹角ϕ代入1.3.1就可以得到量子比特的解析表示。1.4多量子比特多量子比特是对单量子比特的推广，单量子比特所表征的态是由两个基底线性叠加而成。类似的，双量子比特所表示的态由四个基底线性叠加而成，这四个基态分别记为：|00，|01，|10和|11。双量子比特的态表示为：|Ψ=α00|00+α01|01+α10|10+α11|11满足归一化条件：|α00|2+|α01|2+|α10|2+|α11|2=1。同样，对系统进行探测的时候就会发生坍缩，探测第一个量子态为|0的概率为|α00|2+|α01|2，这个时候系统就坍缩在了|00态或者是|01态上，对第二个量子态进一步探测的时候，系统就会进一步坍缩，或为|00态，或为|01态。下面介绍一个特殊的双量子态：|00+|11√2这个量子态看起来很不起眼，但是确是量子隐形传态和超密编码的关键因素，还是其他很多有趣量子状态的原型。这个状态的特殊之处在于，测得第一个结果之后第二个结果就知道了：测第一个量子比特的时候有1/2的概率得到|0，进入的是|00态，也就是说再测第二个量子比特的时候得到的也是|0态；同样有1/2的概率测第一个量子比特得到|1，测第二个量子比特的时候结果和第一个一样。更一般的，n量子比特系统的基态由2n个|x1x2x3.....xn形式的基矢组成。n=500的时候，2n就超过了整个宇宙原子的估计总数，这用传统的经典计算机是不可能实现的，远远超出我们的相像。2.量子逻辑门量子状态的变化可以用量子计算的语言来表示，类似于经典计算机是由包含连线和逻辑门的线路建造起来的，量子计算机由包含量子门和连线的量子线路营造而成。连线实现量子信息的传导，量子逻辑门实现的是信息的转换与处理。2.1单量子比特门2.1.1单量子比特门的表示量子比特可以用向量来描述：Ψ=(αβ)那么，量子比特门就可以用一个2*2的矩阵来表示，记为G=[abcd]，量子门作用在量子比特上就相当于是一个2*2的矩阵作用在一个2*1的向量上，在计算时就是二者相乘。2.1.2几个具体的单量子比特门（1）量子非门（NOTgate/Xgate）要实现的功能是把|0态和|1态互换。也就是说，|0态经过量子非门之后变成|1态，|1态经过量子非门之后变成|0态。那么当系统处在线性叠加态时会发生什么样的变化呢？其实，量子非门是一个线性矩阵，只要把叠加态中的|0与|1互换就好了，即Ψ=α|0+β|1经过量子非门之后变成Ψ’=α|1+β|0。基于量子非门的线性，我们可以将其用一个矩阵表示为：X≡[0110]符号表示为，作用在单量子比特上的效果是：X(αβ)=(βα)（2）Hadmard门把|0态和|1态变成|0与|1的中间态，具体如下：H|0=|0+|1√2H|1=|0−|1√2Hadmard门的矩阵表示为：H≡1√2[111−1]，符号表示为，很容易证明H2=I，也就是说对一个状态进行两次Hadmard门操作就相当于什么都没干。（3）Z门保持|0不变，而使|1发生反转，即：Z|0=|0Z|1=−|1Z门的矩阵表示为：Z≡[100−1]，符号表示为，同样Z2=I。对于一些简单的量子门，我们可以根据其所要实现的功能利用待定系数法求出其矩阵表示。2.1.3量子比特门所要满足的条件根据量子比特的归一化条件很容易证明量子门需要满足酉性条件，也就是说量子比特门对应的矩阵G是一个酉矩阵，即：G∙G∗=I。而且，这是对量子门的唯一限制，只要是量子门就一定是酉矩阵，每一个酉XHZ矩阵都对应着一个量子门。所以，有无数多个量子门。其实，任意一个单量子比特门都可以分解成一个旋转[cosγ2−sinγ2sinγ2cosγ2]和一个可以理解为绕Z轴的旋转[e−iβ200eiβ2]以及全局相移eiα的乘积。2.2多量子比特门多量子比特门是单量子比特门的推广，五个经典比特门是：与（AND）、或（OR）、异或（XOR）、与非（NAND）和或非（NOR）。多量子比特门的原型是受控非门（Control-NOT或CNOT），下面简单介绍一下。受控非门是一个双量子比特门，具有两个输入和两个输出比特，两个输入中一个是控制比特一个是目标比特，当控制比特为|0的时候目标比特保持不变，当控制比特为|1的时候目标比特发生翻转，由|0态变为|1态或者是|1态变为|0态，即|00→|00，|01→|01，|10→|11，|11→|10。由上式的结果可以看出，第一个量子比特总是不变，而第二个量子比特是对经过量子门之前的两个比特进行异或运算的结果，两比特相同时，目标比特为0；两比特不同时目标比特为1，即|ab|aa⊕b形象地，受控非门的几何表示为|a|a|b|a⊕b图2.1受控非门的几何表示对于多量子比特门，有一个通用性结果：任意的多量子比特门都可以由受控非门和单量子比特门复合而成，即受控非门和单量子比特门是其他所有多量子比特门的原型。3.量子线路CNOT量子线路就是实现量子计算的语言，由连线与量子逻辑门构成。下面用一个简单的例子——受控非门（swapoperation）来说明。图3.1对换操作的量子线路从图3.1可以看出，对换操作由三个量子受控非门依次连接构成，信息从左往右传播，初始信息被第一个受控非门处理之后的输出信息作为第二个受控非门的输入信息，第二个的输出信息又作为第三的门的输入信息，最后得到的是最终的输出信息。也就是说，量子线路的读取是由左到右进行的。下面我们看看以|a,b作为输入信息的时候最终的输出信息是什么。第一个受控非门:输入信息是|a,b,过程是|a,b|a,a⊕b;第二个受控非门:输入信息是|a⊕b,a,过程是|a⊕b,a|a⊕b,b;第三个受控非门:输入信息是|b,a⊕b,过程是|b,a⊕b|b,a.于是，输入端为|a,b时，输出为|b,a，实现的是两个量子比特的对调。需要注意的是，有一些经典线路中的概念在量子线路中是不出现的，比如量子线路中不允许出现出现环路，即没有反馈，也没有扇入与扇出操作。由此可以看出，量子线路实现的就是量子信息的传输与操作，量子信息沿着线路传输，遇到量子门的时候进行相应的变换，当然最后会有一个测量操作，将量子信息转换为经典信息，为人们所观测。测量操作的符号表示为：图3.2测量操作的符号表示左边的单线表示信息为量子信息，右边变成了双线，表示的是经典信息，仪表的作用是将量子信息转换成我们能识别的经典信息。CNOTCNOTCNOT4.量子计算使用量子线路可以实现量子计算，量子算法可以模拟经典计算，同时量子并行性使得量子算法具有较于经典算法的绝对优势，可以进行大量而快速的计算。这一节内容将简要介绍一下量子并行性并举几个量子算法的例子加强理解。4.1量子线路对经典线路的模拟要实现量子线路对经典线路的模拟就需要用到一个叫做Toffoli门的可逆门，Toffoli门可以模拟与非门还可以实现扇出，有了这两个操作就可以模拟经典线路中的任意元件。下面简要介绍一下Toffoli门。4.1.1Toffoli门Toffoli门有三个输入比特和三个输出比特，其中两个是控制比特，不收Toffoli门的影响，一个是目标比特，当两个控制比特都置1的时候目标比特发生翻转，否则不变。列写出其真值表如下：输入a00010111b00101011c01001101输出a’00010111b’00101011c’01001110表4.1Toffoli门的真值表其线路表示为：aa’=abb’=bcc’=c⊕ab图4.1Toffoli门的线路表示4.1.2Toffoli门模拟经典与非门具体的线路：aabb11⊕ab图4.2Toffoli门模拟与非门见上图，上面两个控制门是与非门的输入，目标量子门的输入置为1，目标量子门的输出端为与非门的输出，得到的就是控制门的两个比特与非的结果。4.1.3Toffoli门实现扇出线路图为：11aa0a图4.3Toffoli门实现扇出扇入的输入端为图中第二个量子门，输出端为第二个量子门和第三个量子门。当然，把第二个量子门和第一个量子门的情况互换一下也是完全一样的，因为这两个量子比特的地位是完全一致的。量子计算机借用Toffoli门实现经典计算机的模拟，但是对经典计算机的模拟并不是量子计算机的唯一用途，如果这样，量子计算机就没有存在的价值了。它还可以对超大数据进行快速运算，其计算能力远远超过经典计算机，接下来我们看看原因是什么。4.2量子并行性量子并行性使量子计算机可以同时计算函数f(x)在多个不同自变量x值处的函数值。设f(x)：{0,1}→{0,1}是一个定义域与值域都是单量子比特的函数，而量子计算机是双量子比特的，第一个比特存放的寄存器称为数据寄存器，而第二个称为目标寄存器。在运算前双量子比特的值是|x,y，通过一个量子门的运算后是|x,y⊕f(x)，把y置0，那么输出的就是|x,f(x)。由于量子门是线性的，如果x是一个叠加态，那么获得的函数值也是一个叠加态，如||0+|1√2,0→||0+|1√2，f(0)+f(