量子计算入门.ppt

量子计算入门,Royea,量子计算,序言量子力学基础量子计算,序 言,量子计算出现于过去十年间，其中最引人注目的算法是Shor提出的大数因子分解算法，此算法可在量子计算机上以多项式时间实现1，它使NP问题变成P问题。算法的主要思想是将分解问题变为寻找函数的周期问题。它首先使用量子并行性通过一步计算获得所有函数值，然后通过测量函数值得到相关联的函数自变量的叠加态，并对其进行量子付立叶变换。量子付立叶变换和经典付立叶变换一样，实现函数时域到频域的转换，从而可以较高的概率测量到产生函数周期的状态，最后利用函数周期对大数进行质因子的分解。另一个算法是Grover量子搜索算法2。以前对大部分没有确定结构的问题，搜索求解的最好的办法是一个一个地去试，所以如果搜索空间的大小为N，那么这种方法的复杂度就是O(N)。Grover算法在量子计算机上对这类非结构化的问题使用了Walsh-Hadamard变换和相位旋转变换，其求解的时间复杂度是O()，即该算法将数据的搜索速度从N提高到，它是一种对非结构化解空间进行完全搜索的优化算法。,量子力学对已知世界的描述是精确和完整的，也是理解量子计算与量子信息的基础。光子偏振实验狄拉克表示法线性算子线性,量子力学基础,1-1光子的偏振,基本实验原理 光子是我们可以直接观测到的唯一的微观粒子。下面我们将通过解释光子及其偏振的简单实验说明量子力学的某些原理。试验所需的装置有：一个强光源，投影屏和偏振片。偏振片起“过滤”作用，即水平偏振片通过的是偏振方向是水平方向的光子，而滤掉了那些非水平偏振方向的光子；垂直偏振片滤掉了那些非垂直偏振方向的光子。如果把垂直偏振片插入到水平偏振片和投影屏之间，可见到垂直偏振片的出射光的光强为零。假设入射光的偏振方向是随机的。,1-1-1偏振实验,光子是我们可以直接观测到的唯一的微观粒子。下面我们将通过解释光子及其偏振的简单实验说明量子力学的某些原理。试验所需的装置有：一个强光源，如一台激光光源，三个偏振片A、B和C，其偏振方向分别是水平45和垂直。如图1所示，将一束光照射到投影屏上，假设入射光的偏振方向是随机的。首先在光源和投影屏之间插入水平偏振片，可以看到透过A后的出射光光强只有其入射光光强的一半，而且射出的光子现在都变成了水平偏振。图1 实验 1实验可见偏振片A过滤掉了那些非水平偏振方向的光子，通过的是偏振方向是水平方向的光子。由于偏振片A的入射光的偏振方向是随机的，所以入射光中偏振方向是水平方向的光子数目极少，如果偏振片A起过滤作用，则出射光的光强应该非常弱，实际上不会是入射光的光强的一半。,现将垂直偏振片C插入到偏振片A和投影屏之间，如图2所示，可见到垂直偏振片C的出射光的光强为零。“过滤”可以解释这一现象，因为没有偏振方向为水平方向的光子能够通过偏振方向为垂直的偏振片。图2 实验 2最后，我们在A和C间插入偏振方向为45的偏振片B，如图3所示，可看到投影屏上的一些微弱的光，它的光强正好是光源光强的1/8。图3 实验 3,2.1.2 实验解释,如果我们使用两个基向量|和|分别表示垂直偏振方向和水平偏振方向，那么任意一个随机的偏振方向都可以用这两个基向量的线性组合形式表示：a|+b|(1.1)其中，a和b表示复数，而且+=1。在量子力学中，两个基向量|和|被称作本征态。我们感兴趣的是光子的偏振方向，所以可以把一个光子的偏振状态表示为上述形式。实际上，任意两个相互正交的非零单位向量都可以作为状态空间的基。对量子状态的测量要求把该状态分别投影到其对应的正交基上，如图4所示。,对量子状态的测量要求把该状态分别投影到其对应的正交基上，如图4所示。图4 投影在基上的量子态的测量对该状态进行测量的时候，观测到状态|的概率为，而观测到状态|的概率为。由于测测量在相互正交的基上进行的，所以若不特别说明的话，所有的基均指的是正交的。另外，对量子态的测量还将使被测量的量子态改变为测量结果所表示的态。也就是说，如果我们对量子态|=a|+b|进行测量所得的结果是|，那么量子态|就变成了|，如果再用相同的基进行测量，测量结果一定还是态|。由此可见，除非被测量的量子态是被测力学量的一个本征态，否则任何测量都会改变量子态，而且不能由改变后的量子态推知原来的量子态。,现在我们用上述量子力学原理解释前面的偏振试验。插入偏振片可以看成是对光子的量子态进行一次测量。在测量的两个正交基中，一个与偏振片的偏振方向相同，而另一个与偏振片的偏振方向垂直。该测量将改变光子的偏振方向。只有那些测量后的偏振方向与偏振片的偏振方向一致的光子才能通过偏振片，而其它光子被偏振片反射回去了。例如，偏振片A用基|来测量光子的量子态，那么有的光子的量子态在测量后变成了|，有的光子的量子态在测量后变成了|，只有偏振方向为|的光子才能通过偏振片A，而所有偏振方向为|的光子则全被反射回去了。假设光源产生的光子的偏振方向是随机的，各种偏振方向的光子出现的概率相同，那么这些光子的量子态经过偏振片A后，光子状态被偏振片A、B和C改变的概率为50。所以，偏振方向变为水平方向的光子占所有光子的50，这些光子的量子态为|，它们通过偏振片A。而偏振片C用基|来对量子态为|的光子进行测量，光子状态改变的概率为0，其量子态仍然保持|。所以没有任何光子通过偏振片C，从而偏振片C的出射光强为0。,在A和C间插入偏振片B时，由于偏振片B的正交基可以表示为：(|+|),(|)（1.2）我们把它们写为：|,|。量子态为|的光子将通过偏振片B。因此，通过偏振片A后量子态为|的光子被偏振片B测量，光子状态改变的概率为50，其中有50的光子状态变成|，也就是说通过偏振片A的光子中有50可以通过偏振片B。同样，通过偏振片B的光子被偏振片C测量后，其中有50的光子状态变成|。所以，能够通过偏振片A、B和C，最终到达投影屏的光子数量是光源产生的光子数量的1/8。因此投影屏的光强是光源的1/8。从这个实验中我们可以看到，量子态可以是本征态，也可以是叠加态。若将通过偏振片看作测量，你就会发现，量子态经过测量会发生状态塌缩，由最初的状态塌缩到测量给出的状态上。,态的叠加 如果我们使用两个基向量|和|分别表示垂直偏振方向和水平偏振方向，那么任意一个随机的偏振方向(任意一个态)都可以用这两个基向量的线性组合形式表示：a|+b|(2.1)其中，a和b表示复数，而且|a|+|b|=1。在量子力学中，两个基向量|和|被称作本征态。我们感兴趣的是光子的偏振方向,所以可以把一个光子的偏振状态表示为上述形式。实际上，任意两个相互正交的非零单位向量都可以作为状态空间的基。,基态测量,对量子状态的测量要求把该状态分别投影到其对应的正交基(本征态)上，如图1所示。图 1 投影在基上的量子态的测量 对该状态进行测量的时候，观测到状态|的概率为|a|，而观测到状态|的概率为|b|。,由于测量在相互正交的基上进行的，所以若不特别说明的话，所有的基均指的是正交的。另外，对量子态的测量还将使被测量的量子态改变为测量结果所表示的态。也就是说，如果我们对量子态|=a|+b|进行测量所得的结果是|，那么量子态|就变成了|，如果再用相同的基进 行测量，测量结果一定还是态|。从这个实验中我们可以看到，量子态可以是本征态，也可以是叠加态。若将通过偏振片看作测量，你就会发现，量子态经过测量会发生状态塌缩，由最初的状态塌缩到测量给出的状态上。,1-2 状态空间和狄拉克表示法,一个量子系统的状态空间由各种粒子的位置、动量、偏振、自旋等组成，并且随时间的演化过程遵循 Schrdinger 方程，而它的状态空间可以用波函数的Hilbert空间来描述。对于量子计算，我们不必考虑这些波函数的细节。只需涉及有限的量子系统和考虑由抽象波函数如|张成的，具有内积的有限维复向量空间。量子力学系统由Hilbert空间的向量表示，表示量子态的向量称为状态向量。,1-2-1 狄拉克符号,一般量子状态空间和作用在其上的变换可以使用向量、矩阵来描述，而物理学家狄拉克提出了一套更为简洁的符号(bra/ket)表示状态向量。使用称为右矢(ket)的符号|x表示量子态，使用称为左矢(bra)的符号共轭转置。例如，一个二维复向量空间的正交基可以表示为|0,|1。任意向量 都可以表示为|0和|1的线性组合a|0+b|1。,1-2-2 内积和外积表示,两个向量|x 和|y 的内积记为。例如，对于基|0,|1有=1，=0。两个向量|x 和|y 的外积记为|x,|1，由于|0=|0|0=因此，|0对转换为|0，对而将|0转换 的变换。,例子,如果令|0=，|1=，那么有 和|1的变换。,1-3 线性算子,算子是向量空间的一个重要概念。在量子力学中出现的算子大多为线性算子。一些重要算子的概念定义1 设V 为向量空间，A 为函数，A：VV。A称为V上的的线性算子当且仅当下式成立 在复向量空间中，一个线性算子A 可被写为如下nn的矩阵 A|注：线性算子一般满足可加性和连续性，只满足前者为加法算子。,其它算子定义,定义2 算子 称为A 的伴随算子。定义3 如果算子A 满足，则A 称为厄米(Hermitian)算子。定义4 如果算子A 满足，则A 称为酉算子。将一个酉算子作用于一个向量空间的全部向量，对其中任意向量，得到一个新向量，这一操作称为向量的酉变换。酉变换不改变向量的模，也不改变两向量的内积，因此不改变其正交关系。定义5 投影算子(projector)在空间中取一组标准正交基，投影算子，作用到 上得到，这是基 乘以向量 在 上的分量，实际上这是 在 上的投影。称为投向 子空间的投影算子。,1-4 Schrdinger方程,封闭量子系统的演化由Schrdinger方程描述。该方程是量子系统状态演化的基本规律，也是量子计算所遵循的基本规律。当量子系统没有测量的时候，系统遵循这基本规律进行持续的。（1.3）其中Plank常数，实际应用中取。H 是Hamiltonian算子，该算子与特定的物理系统的结构有关，也就是说它的具体的形式(或近似形式)由描述这系统的物理原理确定。如果我们已知这系统在时间 t=0 某一初态，我们可以定义一个算子 U(t)，使得(1.4)于是得到算子方程(1.5)方程的解为(1.6),量子计算机基本信息表示量子门量子并行性,量子计算,2-1 量子计算机基本信息表示,如果我们把数据送入计算机处理，就必须把数据表示成计算机能够识别的形式。在经典的计算机中，信息单元用二进制的1个位来表示，它不是处于0态就是处于1态。在二进制量子计算机中，信息单位称为量子位(Qubit)，它除了处于0态或 1态外，还可处于叠加态。这是两者重要区别之一。n个量子位的有序集合称为n位量子寄存器。它的态是n个量子位态的张量积（即直积）。,2-1-1 量子位 一个量子位是定义在二维复向量空间的一个单位向量。该空间 由一对特定的标准正交基|0，|1 张成。这两个基可以分别对应光子的偏振方向|和|，或偏振方向|和|，也可对应电子的自旋向上(spin-up)和自旋向下(spin-down)状态。取基态(本征态)|0 和|1 对应经典的位 0 和 1 进行编码。量子位可以处在|0 和|1的叠加态 a|0+b|1。读取包含在量子位的信息只有通过测量得到。当测量一个量子位(都对应的基)时，量子位的叠加态就会变成它的一个本征态。因此测量的结果一定是此次测量相应的两个基中的一个。测量会改变量子位的状态，因此不能用不同的基测量同一态。,2-1-2 多量子位,n 个相互无关的粒子组成系统(二维向量空间)。设V 和 W分别是由基 和 张成，则 经典系统：形成一个2n维的向量空间。其笛卡儿积把上述两基 合并形成新空间基，其中基的顺序是任意的。量子系统：形成一个2 维的状态空间。其张量积为 其中基的顺序也是任意的。设其基为|0，|1，则该系统的 状态基为 也可更为紧缩的写为：|00，|01，|10，|11。具有三个量子位的系统，其状态空间的基为：|000，|001，|010，|011，|100，|101，|110，|111 一般来说，具有 n 个量子位的系统，其状态空间由2 个基向量张成。由此可见，量子系统的状态空间的维数随其粒子数的增长成指数倍增长。,纠缠态,在量子系统中，我们不能通过独立描述各个量子位的状态来描述整个量子系统的状态。例如，量子系统的状态|00+|11 就不能用两个量子位各自的状态来描述。换句话说，我们不能找到这样的四个数，使它们满足（3.1）由于=（3.2）若要使上式成立，显然要满足。此式意味着 或。(3.1)式和(3.2)式矛盾。所以量子系统的状态|00+|11不能以这种方式描述。我们把不能通过这种方法分解的态称为纠缠态(entangled states)。这些状态所表示的情形在经典理论中不存在。实际上多个量子位态若不能表成张量积形式即为处于纠缠态。,在量子计算机系统中，表示计算机状态的寄存器称为量子寄存器。它不同与经典计算机的寄存器。首先所有的计算数据全部保存在量子寄存器中，执行计算的时候，量子变换作用在这个量子寄存器上，完成的结果仍然保存在这个量子寄存器中。经典存储器(n位)和量子寄存器，若它们能表示2 个状态，但在某一时刻，前者只能保存2 态中的一个，后者却能保存这2 个状态。如果量子寄存器中保存 2 个状态，并且是一个叠加态。在没有对它进行测量时，它以不同的概率处于这些基本状态中，但是一旦对量子寄存器进行测量，它的状态就会发生塌缩，变成了这2 个状态中的一个。注：n个量子位（量子比特）的有序集合称为量子寄存器。它的态是n个量子位的张量积（直积）。,量子寄存器,2-1-3 测量,对一个或多个量子位的的测量，会将系统状态投射到与测量值相应的状态子空间中去。测量的结果是一个概率，它等于测量所用基复系模的平方和。两个量子位组成的系统的测量 任意一个两个量子位的系统都可以表示为：a|00+b|01+c|10+d|11 其中，a，b，c，d 都是复数。并且 假设我们用基|0，|1 对该系统的第一个量子位进行测量，测量为|0 的概率为。并且如果测量结果是|0，则系统投射到由|00 和为|01 张起的子空间，其结果a|00+b|01。为得到被测态，须做规一化处理，使总概率为1：测量为|1 的概率，测量第二个量子位的工作类似。,2-2 量子门,到目前为止，我们看到的仅仅是在测量时状态才会改变的静态量子系统。而一个量子系统的动态特性在其未被测量前要满足 Schrdinger 方程，动态过程必须保证正交的方法从一个状态转换到另一状态，在复向量空间上保持正交的线性变换是酉变换。在复向量空间上的任何线性变换都可以用一个矩阵来描述。设 是矩阵M的共轭转置矩阵，若，则M 是一个酉变换。一个量子态空间上的任何酉变换都是合法的量子变换，反之亦然。酉变换的一个重要特点就是这些变换都是可逆的，因此量子变换也必须是可逆的。,2-2-1 单个量子位门,常用基本单门 I 是恒等变换，X 是求非变换，Z 为相位移操作，Y=ZX 为两者的组合。可以验证所有这些变换都是酉变换。例如,Walsh-Hadamard 变换 H:当 H 作用于|0时，它将生成一个叠加态。当它分别作用于 n 个量子位的时候，它将生成个2 可能状态的一个叠加态，该叠加态可以看成是数字 0 到2-1的二进制表示：,2-2-2 两个量子位门,受控非门(controlled-NOT-gate)对两个量子位操作规则：如果第一个量子位为1，该门对第二 个量子位进行求非操作，如果第一个量子位为0，则第二个量子位 保持不变。变换可表示成如下形式：它可表示成经典的函数形式：,2-2-3 三个量子位门,T(Toffoli)门控控非门(controlled-controlled-NOT-gate)它对三个量子位的操作规则是：如果前两位的输入同时为1，那么第三位在输出时就要取反。T 门表示成经典的函数形式：T 门对布尔逻辑来说，是一个完备的量子门。例如，若 z 固定为1，则第三位输出结果为；若 x 固定为1，则得到2位得XOR操作。其变换如下图所示。,2-3 量子并行性,量子并行性(quantum parallelism)概念 量子并行性是许多量子算法的一个基本特征，简言之，量子并行性使量子计算机可以同时计算函数 f(x)在许多不同的 x 处的值。我们已知 是一个线性变换。如果将 作用于某个叠加态，它将会同时作用于该叠加态的所有基向量，并且把对所有基向量的作用结果进行叠加，产生一个新的叠加态。由此可见，用此方法计算函数 f(x)，只需应用一次 就可同时计算出 x 取 n 个不同值时的结果。这种效果称之为量子并行性。量子算法的强大能力来源于量子并行性。,计算函数的一般方法,为n 个量子位制备一个初始的叠加态|000 用Walsh-Hadamard 变换对其进行变换，得到如下叠加态：该叠加态可以看作是在 范围之内的所有整数的一个叠加态。由 的线性特性可以得到=其中，f(x)为我们所要计算的函数。,谢谢！,