量子信息学引论第10讲

清华大学2012.11.21IntroductiontoQuantumInformationScience第10讲量子信息学引论量子算法•量子计算机的好处是什么?有些问题用经典计算机是无法解决的。主要有两个量子算法：1.Shor的大数因子化运算速度得到指数级的增长2.Grove的量子搜索算法运算速度得到平方的增长2图4.1主要量子算法及其联系和应用为什么好于经典的量子算法这么少?3第五章量子Fourier变换及其应用•本章讲解量子Fourier变换及其在因数分解与离散对数问题中的应用，并解释这些结果对于密码学的重要性。具体内容分为以下４节。•5.1量子Fourier变换•5.2相位估计•5.3应用:求阶与因数分解•5.4量子Fourier变换的一般应用45.1量子Fourier变换Fourier变换是科学研究中非常有用的一种数学工具。它的核心是把一个非常难解的问题，变换成另一个容易解决的问题，求解后然后再变换回原来的形式。原始问题非常难解求得新问题的解新的问题易解变换变换原始问题的解求解5Fourier变换6原始数据有高频噪声Fourier变换得到频谱滤波去掉噪声然后反变换得到干净数据离散Fourier变换•离散Fourier变换是一种作用在离散数据集上的Fourier变换。•把一个复向量，（x0,…xN-1），变换成另一个复向量，（y0,…,yN-1）：710/21NjNijkjkexNy向量的长度N是固定参数,这里i是虚数不是标号。量子Fourier变换式的一般表示量子Fourier变换和离散Fourier变换严格相同。但记号有所不同。量子Fourier变换就是一个线性算子，F，对正交归一基，，其作用为：10/21NkNijkkeNjF1,,0N8量子Fourier变换对任一个态矢量其中|j,j=0,N-1,为状态空间的正交归一基。那么对于此状态的量子Fourier变换就是：其中：10Njjjx10NkkkyF10/21NjNijkjkexNy9量子Fourier变换Fourier变换也可以写成：把一个态矢量，变换成另一个态矢量，而它的振幅yk就是xj的离散Fourier变换：kyFjxNkkNjj101010/21NjNijkjkexNy1010Njjjx10Nkkky两量子位Fourier变换•两个量子位的态矢量（N=4）：111110010011100100aaaa304/241jijkjkexy320/400010011101124ijjjyxeaaaa2/311012/1000304/212141iiijijjeaeaeaaexyiiijijjeaeaeaaexy3112011000304/4221412/9113012/31000304/632141iiijijjeaeaeaaexy矩阵形式•两个量子位的Fourier变换可以写成矩阵形式。•记w=e2i,那么w=i，w2=-1,故•可以验证上述变换为酉。12iiiiF1111111111112111111112196364232变换是酉变换•量子Fourier变换是酉变换可以从其定义式直接证明。•构造实现量子Fourier变换的线路，也能证明量子Fourier变换是酉变换。13量子Fourier变换量子Fourier变换是对量子力学振幅进行Fourier变换的有效算法。它不加速计算经典数据的Fourier变换，但它能用来做相位估算。相位估算是许多量子算法的基础。14计算基矢态的二进制表示•设n个量子位的量子计算机的计算基矢态为|j,则其二进制表示为:•也就是:|j=|j1j2…jnj=j12n-1+j22n-2+…jn2015二进制分数的表示同样，二进制分数jl/21+jl+1/22+…jm/2m-l+1也可以用类似的形式表示（lm）:0.jljl+1…jm16量子Fourier变换的乘积表示2/02020212)10()10)(10(,...,211njjjijjijinnnnneeejjF17利用态矢量的二进制形式和二进制分数，可以把量子Fourier变换表示为乘积形式:两个量子Fourier变换形式等价•可把|j=|j1j2…jn=|00…0代入验证.181202120202221210nnnknkkinkke///1202220202022121010102101010211nnnnnkkeeennnjjjijjiji///)())(()())((两个量子Fourier变换形式等价191112111121122221/2/200011221/2001122/210011......221......212nnnlnlnlnnlllnllnijkijknnnkkkijknnkknijklnlkkjekekkekkek112222nnlnlnnllllkkk19两个量子Fourier变换形式等价202210101010212110202022212/)())((/nnnnnljjjijjijiijnlneeeelnnnljjjj2222202211整数部分从指数项消失，因为对任意整数k,lkijknlnkelll10221221/2012ike量子Fourier变换的有效线路•此线路可从量子Fourier变换的乘积表示式中推出。•图中没示出线路末尾的交换门(swapgate)，用交换门把量子位的次序反过来。•图中也没示出输出中的归一化因子。212/1Rk门kikeR2/20012222/22/2101010000iiRSeieTeeRii4/2/230010013推导:量子Fourier变换线路考虑第一个量子位。经过H门后,状态为：施加控制-R2门后，因为0.j1j2=j1/2+j2/4，状态变为：23120.1221/21/2110010122ijnnjjjejjnjjijje2.022/1102121120.1221/21/2111010122ijnnjjjejj推导:量子Fourier变换线路对第一位接连施加控制R3,R4,…，Rn，每一次都使其系数增加了一个相移，最后得到：对第二位做类似操作，首先经过Hadamard门后，状态为：24njjjijjen2.022/1102121njijjjijjeen3.02.022/1101021221推导:量子Fourier变换线路对第二位接连施加控制R2,R3,…，Rn-1，对其余量子位做同样操作，最后系统状态为：再经过交换门把量子位的顺序交换，就得到所需要的量子Fourier变换。25njjijjjijjeenn3.02.022/11010212212/0202022)10)(10()10(121njijjijjjinnnneee三个量子位的Fourier变换:线路26kikeR2/20012RS3RT三个量子位Fourier变换的矩阵表示:利用下式推导7/43/2012Fijkkjek27111110101100011010001000,,,,,,,j=0,1,2,3,4,5,6,7三个量子位Fourier变换的矩阵表示:0011223344556677F三个量子位的Fourier变换:矩阵表示12345672462463614725444452741636426427654321111111111111111111181w29量子Fourier变换线路用了多少门?对第一个量子位用了一个H门和n-1控制Rk,共n个门。对第二个量子位用了一个H门和n-2控制Rk,共n-1个门.........第n个量子位用了一个H门，一共用了n+(n-1)+…+1=n(n+1)/2另外需要最多n/2个门做交换。可见,以上所讲的量子Fourier变换线路提供了有效算法需要n2个门，也就是Q(n2)。30量子与经典离散Fourier•量子:2n个元素的量子Fourier变换算法,需用门数Q(n2)•经典:2n个元素的离散Fourier变换算法,需用门数Q(n2n)量子与经典离散Fourier变换所需门数的对比31量子Fourier变换的意义•否!•问题在于:量子计算机中的振幅不能由测量直接得到，因此，不能确定原始状态的Fourier变换过的振幅。•更糟的是:一般无法有效制备将要进行Fourier变换的初始态。•因此，虽然量子Fourier变换速度比经典变换有指数倍的提高，找到量子Fourier变换的应用却不是一件容易的事。•量子Fourier变换能否用来加速经典Fourier变换的计算?325.2相位估计•量子Fourier变换是相位估计的关键。•相位估计则是许多量子算法的关键。phaseestimation33相位估计的目的•设一个酉算子U具有本征矢量|u,其对应的本征值为e2i,其中的值未知。•相位估计的目的:得到的值。34用于相位估计的黑箱为进行相位估计,假设我们拥有一个黑箱,有时也称为oracle,它具备以下功能:(1)能制备态|u.(2)能执行以下受控操作,其中j为适当的非负整数:Controlled-jU235采用黑箱意味什么?•采用黑箱意味着:相位估计步骤本身不是完整的量子算法.•可以认为相位估计是一种”子程序”,它与其它子程序结合起来,能执行有趣的计算任务.•在相位估计的具体应用中,将要描述黑箱如何操作.36相位估计需要两个寄存器(1)第一个为t位寄存器,其位数取决于所希望的精度及成功概率.(2)第二个寄存器用来存储|u.37相位估计的三个阶段(1)混合:采用H变换与受控-U变换。(2)反Fourier变换。(3)测量。38相位估计步骤的第一阶段注意:右边省略了归一化因子392/1假设酉算子U的本征值为，本征矢量为控制U操作ie2u112ieUuueueii112240uuUu1100U控制U操作uu41这样，相对相位是有观测结果的。10102ieU如果控制位为叠加态，则：ie2控制U操作uu42如果U作用指数次，则得到的倍数：112jiejU控制U操作uu4310102jiejU控制U操作uu4410u102ieU1010)2(21tie101010)2(2ieU2UU12t22t10)2(22tieu相位估计第一阶段45相位估计第一阶段2/2101010021222222tiiieeett46注意:右边省略了归一化因子2/1第一阶段：Fourier变换47如果可以用t位二进制数精确表示：0.11…t2/2/21010102101010211021.02.02.02222