量子信息学引论第8讲.ppt

《量子信息学引论第8讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1清华大学2012.11.7IntroductiontoQuantumInformationScience第8讲量子信息学引论12第四章量子线路描述进行量子计算所需的基本元件和基本操作4.1量子算法4.2单量子位操作4.3受控操作4.4测量4.5普适量子门4.6量子计算线路模型总结4.7量子系统模拟23前节课总结单量子位操作，受控操作，测量3CNOTCUZCP44.5普适量子门Universalquantumgates4.5.1两级(two-level)酉门是普适的4.5.2单量子位门与CNOT门是普适的4.5.3普适操作的一个离散集4.5.4近似任意的酉门一般是困难的

2、4.5.5量子计算复杂性45普适门的集合什么是普适门？经典线路中可由一组有限个逻辑门来计算任意函数。称这一组逻辑门为普适的。例如：AND，OR，NOT对于量子线路，如果任意的酉操作都可用一个集合中的门构成的线路来近似，且可达到任意精度，则称此集合中的门对于量子计算是普适的。例如：H，CNOT，S，T564.5.3普适运算的一个离散集合上节证明了受控非门与单量子位酉操作一起构成了量子计算的普适集。尚不知如何实现具有抗错(error-resistant)能力的这些门的简单方法。幸运的是，本节将找出一个用来执行通用量子计算的门的离散集合。且这些门操作能在抗错的形式下执行。67对

3、酉算子近似为什么要近似？酉算子的集合是连续的。门的离散集合不可能精确实现任意的酉运算。78对酉算子的近似设U和V是在同一状态空间上的两个酉算子，U是希望实现的酉算子，V是实际实现了的酉算子。定义实现过程的误差为其中最大运算取遍状态空间中所有量子状态

4、>。89对酉算子的近似前面的定义有一个合理的解释：如果E(U,V)

5、y>测量后输出的概率为PU，测量V

6、y>后得到的概率为PV，那么它们的相差不会超过2e，也就是对任意POVM算子M，我们有：910证明设那么由于11酉算子的近似更进一步说，如果用一系列的门V1,…Vm来近似U1

7、,…Um,则误差是线性相加的：为了使近似线路得到的结果在正确概率的一个允许量>0以内，则只需要保证：1112门的普适性1、Hadamard,CNOT,phase,p/82、Hadamard,CNOT,phase,Toffoli这些门都可提供容错设计。但是后者并不太吸引人第十章会证明。13H+Phase+CNOT+T门的普适性{Hadamard,CNOT,phase,p/8}下面我们来证明下面的集合是普适的：我们可以证明除了一个全局相位，下面的的等式是成立的：1314把前面的等式结合则可得到：用H和T门构造14即仅利用T门和H门就可以构造出，可以证明q是2p的无理倍数。其

8、中q由cos(q/2)cos2(p/8)给出。绕着给定轴转q角，这里15重复迭代则可用以任意精度近似任意的旋转算子。证明：定义qk，使得qk[0,2p），且对于k=1,…,N(整数N>2p/d所需精度)，qk=(kq)mod2p。则根据鸽笼原理，存在不同的j和k(Nk>j)使得

9、qk–qj

10、<2p/N这也就意味着：0<

11、qk-j

12、<2p/N用近似任意旋转1516因此，序列qk-j，q2(k-j)，q3(k-j),…,可填满区间[0,2p)这样对于任意e>0，可以找到n使得用近似任意旋转1617简单的代数运算可以证明：其中是个如下的单位矢量：我们同样可得：用近似任意旋

13、转1718根据练习4.11任意的酉算子可以分解成：则选择合适的n1,n2,n3，根据误差累计原则可以得到：这就是说任意的单量子位酉算子U，可以仅用Hadamard和p/8门组成的线路，近似到指定的误差e以内。单量子位U可用Hadamard和p/8门精确近似1819任意的单量子位酉算子U，可以仅用Hadamard和p/8门组成的线路，近似到任意精度。前面已证明了受控非门和单比特酉门是普适的。这样就证明我们可以用Hadamard,CNOT和p/8门近似含有m个门的量子线路。也就是说Hadamard,CNOT和p/8组成了一个量子线路的普适集。Hadamard,CNOT和p/8

14、组成了量子线路的普适集1920根据Solovay和Kitaev定理对任意单比特门近似到精度e,需要O(logc(1/e))个门,c大约等于2。近似含有m个门的线路(精度e)，则需要O(mlogc(m/e))个门。需要的近似线路随原线路成多重对数增长。对实际应用是可以接受的。近似的效率20214.5.4近似任意的酉门一般是困难的在n个量子位上的任意酉变换都可用一个小的离散集内的门来构造．是否总可有效地做到这些？即，给定对于n个量子位的一个酉变换Ｕ，是否存在n的多项式的线路来近似Ｕ？答案：否。对大多数U门，近似的效率都很低。21