Quantum Computing (fall2013) Instructor:Shengyu Zhang. Lecture 2 Factoring and Abelian HSP 1.Factoring problem Historical importance:one of the oldest computational problems. Average-case hardness:not only hard on worst-case inputs,but also on average-case inputs. Relation to RSA:If Factoring is easy,then RSA is insecure. Best classical algorithms:20)for n-bit numbers. Shor's quantum algorithm:0(n3). 2.Quantum Fourier Transform (QFT) Definition of QFT.In next class,we will define Fourier transform on general groups.Today, we'll only focus on a cyclic group:ZN.(Sometimes it is written as Z/NZ.)Define @N e/N,a primitive N-th root of unity.For each EZ the QFT has the following effect on the basis vectorx): 1 yEZN yEZN In other words,the QFT is the following operator.F(In matrix form,it is 1 1 1 1 ON FUNL=N a呢 呢 呢2 : 1 @y-1 -2 @W-D)(N-1)
Quantum Computing (Fall 2013) Instructor: Shengyu Zhang. Lecture 2 Factoring and Abelian HSP 1. Factoring problem Historical importance: one of the oldest computational problems. Average-case hardness: not only hard on worst-case inputs, but also on average-case inputs. Relation to RSA: If Factoring is easy, then RSA is insecure. Best classical algorithms: 2 O(√𝑛 log 𝑛) for 𝑛-bit numbers. Shor’s quantum algorithm: 𝑂(𝑛 3 ). 2. Quantum Fourier Transform (QFT) Definition of QFT. In next class, we will define Fourier transform on general groups. Today, we’ll only focus on a cyclic group: 𝑍𝑁 . (Sometimes it is written as 𝒁/𝑁𝒁.) Define 𝜔𝑁 = 𝑒 𝑖2𝜋/𝑁, a primitive 𝑁-th root of unity. For each 𝑥 ∈ 𝑍𝑁, the QFT has the following effect on the basis vector |𝑥〉: |𝑥〉 → 1 √𝑁 ∑ 𝜔𝑁 𝑥𝑦 |𝑦〉 𝑦∈𝑍𝑁 = 1 √𝑁 ∑ 𝑒 2𝜋𝑖𝑥𝑦/𝑁|𝑦〉 𝑦∈𝑍𝑁 . In other words, the QFT is the following operator. 𝐹𝑍𝑁 = 1 √𝑁 ∑ 𝜔𝑁 𝑥𝑦 |𝑦〉〈𝑥| 𝑥,𝑦∈𝑍𝑁 . In matrix form, it is
Algorithm for QFT for Zz.(Note:the group is the cyclic group Z with N=2",but not (Z2)xn).Write both x and y by binary numbers,namelyx=2x and y= ∑=d2Jy.Then 1 ) yo- ye{0,1" 18 e2mi2-y》 2”0ye0.1 1-1 n-1 )+exp2mi∑2i+k-"xk =☒ k=0 j=0 2 n-1 =:☒1） j=0 The QFT can be implemented by the following circuit,where we use some controlled-R,, ithRWe've leamed controlled-NOTin the ast css,the general controlled-unitary operator is similar:Conditioned on the control bit being 1,do the unitary.) xo) H-kn-1) x） HR2 3n-2 Kn-3) 12) n-2》 Rn-2Rn-1 z xm-)HR2®3…Rm-®m Izo) We can see intuitively why this circuit works by verifying the first two qubits.For the top qubit,one Hadamard gates makes the output )+(-1)1)=10)+e2ix/1)=z). (Note that we used the fact that ei=1 for all s0 and ,1).)Now look at the second qubit.After the Hadamard gate,it is )+eix1).The controlled-R2 gate further putsa phase exon ),thus the final output on this qubit is)+ e2mi(号+I1）=lzn-z）.Using the same way one can verify the rest qubits
Algorithm for QFT for 𝒁𝟐 𝒏. (Note: the group is the cyclic group 𝑍𝑁 with 𝑁 = 2 𝑛 , but not (𝑍2 ) ×𝑛 ). Write both 𝑥 and 𝑦 by binary numbers, namely 𝑥 = ∑ 2 𝑘𝑥𝑘 𝑛−1 𝑘=0 and 𝑦 = ∑ 2 𝑗𝑦𝑗 𝑛−1 𝑗=0 . Then The QFT can be implemented by the following circuit, where we use some controlled-𝑅𝑟 , with 𝑅𝑟 = ( 1 0 0 𝑒 2𝜋𝑖/2 𝑟 ). (We’ve learned controlled-NOT in the last class; the general controlled-unitary operator is similar: Conditioned on the control bit being 1, do the unitary.) We can see intuitively why this circuit works by verifying the first two qubits. For the top qubit, one Hadamard gates makes the output |0〉 + (−1) 𝑥0 |1〉 = |0〉 + 𝑒 2𝜋𝑖𝑥0 /2 |1〉 = |𝑧𝑛−1 〉. (Note that we used the fact that 𝑒 2𝜋𝑖2 𝑠 𝑥𝑘 = 1 for all 𝑠 ≥ 0 and 𝑥𝑘 ∈ {0,1}.) Now look at the second qubit. After the Hadamard gate, it is |0〉 + 𝑒 2𝜋𝑖𝑥1 /2 |1〉. The controlled-𝑅2 gate further puts a phase 𝑒 2𝜋𝑖𝑥0 /4 on |1〉, thus the final output on this qubit is |0〉 + 𝑒 2𝜋𝑖( 𝑥1 2 + 𝑥0 4 ) |1〉 = |𝑧𝑛−2 〉. Using the same way one can verify the rest qubits
3.Tool-Phase Estimation One important application of QFT on Zw is Phase Estimation.Suppose that there is a unitary operation U and we are given the ability of applying controlled-U operations for j= 2,22,23,...We are also given an eigenstate lu),which corresponds to an eigenvalueu The task is to get an estimate of(Recall the spectral decomposition of normal matrices.) Here is a simple algorithm using QFT. Algorithm:Quantum phase estimation Inputs:(1)A black box wich performs a controlled-U operation,for integer j, (2)an eigenstate u)of U with eigenvalue e,and (3)t=n+[log (2+ qubits initialized to 0). Outputs:An n-bit approximation u tou. Runtime:O(t2)operations and one call to controlled-U black box.Succeeds with probability at least 1-e. Procedure: 1. 10)1u) initial state 1 2-1 2. vE∑bw create superposition j=0 2-1 3. 1 → v2i lj》Ulu) apply black box j=0 121 2mijpulj)lu) result of black box j=0 4. →lpa)川u) apply inverse Fourier transform 5. →pu measure first register To get an intuition why the above algorithm is correct,consider the case that the eigenvalue has an n-bit binary representation.Then the inverse Fourier transform in Step 4 above will give exactly the eigenvalueu.(Recall the definition of Fourier transform:lp）→∑yezn e2 j》,)
3. Tool – Phase Estimation One important application of QFT on 𝑍𝑁 is Phase Estimation. Suppose that there is a unitary operation 𝑈 and we are given the ability of applying controlled-𝑈 𝑗 operations for j = 2, 2 2 , 2 3 , … We are also given an eigenstate |𝑢〉, which corresponds to an eigenvalue 𝜑𝑢 . The task is to get an estimate of 𝜑𝑢 . (Recall the spectral decomposition of normal matrices.) Here is a simple algorithm using QFT. To get an intuition why the above algorithm is correct, consider the case that the eigenvalue has an 𝑛-bit binary representation. Then the inverse Fourier transform in Step 4 above will give exactly the eigenvalue 𝜑𝑢. (Recall the definition of Fourier transform: |𝜑〉 → ∑ 𝑒 2𝜋𝑖𝜑𝑗|𝑗〉 𝑦∈𝑍𝑁 .)
4.Quantum algorithm for Factoring First,Factoring is known to be equivalent to another problem called Order Finding.In Order Finding,we are given two positive integers x and N that are co-prime to each other.We want to find the smallest r s.t.x"=1 mod N.For example,when x=5 and N=21, then it is not hard to verify that the powers of x are 5,4,20,16,17,1(all mod 21),thus the order is 6. Algorithm for Order Finding.Consider the unitary matrix Uly)=xy mod N)for each y E[0,N-1].Note that for different y's,Uly)'s are also different.(Suppose xy=xy2, then x(y-y2)=0,impossible because x is co-prime with N.)Thus U is indeed a unitary matrix. For each s[-1],consider state lu=skmod N).It is actually an eigenvector of U with respect to eigenvalue ws: -1 Ulu;) 1 sk +1 mod N)= 1 sk-11 xk mod N)=ωlus k=0 Thus we can run the Phase Estimation algorithm on lus)and we'll get s/r. Some issues:We don't have lus);after all it needs information of r.But note that r一1 r-1 r-1 1 〉lus〉= >wrsk lxk mod N)=11). 三0 S=0 k=0 (Fork≠0，∑sw,sk=0.)So if we prepare1）and run the Phase Estimation algorithm, then we will get/).Measuring the first register gives s/r.Using a simple procedure called the comed fraction one can getsandmay mot be butr is at least a factor of r.Doing this a couple oftimes and get"and take the least common multiple ofr'would give us r.(Actually,a careful analysis shows that most likely the least common multiple of r'and r"is already r.) Another issue is that in Phase Estimation,we need controlled-U2operations
4. Quantum algorithm for Factoring First, Factoring is known to be equivalent to another problem called Order Finding. In Order Finding, we are given two positive integers 𝑥 and 𝑁 that are co-prime to each other. We want to find the smallest 𝑟 s.t. 𝑥 𝑟 = 1 mod 𝑁. For example, when 𝑥 = 5 and 𝑁 = 21, then it is not hard to verify that the powers of 𝑥 are 5, 4, 20, 16, 17, 1 (all mod 21), thus the order is 6. Algorithm for Order Finding. Consider the unitary matrix 𝑈|𝑦〉 = |𝑥𝑦 mod 𝑁〉 for each 𝑦 ∈ [0,𝑁 − 1]. Note that for different 𝑦’s, 𝑈|𝑦〉’s are also different. (Suppose 𝑥𝑦1 ≡ 𝑥𝑦2 , then 𝑥(𝑦1 − 𝑦2 ) ≡ 0, impossible because 𝑥 is co-prime with 𝑁.) Thus 𝑈 is indeed a unitary matrix. For each 𝑠 ∈ [0, 𝑟 − 1], consider state |𝑢𝑠 〉 = 1 √𝑟 ∑ 𝜔𝑟 −𝑠𝑘 |𝑥 𝑘 mod 𝑁〉 𝑟−1 𝑘=0 . It is actually an eigenvector of 𝑈 with respect to eigenvalue 𝜔𝑟 𝑠 : 𝑈|𝑢𝑠 〉 = 1 √𝑟 ∑ 𝜔𝑟 −𝑠𝑘 |𝑥 𝑘+1 mod 𝑁〉 𝑟−1 𝑘=0 = 1 √𝑟 ∑ 𝜔𝑟 −𝑠(𝑘−1) |𝑥 𝑘 mod 𝑁〉 𝑟−1 𝑘=0 = 𝜔𝑟 𝑠 |𝑢𝑠 〉. Thus we can run the Phase Estimation algorithm on |𝑢𝑠 〉 and we’ll get 𝑠/𝑟. Some issues: We don’t have |𝑢𝑠 〉; after all it needs information of 𝑟. But note that 1 √𝑟 ∑|𝑢𝑠 〉 𝑟−1 𝑠=0 = 1 √𝑟 ∑ 1 √𝑟 ∑ 𝜔𝑟 −𝑠𝑘|𝑥 𝑘 mod 𝑁〉 𝑟−1 𝑘=0 𝑟−1 𝑠=0 = |1〉. (For 𝑘 ≠ 0, ∑ 𝜔𝑟 −𝑠𝑘 s = 0.) So if we prepare |1〉 and run the Phase Estimation algorithm, then we will get 1 √𝑟 ∑ |𝑠/𝑟〉|𝑢𝑠 〉 𝑟−1 𝑠=0 . Measuring the first register gives 𝑠/𝑟. Using a simple procedure called the continued fraction, one can get 𝑠′ and 𝑟 ′ s.t. 𝑠 ′ 𝑟 ′ = 𝑠 𝑟 . 𝑟 ′ may not be 𝑟, but 𝑟 ′ is at least a factor of 𝑟. Doing this a couple of times and get 𝑟 ′′ , 𝑟 ′′′ , … and take the least common multiple of 𝑟 ′ , 𝑟 ′′ , 𝑟 ′′′ , … would give us 𝑟. (Actually, a careful analysis shows that most likely the least common multiple of 𝑟 ′ and 𝑟 ′′ is already 𝑟.) Another issue is that in Phase Estimation, we need controlled-𝑈 2 𝑗 operations
5.Hidden Subgroup Problem (HSP) Definition of HSP.Order Finding and many other problems fall into the framework of Hidden Subgroup Problem(HSP).In HSP,there is a function f:GS on a group G,which containsa subgroup H.H partitions G by(left)cosets.We have the promise that f is constant on each coset, and distinct on different cosets.The goal is to identify H efficiently.In quantum algorithms,wecan access f by controlled-f gates.In particular,we can make the following transform:Ix)10) Ix)If(x)》 HSP for finite Abelian groups.Any finite Abelian group G is isomorphic to Zn,X...x ZFor each element a=(a,,ak)∈Zn,×…×Znk,definea character function Xa:G→C by xa(x1…xk)=ω.2i.waxla1…ak),and define the QFTby）→ a).It is easily checked that each is a homomorphism:Xy Xa(xy).The set ofthe xa's is denoted by G,which is isomorphic to G itself.One property for G is that any two distinct characters are orthogonal.In particular,if a (0,…,0),then∑xEGXa(x)=0. Algorithm. aree l) /prepare a uniform superposition query f a2.(x》 measure If(x)》 a乙，enls+）for anunknwdm 赢品2ec2enxs+W measure a random x with x(y)=1,Vy E H. Do this for t=o(loglGD)times,and obtain x1,...,x.For a character x,define its kernel as ker(x)=g E G:x(g)=1],and it is easily seen that kernel is a subgroup of G. Claim.For some T=log2Gl,it holds that H==ker (with high probability. Proof.First,there is a fact that Hx(y)=1,Vy EH=x:H<ker (x)}is a group and it's isomorphic to the quotient group G/H.Thus H=GHI.Similarly K=
5. Hidden Subgroup Problem (HSP) Definition of HSP. Order Finding and many other problems fall into the framework of Hidden Subgroup Problem (HSP). In HSP, there is a function 𝑓:𝐺 → 𝑆 on a group 𝐺, which contains a subgroup 𝐻. 𝐻 partitions 𝐺 by (left) cosets. We have the promise that 𝑓 is constant on each coset, and distinct on different cosets. The goal is to identify 𝐻 efficiently. In quantum algorithms, we can access 𝑓 by controlled-𝑓 gates. In particular, we can make the following transform: |𝑥〉|0〉 → |𝑥〉|𝑓(𝑥)〉. HSP for finite Abelian groups. Any finite Abelian group 𝐺 is isomorphic to 𝑍𝑛1 × ⋯ × 𝑍𝑛𝑘 . For each element 𝑎 = (𝑎1 ,… , 𝑎𝑘 ) ∈ 𝑍𝑛1 × ⋯ × 𝑍𝑛𝑘 , define a character function 𝜒𝑎 : 𝐺 → 𝐶 by 𝜒𝑎 (𝑥1 …𝑥𝑘 ) = 𝜔𝑛1 𝑎1𝑥1 … 𝜔𝑛𝑘 𝑎𝑘𝑥𝑘 |𝑎1 …𝑎𝑘 〉, and define the QFT by |𝑥〉 → 1 √|𝐺| ∑ 𝜒𝑎 (𝑥)|𝑎〉 𝑎 . It is easily checked that each 𝜒𝑎 is a homomorphism: 𝜒𝑎 (𝑥𝑦) = 𝜒𝑎 (𝑥)𝜒𝑎 (𝑦). The set of the 𝜒𝑎 ’s is denoted by 𝐺̂, which is isomorphic to 𝐺 itself. One property for 𝐺̂ is that any two distinct characters are orthogonal. In particular, if 𝑎 ≠ (0,… ,0), then ∑ 𝜒𝑎 (𝑥) 𝑥∈𝐺 = 0. Algorithm. 1 √|𝐺| ∑ |𝑥〉 𝑥∈𝐺 // prepare a uniform superposition query 𝑓 → 1 √|𝐺| ∑ |𝑥〉|𝑓(𝑥)〉 𝑥∈𝐺 measure |𝑓(𝑥)〉 → 1 √|𝐻| ∑ |𝑠 + 𝑦〉 𝑦∈𝐻 for an unknown and random 𝑠 ∈ 𝐺 QFT → 1 √|𝐻||𝐺| ∑ ∑ 𝜒(𝑠 + 𝑦)|𝜒〉 𝜒∈𝐺̂ 𝑦∈𝐻 𝑚𝑒𝑎𝑠𝑢𝑟𝑒 → a random 𝜒 with 𝜒(𝑦) = 1, ∀𝑦 ∈ 𝐻. Do this for 𝑡 = 𝑂(log|𝐺|) times, and obtain 𝜒1 , …, 𝜒𝑡 . For a character 𝜒, define its kernel as ker(𝜒) = {𝑔 ∈ 𝐺:𝜒(𝑔) = 1}, and it is easily seen that kernel is a subgroup of 𝐺. Claim. For some 𝑇 = log2 |𝐺|, it holds that 𝐻 = ⋂ ker (𝜒𝑖 ) 𝑖=1,…,𝑇 with high probability. Proof. First, there is a fact that 𝐻 ⊥ ≝ {𝜒: 𝜒(𝑦) = 1,∀𝑦 ∈ 𝐻} = {𝜒: 𝐻 ≤ ker (𝜒)} is a group and it’s isomorphic to the quotient group 𝐺/𝐻. Thus |𝐻 ⊥| = |𝐺|/|𝐻| . Similarly |𝐾𝑡 ⊥ | =
IG/Kl.Suppose that after t times,K=nf=ker (xi)is still strictly larger than H.The next eration gives a radom∈H'SinceK+1≤K,we know that≤unless K=K.Since KKker ()it suffices to show thatKker(1. Note that Kker()meansTherefore.ker( IGl/八Hl HKl.This ratio is at most 1/2 since we assumed that H is a proper subgroup of Kt. Note There are many explanations of Shor's algorithm,see the wiki page.We basically followed [NC00], Chapter 5 and [CvD10]Section III. For the Hidden Subgroup Problem part,see [CvD10],Section IV-C. Reference [NC0O]Michael Nielsen and Isaac Chuang,Quantum Computation and Quantum Information, Cambridge University Press,2000 [CvD10]Andrew M.Childs and Wim van Dam,Quantum algorithms for algebraic problems,Reviews of Modern Physics,Volume 82,January-March 2010. Exercise 1.Verify that the QFToperator FN is unitary 2.Write down the QFT for Z2,Z3.Z4.Zs. 3.Suppose NWe wantauniformsuperposition).Prove that we canobtain it by simply preparing n qubits all in state 0),and then applying a Hadamard gate on each qubit
|𝐺|/|𝐾𝑡 |. Suppose that after 𝑡 times, 𝐾𝑡 = ⋂𝑖=1 𝑡 ker (𝜒𝑖 ) is still strictly larger than 𝐻. The next iteration gives a random 𝜒 ∈ 𝐻 ⊥ . Since 𝐾𝑡+1 ≤ 𝐾𝑡 , we know that |𝐾𝑡+1 | |𝐾𝑡 | ≤ 1 2 unless 𝐾𝑡+1 = 𝐾𝑡 . Since 𝐾𝑡+1 = 𝐾𝑡 ∩ ker (𝜒), it suffices to show that Pr 𝜒∈𝐻⊥ [𝐾𝑡 ⊆ ker(𝜒)] ≤ 1/2. Note that 𝐾𝑡 ⊆ ker(𝜒) means 𝜒 ∈ 𝐾𝑡 ⊥ . Therefore, Pr 𝜒∈𝐻⊥ [𝐾𝑡 ⊆ ker(𝜒)] = |𝐾𝑡 ⊥| |𝐻⊥| = |𝐺|/|𝐾𝑡 | |𝐺|/|𝐻| = |𝐻|/|𝐾𝑡 |. This ratio is at most 1/2 since we assumed that 𝐻 is a proper subgroup of 𝐾𝑡 . Note There are many explanations of Shor’s algorithm, see the wiki page. We basically followed [NC00], Chapter 5 and [CvD10] Section III. For the Hidden Subgroup Problem part, see [CvD10], Section IV-C. Reference [NC00] Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000. [CvD10] Andrew M. Childs and Wim van Dam, Quantum algorithms for algebraic problems, Reviews of Modern Physics, Volume 82, January–March 2010. Exercise 1. Verify that the QFT operator 𝐹𝑁 is unitary. 2. Write down the QFT for 𝑍2, 𝑍3, 𝑍4, 𝑍5. 3. Suppose 𝑁 = 2 𝑛. We want a uniform superposition 1 √𝑁 ∑ |𝑥〉 𝑁 𝑥=1 . Prove that we can obtain it by simply preparing 𝑛 qubits all in state |0〉, and then applying a Hadamard gate on each qubit