量子信息学引论第9讲

1清华大学2012.11.14量子信息学引论IntroductiontoQuantumInformationScience第九讲12第四章量子线路复习4.1量子算法4.2单量子位操作4.3受控操作4.4测量4.5普适量子门4.6量子计算线路模型总结4.7量子系统模拟23第四章量子逻辑门复习单量子位操作，受控操作，测量3CNOTCUcctctcUtZCP10000100001000014小测验1、写出Hadamard门的矩阵形式，写出它对输入态|1和|0作用后的输出。2、写出Hadamard门的外积表示形式。5第五章量子算法•量子并行性•Deutsch算法•Deutsch-Jozsa算法•两个主要的量子算法：•Shor的大数因子化运算速度得到指数级的增长•Grove的量子搜索算法运算速度得到平方的增长•量子算法总结56量子算法(1)用量子线路能进行哪些类型的计算?(2)此类计算与经典逻辑线路的算法相比如何?(3)能否发现一个任务，量子计算机完成得比经典计算机出色？本节研究这些问题，解释如何在量子计算机上进行经典计算，给出量子计算机优于经典计算机的几个例子，总结已知的量子算法。67量子计算机上的经典计算•能否用量子线路来模拟一个经典逻辑线路？能！•但是，量子线路不能直接用来模拟经典线路。•因为：酉(unitary)量子逻辑门本质上是可逆的（reversible)，而许多经典逻辑门（如与非门=NAND）是不可逆的(irreversible)。78Toffoli门•利用已知可逆的Toffoli门，所有的经典线路都可用只含可逆元件的等效线路来代替。•关键：用Toffoli门来表示与非门（NAND门）。•因为：与非门是经典的普适门(universalgate)，只用它就可以构成所有经典计算线路。8Proposedin1980byTommasoToffoli9与非门(NAND)与逻辑真值表与逻辑函数表达式：Z＝A•B=AB与非的真值表ABABZ或与非逻辑函数表达式10Toffoli门的特点•Toffoli门有3个输入位，3个输出位（与CNOT门类似）。•2个位是控制位(controlbits)，不受Toffoli门作用的影响；第3位是目标位（targetbit)。•如果两个控制位都置为1，则目标位翻转，其它情况，目标位不变。1011Toffoli门的真值表与线路表示11Proposedin1980byTommasoToffoli12Toffoli门的逆是自身注意,施加两次Toffoli门到一组位上的效果:),,())(,,(),,(),,(cbaababcbaabcbacba因此,Toffoli门为可逆门,因为它有一个逆—自身.1213采用Toffoli门实现与非门•上面两位表示给与非门的输入，第3位制备成标准态1（也称为辅助态：ancillastate).•输出放在第3位13abou00101110111014采用Toffoli门的扇出（fanout)•第二位是到FANOUT的输入，其它两位为标准辅助位。•FANOUT的输出在第二位和第三位。1415与非门与FANOUT：够了•有了用Toffoli门表示的与非门与FANOUT，就可模拟经典线路中的所有其它元件。•因而，一个任意的经典线路都能用一个等效的可逆线路来模拟。1516量子不可克隆原理假设我们想拷贝系统A中的一个态|fA。为了拷贝态|fA，我们需要具有同样态空间的系统B，其初始态设为|eB,这样初始态为：|fA|eB我们想控制复合系统中的哈密顿量并且作一个幺正演化U。U充当一个克隆机。17量子不可克隆原理那么对任意|fA和|jA,我们有ABABABABUeUefffjjj由幺正算符的性质，我们有：2†BAABBAABeUUejfjjffjf18量子不可克隆原理†BAABAeUUejfjf10ABjfjf由于因此只有正交或态本身可以克隆，并不是所有的态都可以。参考:W.K.WottersandW.H.Zurek,Nature299,802(1982)19量子并行性•量子并行性是许多量子算法的一个根本特征。•直观上，量子并行性允许量子计算机同时对不同的x求函数f(x)值。•一个量子线路同时计算所有f(x)值。–经典并行计算用多个线路同时计算不同x的f(x)1920同时计算f(0)和f(1)0,01,020,(0)1,(1)2fUff设}1,0{}1,0{:)(xf为一个定义域和值域都为单个位的数．20,,()fUxyxyfx数据寄存器目标寄存器If0then?()yfx21Hadamard变换•输入为|0|02111001002102102122多量子位Hadamard变换xnnnxH210•所有量子位的初始态都为|0即初态为|000……0•求和是对所有可能的x值(全部计算基矢态）|00…….0,|00…….1,…,|11…….12223{|00…….0,…,|11…….1}={|a1,a2,…,an}二进制分解表示数x的二进制分解1m12anmmx24量子并行性)(21xfxxn对具有n个量子位的输入，f(x）具有n位输入，1位输出，Uf变换结果仅有量子并行性并不能提高运算速度。每次测量只能得到一个结果！而且所的结果的机率是一样的。2425Deutsch算法•Deutsch算法将量子并行性与量子力学的干涉性质结合起来。证明了量子计算比经典计算更强大。2526实现Deutsch算法的量子线路26只需一次测量就可以得到f(x)的整体性质f(0)f(1)27Deutsch算法的推导：010输入态2728Deutsch算法的推导：2102101对初始态做Hadamard变换282929210)1(1,210)1(01021)1()(1)(21U210)1()0()(ffxffxxfxfxx施加Deutsch算法的推导：30Deutsch算法的推导：经过Uf变换3021021012102)1(1)1(0210)1(1210)1(021)1()0()1()0(2ffff31Deutsch算法的推导：)1()0(:,210210)1()0(:,2102102ffifffif312102)1(1)1(0)1()0(2ff32Deutsch算法的推导：)1()0(:,2101)1()0(:,21003ffifffif第一个量子比特经过最后的Hadamard门3233Deutsch算法的推导：210)1()0(3ff•只对第一位测量一次，即可得知f(x)的一个整体特性。•量子线路使我们能确定函数的一个整体特性，而只计算一次f(x).331)1()0()1()0(0)1()0()1()0(ffffffff，如果，如果因为)1()0(:,2101)1()0(:,21003ffifffif34Deutsch-Jozsa算法•比Deutsh算法更精彩•游戏规则：Alice,0~2n–1间选数x.送给Bob,计算f(x)–Bob只能选择两种函数之一：constantorbalanced–Constant-对所有的x,f(x)值相同（或为0或为1）–Balanced-对一半的x,f(x)值为零，另一半为1•Bob把计算的数据发给Alice•Alice猜Bob所选择的f(x)种类•Alice猜多少次才能成功？–经典算法：最少2次，最多需要(2n/2)+1次。–量子算法需要多少次？1次3435一次猜出的条件•Alice和Bob可以交换量子比特•Bob同意用酉变换Uf来计算f(x)条件：做法：•Alice用n量子比特的寄存器存储她的查询输入，用一个单量子比特寄存器给Bob存储答案•开始把查询和答案寄存器置于一个叠加态•Bob用量子并行计算f(x)，把结果放在答案寄存器中•Alice用Hadamard变换干涉查询寄存器的状态并做测量36实现Deutsch-Jozsa算法的量子线路“/n”表示一组有n个量子位36100n查询寄存器答案寄存器37多量子位Hadamard变换xnnnxH210•所有量子位的初始态都为|0即初态为|000……0•求和是对所有可能的x值(全部计算基矢态）|00…….0,|00…….1,…,|11…….13738D-J算法的推导:21021,01nxnx3839D-J算法的推导:3920122221222nnxxnxfxfxxxfxfxx()2(1)0122fxnxx0110101if0,122222211001if1,1222222fxfxfxfxfxfxfxfx因此我们有40(1)2xzzzHxD-J算法的推导:0102H0112H因为所以41D-J算法的推导:nzznzxzxnnnnnzzxxH2,...,)1(,...,,...,1111141nzzxnzxH2)1(简单记为：42D-J算法的推导:2102)1()(3zxnxfzxz4243D-J算法的推导:2102)1()(3zxnxfzxz43考察项0,0,,0z我们有0()()(1)0,0,,0(1)0,0,,022xfxfxnnxx44结果：如果Alice测的都为0，则f为常量；其它为平衡现在,Alice测量询问寄存器.注意0n态的振幅为xnxf2/)1()(.A:若f为常量,0n的振幅为+1或-1,取决于f(x)的值.因3为单位长度,其余态的振幅必为0,即对询问寄存器的所有量子位测量到的值都为0.B:若f(x)为balanced,则xnxf02/)1()(,即测量询问寄存器时,至少一个量子位不为零.4445总结45查询寄存器测量全部为零，则为常数不全为零，为平衡函数46Deutsch-Jozsa算法Inputs:(1)AblackboxUfwhichperformsthetransformation,)(xfyxyxfor12,...,0nxand1,0)(xf.Itispromisedthat)(xfiseitherconstantforallvaluesofx,orelse)(xfisbalanced,thatisequalto1forexactlyhalfofallthepossiblex,and0fortheotherhalf.Outputs:0ifandonlyiffisconstant.Runtime:OneevaluationofUf.Alwayssucceeds.4647Deutsch-Jozsa算法(续)1.10ninitializestate2.21021120nxnxcreatesuperpositionusingHadamardgates3.xxfnx210)1(21)(calculatefunctionfusingUf4.()(1)0122xzfxnxxz