第一章 3. Deutsch algorithm.pptVIP

Deutsch Algorithm Outline Hadamard transform Deutsch Algorithm Simon’s algorithm Other problems Hadamard transform Hadamard transform on one q-bit Hadamard transform Hadamard transform on the Bloch sphere picture Correspond to rotation and reflection 单量子比特门对应于球面上的旋转和反射。 Hadamard transform 先绕y轴旋转90。， 再绕x轴旋转180。 Hadamard transform Hadamard transform Hadamard transform on n qubits Here “.” is bitwise inner product ，module 2 . 模2按位内积 Deutsch Algorithm Simple Deutsch algorithm Simple Deutsch algorithm Simple Deutsch algorithm Simple Deutsch algorithm NMR Results of the Deutsch Jozsa Algorithm 意义： Measurements in bases other than the computational basis |+=(|0+|1)/21/2, |-=(|0-|1)/21/2 |0=(|++|-)/21/2, |1=(|+-|-)/21/2 Thank you! Uf(x) H H H H Frontside Backside ancilla ancilla Deutsch-Jozsa Algorithm f00 0 constant f11 0 constant f01 1 balanced f10 1 balanced J.A.Jones and M. Mosca, J. Chem. Phys. 109, 1648 (1998), I.L. Chuang et al. Nature 393, 143 (1998) Sven Zülsdorff, master thesis, Stuttgart, 1999 M. S. Anwar et al. Phys. Rev. A 70, 032324 (2004) (parahydrogen) 3. Deutsch-Jozsa Algorithm Experimental Result 量子线路可以让我们仅用对f(x)的一次计算，就能够确定f(x)的全局性质，即f(0)+f(1)，这个过程比所有可能的经典设备都要快，因为经典设备至少需要两次计算。 许多量子算法的设计本质在于： 精心选择函数和最终变换，以便有效地确定有关函数的有用全局信息，而经典计算机上无法快速得到。 Deutsch-Jozsa Algorithm Deutsch problem: Alice位于A地，她从{0,1,…,2n-1}个数中选取 1个数x，发给位于B地的Bob。 Bob选择两类函数（常数或平衡）之一计算出f(x)，并发给 A。 Alice如何用尽可能少的通信，确定出Bob用的是常数还是平衡函数，她能够做到多快？ Deutsch-Jozsa Algorithm Alice用一个n量子比特的寄存器存储她的查询输入，用一个单量子比特寄存器存储Bob给的答案，她把查询和答案寄存器置于一个叠加态，Bob用量子并行性计算f(x)，把结果放在答案寄存器中，Alice用Hadamard变换干涉查询寄存器的状态，再经过适当的测量，决定f是 平衡函数还是常数。 Deutsch-Jozsa Algorithm Step1：状态初始化 Step2:用Hadamard门产生叠加 Step3:用Uf计算函数f Step4:进行Hadamard变换 Step5测量最终输出z 当且仅当z是全0态，f是常数。 Three caveats: 1 Deutsch’s problem is not an especially important problem. 2 The comparison between classical and quantum algorithm is in some ways an apple and oranges comparison. 3 probabilistic classical computer can