3. Deutsch algorithm.ppt

1、Deutsch Algorithm,Quantum Computation and Quantum information,2009.03.23,Quantum Game,Outline,Hadamard transform Deutsch Algorithm Simons algorithm Other problems,Hadamard transform,Hadamard transform on one q-bit,Hadamard transform,Hadamard transform on the Bloch sphere picture Correspond to rotati

2、on and reflection 单量子比特门对应于球面上的旋转和反射。 Hadamard transform 先绕y轴旋转90。， 再绕x轴旋转180。,Parallel operation on quantum register,Questions： (1) Suppose a quantum register has n qubits, how to determine this vector using these n qubits?,(2)Can quantum hadamard transformation on n qubits be achieved by quantum h

3、adamard transformation on one qubit? These relate to parallel operation on quantum register, then we will answer the above questions.,Tensor product of quantum vector,Definition Suppose are n qubits, then define n-dimensional quantum vector,is tensor product of A1, A2, An.,The probability the tensor

4、 product result is is .,Definition Suppose are two quantum vectors, we define their tensor product as,Tensor product of two quantum vector,qubit A,qubit B,=,Two Quantum Systems,tensor张量积。,Concept of entanglement If one n-dimensional quantum vector is the tensor product of some n qubits, then these n

5、 qubits dont entangle, else these n qubits have entanglement(纠缠).,Example: 2-dimensional quantum vector,is not the tensor product of some 2 qubits.,Definition Suppose are two quantum vectors, T1 and T2 are two quantum transformations on A and B, respectively, we define their tensor product as,A,Tens

6、or product of quantum transformation,B,A,B,Thorem is 1-dimensional HT, then the tensor product of n HT is,n-dimensional Hadamard Transform,viz.,n-dimensional HT,- Transformation on quantum vector -,Especially，,Hadamard transform,Eg:n=2: T|00=,Hadamard transform,Hadamard transform on n qubits Here “.

7、” is bitwise inner product ，module 2 . 模2按位内积,The Hadamard transform on n qubits initially in the all state is described as follows:,Hadamard 变换 产生了所有计算基的平衡叠加，而且它的效率非常高，仅用了n个门就产生了2n个状态的叠加。,Hadamard transform produces an equal superposition of all computation basis states.,Postulate 4: The state spac

8、e of a composite physical system is the Tensor product of the state spaces of the component physical systems. Moreover, if we have systems numbered 1 through n, and system number i is prepared in the state , then the joint state of the total system is,composite physical system(P94),复合物理系统(P94),假设4:

9、复合物理系统的状态空间是分物理系统状态空间的张量积，若将分系统编号为1到n，系统i的状态被置为，则整个系统的状态为：,D.Deutsch, 1992, Firstly demonstrated the superiority of quantum computer.,Deutsch Algorithm,David Deutsch Oxford, U.K.,Problem Determine the function,is constant or balanced,Quantum : a single query suffices. only yes/no outcome desired.,D.

10、 Deutsch and R. Jozsa, Proc. Roy. Soc. London A 439, 553 (1992),Classically: need at least 2n-1+1 queries,Step 1：Preparation of superposition state:,Deutsch Algorithm,How to prepare it ?,Step 2: Quantum Transformation,量子计算算法的基本模型 经典计算机上运行的算法未必是可逆变换，但量子计算机却要求量子算法是可逆变换。为此，必须将经典算法f(x)转换为可逆变换。这个转换可用下述方法

11、实现： 设 ,则计算f(x)的过程等价于下述过程： 这就是一个可逆变换,而且它还是对合变换. 这里我们忽略了中间变量，通常我们取 b=0。,Review,Step 3, perform quantum tranformation,Deutsch Algorithm,Step 4,The probability that the result is 0 is,Deutsch Algorithm,Step 5 read the first registers result: (1)If the result is 0, then f(x) is not balanced function; (2)

12、If the result is not 0, then f(x) is not constant function.,Deutsch Algorithm,Simple Deutsch algorithm Modified Deutsch algorithm,Mapping a single bit to a binary function f(x) with x e 0,1 and f(x) e 0,1,constant,constant,balanced,balanced,Deutsch:,9:00,Deutsch Algorithm,Example,There are intotal 4

13、 different bool functions f00,f01,f10,f11,Simple Deutsch algorithm,原始算法的改进和简化版本，将 量子的并行性和量子力学中称为干涉(interference)的性质结合起来。,Simple Deutsch algorithm,Step1: input |0|1 Step2: Hadamard transform on the two q-bit,we will get Step3:Uf,Simple Deutsch algorithm,Step4: Hadamard transform on the first q-bit,Si

14、mple Deutsch algorithm,Step5:measure on the first q-bit ,we will determined f(0)+f(1) |0- - - - |1- - -,H,H,x x y y+f(x),H,Uf(x),H,H,H,H,Frontside,Backside,ancilla,ancilla,Deutsch-Jozsa Algorithm,NMR Results of the Deutsch Jozsa Algorithm,f00,0,constant,f11,0,constant,f01,1,balanced,f10,1,balanced,J

15、.A.Jones and M. Mosca, J. Chem. Phys. 109, 1648 (1998), I.L. Chuang et al. Nature 393, 143 (1998),Sven Zlsdorff, 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(

16、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量子比特

17、的寄存器存储她的查询输入，用一个单量子比特寄存器存储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 Deutschs problem is not an espec

18、ially important problem. 2 The comparison between classical and quantum algorithm is in some ways an apple and oranges comparison. 3 probabilistic classical computer can solve this problem quickly.,三个提醒:,1 Deutschs 问题不是一个具有实质重要性的问题. 2 经典算法和量子算法很难比较，这是因为计算函数值的方法差别很大. 3 概率经典计算机很快以非常高的概率决定Deutschs 问题.,

19、Simons algorithm,2-to-1 function with s period,Definition Suppose f :0,1m 0,1n , if there is s0 to any x1 x2， f(x1) f(x2) is equivalent to x1 x2 s, then f (x) is a 2-to -1 function with s period.,Simons Problem,Suppose f :0,1m 0,1n is either 1-1 function or 2-to-1 function with s0. Design one algori

20、thm to distinguish that f is either 1-1 function or 2-to-1 function with s0, and if f is 2-to-1 function, find s.,Simons algorithm,Step 1,produce a superimposed state,Step 2, perform quantum transformation,Step 3, perform quantum transformation,Analysis on the amplitudes of quantum vector,Simons alg

21、orithm,(1) If f is 1-1 function, different x corresponds to different f(x), | y, f(x)are different，so each amplitude of | y, f(x)is 2-n. (2)If f is 2-to-1 function with s0, f(x)=f(y) is equivalent to yx s，so,When sy0，axy21-n; when sy1,axy 0.,This indicates that we can calculate s after get n linear independent y.,The amplitude of | y, f(x)is,Simons algorithm,Step 4,read, and record the results y of| y, f(x).,Step 5,repeat the process from step 1 to step 4 N times, and get y1, y2, yN.,Step 6,solve the equations,to determine a value of s. If f(s)=f(0n),the