量子信息学引论第8讲

1、1,清华大学 2012.11.7,Introduction to Quantum Information Science,第8讲,量子信息学引论,1,2,第四章 量子线路,描述进行量子计算所需的基本元件和基本操作 4.1 量子算法 4.2 单量子位操作 4.3 受控操作 4.4 测量 4.5 普适量子门 4.6 量子计算线路模型总结 4.7 量子系统模拟,2,3,前节课总结,单量子位操作，受控操作，测量,3,CNOT,CU,Z,CP,4,4.5 普适量子门Universal quantum gates,4.5.1 两级(two-level)酉门是普适的 4.5.2 单量子位门与CNOT门是普适

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

3、将找出一个用来执行通用量子计算的门的离散集合。且这些门操作能在抗错的形式下执行。,6,7,对酉算子近似,为什么要近似？ 酉算子的集合是连续的。 门的离散集合不可能精确实现任意的酉运算。,7,8,对酉算子的近似,设U和V是在同一状态空间上的两个酉算子，U是希望实现的酉算子，V是实际实现了的酉算子。定义实现过程的误差为 其中最大运算取遍状态空间中所有量子状态| 。,8,9,对酉算子的近似,前面的定义有一个合理的解释： 如果E(U,V ) 测量后输出的概率为PU，测量V|y后得到的概率为PV，那么它们的相差不会超过2e，也就是对任意POVM算子M，我们有：,9,10,证明,设,那么,由于,11,酉算

4、子的近似,更进一步说，如果用一系列的门V1,Vm来近似U1,Um,则误差是线性相加的： 为了使近似线路得到的结果在正确概率的一个允许量0以内，则只需要保证：,11,12,门的普适性,1、Hadamard, CNOT, phase, p/8 2、Hadamard, CNOT, phase, Toffoli,这些门都可提供容错设计。但是后者并不太吸引人 第十章会证明。,13,H + Phase + CNOT + T 门的普适性, Hadamard, CNOT, phase, p/8 ,下面我们来证明下面的集合是普适的：,我们可以证明除了一个全局相位，下面的的等式是成立的：,13,14,把前面的等式

5、结合则可得到：,用H和T门构造,14,即仅利用T门和H 门就可以构造出 ， 可以证明q是2p的无理倍数。,其中q由cos(q/2) cos2(p /8)给出。,绕着给定轴转q角，这里,15,重复迭代则可用 以任意精度近似任意的旋转算子 。 证明： 定义qk，使得qk0, 2p），且对于k=1, N (整数 N 2p/d所需精度)，qk=(kq)mod2p。则根据鸽笼原理，存在不同的j 和k (Nkj)使得 |qk qj|2p/N 这也就意味着：0|qk-j| 2p/N,用 近似任意旋转,15,16,因此，序列 qk-j，q2(k-j) ，q3(k-j) , 可填满区间0, 2p) 这样对于任意

6、e 0，可以找到n使得,用 近似任意旋转,16,17,简单的代数运算可以证明： 其中 是个如下的单位矢量： 我们同样可得：,用 近似任意旋转,17,18,根据练习4.11任意的酉算子可以分解成： 则选择合适的n1,n2,n3，根据误差累计原则可以得到： 这就是说任意的单量子位酉算子U，可以仅用 Hadamard 和p/8门组成的线路，近似到指定的误差e以内。,单量子位U可用 Hadamard 和p/8门精确近似,18,19,任意的单量子位酉算子U，可以仅用 Hadamard 和p/8门组成的线路，近似到任意精度。前面已证明了受控非门和单比特酉门是普适的。这样就证明我们可以用 Hadamard,

7、 CNOT和p/8 门近似含有m个门的量子线路。 也就是说Hadamard, CNOT和p/8 组成了一个量子线路的普适集。,Hadamard, CNOT和p/8 组成了量子线路的普适集,19,20,根据Solovay和Kitaev定理对任意单比特门近似到精度e, 需要 O(logc(1/e) 个门, c大约等于2。 近似含有m个门的线路(精度e)，则需要 O (mlogc(m/e) 个门。 需要的近似线路随原线路成多重对数增长。对实际应用是可以接受的。,近似的效率,20,21,4.5.4 近似任意的酉门一般是困难的,在n个量子位上的任意酉变换都可用一个小的离散集内的门来构造 是否总可有效地做

8、到这些？即，给定对于n个量子位的一个酉变换，是否存在n的多项式的线路来近似？ 答案：否。对大多数U门，近似的效率都很低。,21,22,4.5.5 量子计算复杂性,经典复杂性分类: - 复杂类P - 求解所需时间: O(poly(|input|) -复杂类NP（nondeterministic polynomial time） -验证所需时间: O(poly(|input|) -复杂类NP-complete -任何别的NP问题都可约化到此问题。 -复杂类NPI （NP Intermediate）- NP 但不是NP-complete -复杂类PSPACE(polynomial space) -

9、求解所需空间: O(poly(|input|) - 复杂类EXP -求解所需空间: O(2poly(|input|),22,23,复杂性类 PSAPCE,复杂性类 PSPACE - 可以用图灵机解决的判定问题。 - 需要的空间随问题的大小成多项式增长，可以使用任意长的时间。,23,24,量子复杂性类BQP,复杂性类BQP（bounded error quantum polynomial time，是BPP的量子对应） 实质上是量子复杂性类 可以利用多项式规模量子线路计算的，并且误差在有界概率内可解的判定问题。,24,25,复杂性类BPP,复杂性类 BPP(Bounded-error proba

10、bilistic time) - 经典复杂性类 - 在经典图灵机上用多项式的时间，且误差在有界概率内可解的判定问题。 - 显然： BPPBQP,25,26,量子计算复杂性类,P,BQP,NP,PSPACE,26,27,量子复杂性类PSAPCE 包含BQP,可以证明BQPPSAPCE，也就是任何利用量子算法在多项式大小的量子线路可以有界误差确定的语言，L，都可以用经典机器用多项式空间确定。即 LBPQ LPSPACE,27,28,量子复杂性类,量子计算机也遵守Church-Turing论题： 任何计算过程都可用图灵机来模拟。,28,29,能量与计算,计算机复杂性研究了求解一个计算问题所需的时间和

11、空间量。另一类重要的计算资源是能量。,30,3.2.5 能量与计算,计算中的能量消耗与计算是否可逆是深刻相联系的。 说一个计算是可逆的, 等价于说，在计算中没有信息被擦除。,30,31,经典不可逆逻辑门,如，与非门等是不可逆的，两个输入，一个输出， 即给定输出，不可唯一地确定输入。,32,经典可逆逻辑门,如，非门和offoli 门等是可逆的。,33,Landauer 原理,(第一种形式): 设一个计算机擦除一位的信息, 则耗散到环境中的能量至少为kBTln2，其中，kB为Boltzman常数, T为计算机的环境温度。 (第二种形式): 设一个计算机擦除一位信息, 则环境的熵至少增加kBln2。

12、,33,34,能量与计算的意义,尽管现有计算机远没有达到Landauer 原理给出的下限，弄清可以减少多少能量消耗仍然是有意义的。 主要源于摩尔定律，如果计算机的能力不断增强，除非每个操作的能量消耗至少像计算能力提高一样迅速降低，否则消耗的总能量必然增加。,35,从研究可逆计算学到什么？,计算的可逆性来源于我们保留所有的信息。信息的擦除带来了不可逆。 可逆计算过程不耗费能量。 可以有效地进行可逆计算。也就是如果存在一个不可逆的线路计算某函数，则可以用一个可逆线路有效的模拟这个线路。 可逆计算导致了物理学中的一个老问题：麦克斯韦妖,35,36,Maxwell 妖,热力学第二定律： 封闭系统的熵永

13、远不会减少,Maxwells Demon Assisted Thermodynamic Cycle in Superconducting Quantum Circuits, H. T. Quan, Y. D. Wang, Yu-xi Liu, C. P. Sun, and F. Nori, Phys. Rev. Lett. 97, 180402 (2006) 2. Quantum thermodynamic cycles and quantum heat engines, H. T. Quan, Yu-xi Liu, C. P. Sun, and F. Nori, Phys. Rev. E 7

14、6, 031105 (2007) 3. The Physics of Maxwell demon and information, K. Maruyama, F. Nori, and V. Vedral， Rev. Mod. Phys. 81, 1 (2009),1871年， J. C. Maxwell 提出表面上违反这条定律的机器。 他提出如图所示的小妖怪，把气缸中的快慢气体分为两半，当快分子从左边靠近小门，他就打开小门让分子通过。通过足够长的时间整个气缸的熵就会减少。,37,4.6 量子计算线路模型总结,（）经典资源 量子计算包括经典部分和量子部分。 （）一个合适的状态空间 2n维的复Hi

15、lbert空间, 积形式|x1,x2,x3,xn的状态称为计算机的计算基态，其中xi=0,1,每一个基矢态简写为|x且x 是二进制表示为x1xn的数。,37,38,4.6 量子计算线路模型总结,（）制备处于计算基矢态的能力 任何计算基矢态|x1,xn ,可在n步内制备。 （）执行量子门运算的能力 可以对量子比特的任意子集施加逻辑门。存在普适量子门集。 （）在计算基矢上进行测量的能力。,38,39,4.7 量子系统仿真,4.7.1 仿真原理 4.7.2 量子仿真算法 4.7.3 一个说明例子 4.7.4 量子仿真概览,39,40,4.7.1 量子仿真,仿真的核心是解微分方程，这些微分方程用于刻画

16、统治系统动力学行为的物理定律。 如: 牛顿定律, Poisson定律，扩散方程， Schrdinger方程等。 总的目标是：给定系统的初始态，在其它时间或位置的状态如何？它是什么状态？,40,41,模拟量子系统,模拟的核心是解微分方程，这些微分方程用于刻画统治系统动力学行为的物理定律。 以上步骤中的误差是有界的，且小于迭代次数的某个低次幂。 不是所有的系统都能被有效率地模拟。,41,42,模拟量子系统的挑战,用经典计算机可以模拟量子系统，但一般效率很低 模拟量子系统的关键挑战是：需解的微分方程的数目为指数个。 对按薛定谔方程演化的N量子位，需要解2N个方程。,42,43,量子计算机可以模拟量子

17、系统，它们没有有效的经典仿真。 也可能有不能在量子计算机可以模拟的量子系统。,注意,44,4.7.2量子仿真算法,time-independent Hamiltonian 系统的初始状态为 |y(0) 对时不变的哈密顿量 H, 作用在系统上的时间为t 。 系统演化成 |y(t) = e-iHt |y(0) H的指数一般极难求。 一阶近似 |y(t + Dt) ( I - iH Dt)|y(t) 但这样的一阶解一般不能满足要求。,44,45,有些Hamilton量是可以求解的 例子： 一个在均匀磁场中沿z轴的自旋为1/2的粒子的哈密顿量为： 其中c = (eB/mC) 则经过时间t后：,系统Ha

18、milton量,45,46,系统Hamilton量,在均匀磁场中沿z轴两个无相互作用的自旋为1/2的粒子的哈密顿量为：,46,47,Hamilton量可以分解,虽然Hamilton量的指数很难求，但对许多Hamilton量求高阶近似解是可能的。 例如对大多数物理系统，Hamilton量可以写成许多局部相互作用的和的形式；如对一个n粒子系统： 其中Hk最多作用在常数c数目的子系统上，L是n的一个多项式。,47,48,量子仿真,我们可以选择子系统使得每一个e-iHkt 都很容易仿真。 但通常 Hk,Hj 0，所以 - 那么如何从e-iHkt构造e-iHt？,48,49,我们可以对e-iHt近似（通

19、过无限逼近的办法）。 定理4.3（Trotter公式）: 令A和B是Hermite算子，则对任意实数t，有,量子仿真算法的核心-渐进近似定理：Trotter 公式,49,50,三个记号,O 为函数行为设定的上界：定义设非负整数函数f(n)和g(n)，如果存在常数c和n0使得所有大于n0的n有如下关系 c g(n) f(n)，那么就说f(n)属于类O（g(n)），即除去一个不重要的常数因子g(n)是f(n)的一个上界。 指除去不重要的常数因子 W下界：函数f(n)称为是W（g(n)），如果存在常数c和n0使得所有大于n0的n有如下关系 f(n) c g(n) ，即除去一个不重要的常数因子g(n)

20、是f(n)的一个下界。,51,证明,由于,所以,并且用二项式展开,52,证明,因此,由于,53,近似Hamilton量的两个有用公式,例子：,53,这里Dt是一个很小的量。,54,算法: 量子模拟,输入： 1）作用在N维系统上的Hamilton量， 其中每个Hk作用在尺寸和N无关的子系统上。 2）在t=0的系统初始态为|y0。 3）正的非零精度d。 4）需要求的演变后状态的时刻tf。 输出：状态 ，使得 运行时间：O(poly(1/d)数目的操作。,54,55,量子模拟过程,过程： 选择一个表示，使得n=poly(logN)量子比特的状态，能近似系统状态，且算子e-iHkDt具有有效的量子近似线路。选择一个近似方法和Dt,使得期望误差在可接受范围内（并且对某个整数j,jDt=tf),为迭代构造一个相应的量子线路