量子信息学引论第8讲

1清华大学2012.11.7IntroductiontoQuantumInformationScience第8讲量子信息学引论12第四章量子线路描述进行量子计算所需的基本元件和基本操作4.1量子算法4.2单量子位操作4.3受控操作4.4测量4.5普适量子门4.6量子计算线路模型总结4.7量子系统模拟23前节课总结单量子位操作，受控操作，测量3CNOTCUcctctcUtZCP100001000010000144.5普适量子门Universalquantumgates4.5.1两级(two-level)酉门是普适的4.5.2单量子位门与CNOT门是普适的4.5.3普适操作的一个离散集4.5.4近似任意的酉门一般是困难的4.5.5量子计算复杂性45普适门的集合•什么是普适门？•经典线路中可由一组有限个逻辑门来计算任意函数。称这一组逻辑门为普适的。例如：AND，OR，NOT•对于量子线路，如果任意的酉操作都可用一个集合中的门构成的线路来近似，且可达到任意精度，则称此集合中的门对于量子计算是普适的。例如：H，CNOT，S，T564.5.3普适运算的一个离散集合•上节证明了受控非门与单量子位酉操作一起构成了量子计算的普适集。•尚不知如何实现具有抗错(error-resistant)能力的这些门的简单方法。•幸运的是，本节将找出一个用来执行通用量子计算的门的离散集合。且这些门操作能在抗错的形式下执行。67对酉算子近似•为什么要近似？•酉算子的集合是连续的。•门的离散集合不可能精确实现任意的酉运算。zyziRRReU78对酉算子的近似设U和V是在同一状态空间上的两个酉算子，U是希望实现的酉算子，V是实际实现了的酉算子。定义实现过程的误差为其中最大运算取遍状态空间中所有量子状态|。)(max),(VUVUE89对酉算子的近似2),(2VUEPPvU前面的定义有一个合理的解释：如果E(U,V)，那么对于在POVM中的任意一个测量M，对U|测量后输出的概率为PU，测量V|后得到的概率为PV，那么它们的相差不会超过2，也就是对任意POVM算子M，我们有：910证明††||||22(,)UVPPUMMVUMMVEUVUV设那么由于††||||UVPPUMUVMV11酉算子的近似更进一步说，如果用一系列的门V1,…Vm来近似U1,…Um,则误差是线性相加的：为了使近似线路得到的结果在正确概率的一个允许量0以内，则只需要保证：mjjjmmmmVUEVVVUUUE11111,),(mVUEjj2/,1112门的普适性1、Hadamard,CNOT,phase,p/82、Hadamard,CNOT,phase,Toffoli这些门都可提供容错设计。但是后者并不太吸引人第十章会证明。13H+Phase+CNOT+T门的普适性{Hadamard,CNOT,phase,p/8}下面我们来证明下面的集合是普适的：我们可以证明除了一个全局相位，下面的的等式是成立的：13exp/80exp/8expexpexp0exp/88884ziTiiiZiRipppppppexpexpexp4844xHTHiiXiRpppp14把前面的等式结合则可得到：用H和T门构造nR~14nR~即仅利用T门和H门就可以构造出，可以证明是2p的无理倍数。其中由cos(/2)cos2(p/8)给出。2n888888expexpcoscossinsin=RiZiXIiXZYpppppp绕着给定轴转角，这里28888cos,sin,cos/1cosnpppp15重复迭代则可用以任意精度近似任意的旋转算子。证明：定义k，使得k[0,2p），且对于k=1,…,N(整数N2p/所需精度)，k=(k)mod2p。则根据鸽笼原理，存在不同的j和k(Nkj)使得|k–j|2p/N这也就意味着：0|k-j|2p/N用近似任意旋转nR~nR~nR~nR~1516因此，序列k-j，2(k-j)，3(k-j),…,可填满区间[0,2p这样对于任意0，可以找到n使得3)(),(~~nnnRRE用近似任意旋转nR~nR~1617简单的代数运算可以证明：其中是个如下的单位矢量：我们同样可得：)()(~~mnRHHR3)(),(~~nmmRRE82cos1/)8/cos(),8/sin(),8/cos(~ppppmm~用近似任意旋转nR~nR~1718根据练习4.11任意的酉算子可以分解成：则选择合适的n1,n2,n3，根据误差累计原则可以得到：这就是说任意的单量子位酉算子U，可以仅用Hadamard和p/8门组成的线路，近似到指定的误差以内。单量子位U可用Hadamard和p/8门精确近似nmnRRRU~~~321)()()(,~~~nnnnnnHRHRRUE1819•任意的单量子位酉算子U，可以仅用Hadamard和p/8门组成的线路，近似到任意精度。前面已证明了受控非门和单比特酉门是普适的。这样就证明我们可以用Hadamard,CNOT和p/8门近似含有m个门的量子线路。•也就是说Hadamard,CNOT和p/8组成了一个量子线路的普适集。Hadamard,CNOT和p/8组成了量子线路的普适集1920根据Solovay和Kitaev定理对任意单比特门近似到精度,需要O(logc(1/))个门,c大约等于2。近似含有m个门的线路(精度)，则需要O(mlogc(m/))个门。需要的近似线路随原线路成多重对数增长。对实际应用是可以接受的。近似的效率20214.5.4近似任意的酉门一般是困难的•在n个量子位上的任意酉变换都可用一个小的离散集内的门来构造．•是否总可有效地做到这些？即，给定对于n个量子位的一个酉变换Ｕ，是否存在n的多项式的线路来近似Ｕ？•答案：否。对大多数U门，近似的效率都很低。21224.5.5量子计算复杂性•经典复杂性分类:-复杂类P-求解所需时间:O(poly(|input|))-复杂类NP（nondeterministicpolynomialtime）-验证所需时间:O(poly(|input|))-复杂类NP-complete-任何别的NP问题都可约化到此问题。-复杂类NPI（NPIntermediate）-NP但不是NP-complete-复杂类PSPACE(polynomialspace)-求解所需空间:O(poly(|input|))-复杂类EXP-求解所需空间:O(2poly(|input|))2223复杂性类PSAPCE复杂性类PSPACE-可以用图灵机解决的判定问题。-需要的空间随问题的大小成多项式增长，可以使用任意长的时间。2324量子复杂性类BQP复杂性类BQP（boundederrorquantumpolynomialtime，是BPP的量子对应）•实质上是量子复杂性类•可以利用多项式规模量子线路计算的，并且误差在有界概率内可解的判定问题。2425复杂性类BPP复杂性类BPP(Bounded-errorprobabilistictime)-经典复杂性类-在经典图灵机上用多项式的时间，且误差在有界概率内可解的判定问题。-显然：BPPBQP2526量子计算复杂性类PBQPNPPSPACE2627量子复杂性类PSAPCE包含BQP可以证明BQPPSAPCE，也就是任何利用量子算法在多项式大小的量子线路可以有界误差确定的语言，L，都可以用经典机器用多项式空间确定。即LBPQLPSPACE2728量子复杂性类量子计算机也遵守Church-Turing论题：任何计算过程都可用图灵机来模拟。2829能量与计算计算机复杂性研究了求解一个计算问题所需的时间和空间量。另一类重要的计算资源是能量。303.2.5能量与计算•计算中的能量消耗与计算是否可逆是深刻相联系的。•说一个计算是可逆的,等价于说，在计算中没有信息被擦除。3031经典不可逆逻辑门如，与非门等是不可逆的，两个输入，一个输出，即给定输出，不可唯一地确定输入。32经典可逆逻辑门如，非门和Ｔoffoli门等是可逆的。a非a33Landauer原理•(第一种形式):设一个计算机擦除一位的信息,则耗散到环境中的能量至少为kBTln2，其中，kB为Boltzman常数,T为计算机的环境温度。•(第二种形式):设一个计算机擦除一位信息,则环境的熵至少增加kBln2。3334能量与计算的意义尽管现有计算机远没有达到Landauer原理给出的下限，弄清可以减少多少能量消耗仍然是有意义的。主要源于摩尔定律，如果计算机的能力不断增强，除非每个操作的能量消耗至少像计算能力提高一样迅速降低，否则消耗的总能量必然增加。35从研究可逆计算学到什么？•计算的可逆性来源于我们保留所有的信息。信息的擦除带来了不可逆。•可逆计算过程不耗费能量。•可以有效地进行可逆计算。也就是如果存在一个不可逆的线路计算某函数，则可以用一个可逆线路有效的模拟这个线路。•可逆计算导致了物理学中的一个老问题：麦克斯韦妖3536Maxwell妖热力学第二定律：封闭系统的熵永远不会减少1.Maxwell'sDemonAssistedThermodynamicCycleinSuperconductingQuantumCircuits,H.T.Quan,Y.D.Wang,Yu-xiLiu,C.P.Sun,andF.Nori,Phys.Rev.Lett.97,180402(2006)2.Quantumthermodynamiccyclesandquantumheatengines,H.T.Quan,Yu-xiLiu,C.P.Sun,andF.Nori,Phys.Rev.E76,031105(2007)3.ThePhysicsofMaxwelldemonandinformation,K.Maruyama,F.Nori,andV.Vedral，Rev.Mod.Phys.81,1(2009)1871年，J.C.Maxwell提出表面上违反这条定律的机器。他提出如图所示的小妖怪，把气缸中的快慢气体分为两半，当快分子从左边靠近小门，他就打开小门让分子通过。通过足够长的时间整个气缸的熵就会减少。374.6量子计算线路模型总结（１）经典资源量子计算包括经典部分和量子部分。（２）一个合适的状态空间2n维的复Hilbert空间,积形式|x1,x2,x3,…,xn的状态称为计算机的计算基态，其中xi=0,1,每一个基矢态简写为|x且x是二进制表示为x1…xn的数。37384.6量子计算线路模型总结（３）制备处于计算基矢态的能力任何计算基矢态|x1,…,xn,可在n步内制备。（４）执行量子门运算的能力可以对量子比特的任意子集施加逻辑门。存在普适量子门集。（５）在计算基矢上进行测量的能力。38394.7量子系统仿真•4.7.1仿真原理•4.7.2量子仿真算法•4.7.3一个说明例子•4.7.4量子仿真概览39404.7.1量子仿真•仿真的核心是解微分方程，这些微分方程用于刻画统治系统动力学行为的物理定律。•如:牛顿定律,Poisson定律，扩散方程，Schrödinger方程等。总的目标是：给定系统的初始态，在其它时间或位置的状态如何？它是什么状态？4041模拟量子系统模拟的核心是解微分方程，这些微分方程用于刻画统治系统动力学行为的物理定律。-以上步骤中的误差是有界的，且小于迭代次数的某个低次幂。-不是所有的系统都能被有效率地模拟。(x0,t0)(