Chapter 4 The abelian quantum Fourier transform and phase estimation 4.1 Quantum Fourier transform Perhaps the most important unitary transformation in quantum computing is the quantum Fourier transform (QFT).Later,we will discuss the QFT over arbitrary finite groups,but for now we will focus on the case of an abelian group G.Here the transformation is 1 FG:=- ∑∑xwa国 (4.1) VIGI EG vEG where G is a complete set of characters of G,and xu()denotes the yth character of G evaluated at z. (You can verify that this is a unitary operator using the orthogonality of characters.)Since G and G are isomorphic,we can label the elements of G using elements of G,and it is often useful to do so. The simplest QFT over a family of groups is the QFT over G=Z2.The characters of this group are Xy()=(-1)v,so the QFT is simply sV房∑(-1r4=Hn (4.2) I,yEZR You have presumably seen how this transformation is used in the solution of Simon's problem 98. 4.2 QFT over Z2n A more complex quantum Fourier transform is the QFT over G=Z2m: ∑) (4.3) x,y∈Z2n where wm:=exp(2mi/m)is a primitive mth root of unity.To see how to realize this transformation by a quantum circuit,it is helpful to represent the input x as a string of bits,x =xn-1...1zo,and to consider
Chapter 4 The abelian quantum Fourier transform and phase estimation 4.1 Quantum Fourier transform Perhaps the most important unitary transformation in quantum computing is the quantum Fourier transform (QFT). Later, we will discuss the QFT over arbitrary finite groups, but for now we will focus on the case of an abelian group G. Here the transformation is FG := 1 p |G| X x∈G X y∈Gˆ χy(x)|yihx| (4.1) where Gˆ is a complete set of characters of G, and χy(x) denotes the yth character of G evaluated at x. (You can verify that this is a unitary operator using the orthogonality of characters.) Since G and Gˆ are isomorphic, we can label the elements of Gˆ using elements of G, and it is often useful to do so. The simplest QFT over a family of groups is the QFT over G = Z n 2 . The characters of this group are χy(x) = (−1)x·y , so the QFT is simply FZ n 2 = 1 √ 2 n X x,y∈Z n 2 (−1)x·y |yihx| = H⊗n . (4.2) You have presumably seen how this transformation is used in the solution of Simon’s problem [98]. 4.2 QFT over Z2 n A more complex quantum Fourier transform is the QFT over G = Z2n : FZ2n = 1 √ 2 n X x,y∈Z2n ω xy 2n |yihx| (4.3) where ωm := exp(2πi/m) is a primitive mth root of unity. To see how to realize this transformation by a quantum circuit, it is helpful to represent the input x as a string of bits, x = xn−1 . . . x1x0, and to consider
18 Chapter 4.The abelian quantum Fourier transform and phase estimation how an input basis vector is transformed: 国口 1 ∑助 (4.4) 1 V元 2dn2*gn-1…h%）} (4.5) Ⅱ2gn-1…h (4.6) y∈Z2nk=0 n- V2n ☒∑2*) (4.7) k=0yk∈Z2 n-1 =☒) (4.8) k=0 where 1 (4.9) k∈Z2 、1 0)+2叨 (4.10) 0+2 1 (4.11) 方0）+e2ao2-+2++女-21p到 (4.12) (A more succinct way to write this is)+1)),but the above expression is more helpful for understanding the circuit.)In other words,Fl)is a tensor product of single-qubit states,where the kth qubit only depends on the n-k least significant bits of x. This decomposition immediately gives a circuit for the QFT over Z2m.Let Re denote the single-qubit unitary operator 710 Rk=0w2* (4.13) Then the circuit can be written as follows: Izo) 风lm-i) z1) H® lzn-2） 4 zn-3） 122） zn-2〉 12) zn-1)日®2-®3…Bm-dRn 12o)》 This circuit uses O(n2)gates.However,there are many rotations by small angles that do not affect the final result very much.If we simply omit the gates Rk with k=(logn),then we obtain a circuit with O(n log n)gates that implements the QFT with precision 1/poly(n)
18 Chapter 4. The abelian quantum Fourier transform and phase estimation how an input basis vector is transformed: |xi 7→ 1 √ 2 n X y∈Z2n ω xy 2n |yi (4.4) = 1 √ 2 n X y∈Z2n ω x( Pn−1 k=0 yk2 k ) 2n |yn−1 . . . y1y0i (4.5) = 1 √ 2 n X y∈Z2n nY−1 k=0 ω xyk2 k 2n |yn−1 . . . y1y0i (4.6) = 1 √ 2 n nO−1 k=0 X yk∈Z2 ω xyk2 k 2n |yki (4.7) = nO−1 k=0 |zki (4.8) where |zki := 1 √ 2 X yk∈Z2 ω xyk2 k 2n |yki (4.9) = 1 √ 2 (|0i + ω x2 k 2n |1i) (4.10) = 1 √ 2 (|0i + ω Pn−1 j=0 xj 2 j+k 2n |1i) (4.11) = 1 √ 2 (|0i + e 2πi(x02 k−n+x12 k+1−n+···+xn−1−k2 −1 ) |1i). (4.12) (A more succinct way to write this is |zki = √ 1 2 (|0i + ω x 2n−k |1i), but the above expression is more helpful for understanding the circuit.) In other words, F|xi is a tensor product of single-qubit states, where the kth qubit only depends on the n − k least significant bits of x. This decomposition immediately gives a circuit for the QFT over Z2n . Let Rk denote the single-qubit unitary operator Rk := 1 0 0 ω2 k . (4.13) Then the circuit can be written as follows: |x0i · · · • · · · • · · · • H |zn−1i |x1i · · · • · · · • · · · H R2 |zn−2i . . . . . . . . . . . . . . . . . . |xn−3i • · · · • · · · · · · |z2i |xn−2i • · · · H R2 · · · Rn−2 Rn−1 · · · |z1i |xn−1i H R2 R3 · · · Rn−1 Rn · · · · · · |z0i This circuit uses O(n 2 ) gates. However, there are many rotations by small angles that do not affect the final result very much. If we simply omit the gates Rk with k = Ω(log n), then we obtain a circuit with O(n log n) gates that implements the QFT with precision 1/ poly(n)
4.3.Phase estimation 19 4.3 Phase estimation Aside from being directly useful in quantum algorithms,such as Shor's algorithm,The QFT over Z2m provides a useful quantum computing primitive called phase estimation [35,64].In the phase estimation problem,we are given a unitary operator U(either as an explicit circuit,or as a black box that lets us apply a controlled-Ui operation for integer values of j).We are also given a state o)that is promised to be an eigenvector of U,namely Ulo)=e)for someR.The goal is to output an estimate of to some desired precision. The procedure for phase estimation is straightforward.To get an n-bit estimate of o,prepare the quantum computer in the state 1 V2元 ∑z,, (4.14) x∈Z2n apply the operator ∑红⑧U (4.15) r∈Z2n to give the state 际∑k, 1 (4.16) apply an inverse Fourier transform on the first register,and measure.If the binary expansion of o/2m terminates after at most n bits (i.e.,if =2my/2"for some yeZ2m),then the state (4.16)is F2my)), so the result is guaranteed to be the binary expansion of /2.In general,we obtain a good approximation with high probability.In particular,the probability of obtaining the result y(corresponding to the estimate 2my/27 for the phase)is 1 sin2(2n-1) Pr()=22n‘in2(号-票) (4.17） which is strongly peaked around the best n-bit approximation (in particular,it gives the best n-bit approx- imation with probability at least 4/2).We will see the details of a similar calculation when we discuss period finding. 4.4 QFT over ZN and over a general finite abelian group One useful application of phase estimation is to implement the QFT over an arbitrary cyclic group ZN: 1 FN=示 ∑w) (4.18) .yEZN The circuit we derived using the binary representation of the input and output only works when N is a power of two (or,with a slight generalization,some other small integer).But there is a simple way to realize FzN (approximately)using phase estimation. We would like to perform the transformation that maps ))where):=FN)denotes a Fourier basis state.(By linearity,if the transformation acts correctly on a basis,it acts correctly on all states.)It is straightforward to perform the transformation 0),);then it remains to erase the register z)from such a state. Consider the unitary operator that adds 1 modulo N: U=∑z+1 (4.19) IEZN The eigenstates of this operator are precisely the Fourier basis states ):=FZr),since (as a simple calculation shows) F克UFIN=∑l (4.20)
4.3. Phase estimation 19 4.3 Phase estimation Aside from being directly useful in quantum algorithms, such as Shor’s algorithm, The QFT over Z2n provides a useful quantum computing primitive called phase estimation [35, 64]. In the phase estimation problem, we are given a unitary operator U (either as an explicit circuit, or as a black box that lets us apply a controlled-U j operation for integer values of j). We are also given a state |φi that is promised to be an eigenvector of U, namely U|φi = e iφ |φi for some φ ∈ R. The goal is to output an estimate of φ to some desired precision. The procedure for phase estimation is straightforward. To get an n-bit estimate of φ, prepare the quantum computer in the state 1 √ 2 n X x∈Z2n |x, φi, (4.14) apply the operator X x∈Z2n |xihx| ⊗ U x (4.15) to give the state 1 √ 2 n X x∈Z2n e iφx|x, φi, (4.16) apply an inverse Fourier transform on the first register, and measure. If the binary expansion of φ/2π terminates after at most n bits (i.e., if φ = 2πy/2 n for some y ∈ Z2n ), then the state (4.16) is F2n |yi ⊗ |φi, so the result is guaranteed to be the binary expansion of φ/2π. In general, we obtain a good approximation with high probability. In particular, the probability of obtaining the result y (corresponding to the estimate 2πy/2 n for the phase) is Pr(y) = 1 2 2n · sin2 (2n−1φ) sin2 ( φ 2 − πy 2n ) , (4.17) which is strongly peaked around the best n-bit approximation (in particular, it gives the best n-bit approximation with probability at least 4/π2 ). We will see the details of a similar calculation when we discuss period finding. 4.4 QFT over ZN and over a general finite abelian group One useful application of phase estimation is to implement the QFT over an arbitrary cyclic group ZN : FZN = 1 √ N X x,y∈ZN ω xy N |yihx|. (4.18) The circuit we derived using the binary representation of the input and output only works when N is a power of two (or, with a slight generalization, some other small integer). But there is a simple way to realize FZN (approximately) using phase estimation. We would like to perform the transformation that maps |xi 7→ |x˜i, where |x˜i := FZN |xi denotes a Fourier basis state. (By linearity, if the transformation acts correctly on a basis, it acts correctly on all states.) It is straightforward to perform the transformation |x, 0i 7→ |x, x˜i; then it remains to erase the register |xi from such a state. Consider the unitary operator that adds 1 modulo N: U := X x∈ZN |x + 1ihx|. (4.19) The eigenstates of this operator are precisely the Fourier basis states |x˜i := FZN |xi, since (as a simple calculation shows) F † ZN UFZN = X x∈ZN ω −x N |xihx|. (4.20)
20 Chapter 4.The abelian quantum Fourier transform and phase estimation Thus,using phase estimation on U(with n bits of precision where n =O(log N)),we can perform the transformation ,0〉→，x) （4.21) (actually,phase estimation only gives an approximation of z,so we implement this transformation only approximately).By running this operation in reverse,we can erase )and thereby produce the desired QFT. Given the Fourier transform over ZN,it is straightforward to implement the QFT over an arbitrary finite abelian group:any finite abelian group can be written as a direct product of cyclic factors,and the QFT over a direct product of groups is simply the tensor product of QFTs over the individual groups
20 Chapter 4. The abelian quantum Fourier transform and phase estimation Thus, using phase estimation on U (with n bits of precision where n = O(log N)), we can perform the transformation |x, ˜ 0i 7→ |x, x ˜ i (4.21) (actually, phase estimation only gives an approximation of x, so we implement this transformation only approximately). By running this operation in reverse, we can erase |xi, and thereby produce the desired QFT. Given the Fourier transform over ZN , it is straightforward to implement the QFT over an arbitrary finite abelian group: any finite abelian group can be written as a direct product of cyclic factors, and the QFT over a direct product of groups is simply the tensor product of QFTs over the individual groups
Chapter 5 Discrete log and the hidden subgroup problem In this lecture we will discuss the discrete logarithm problem and its relevance to cryptography.We will introduce the general hidden subgroup problem,and show how Shor's algorithm solves a particular instance of it,giving an efficient quantum algorithm for discrete log. 5.1 Discrete log Let G=(g)be a cyclic group generated by g,written multiplicatively.Given an element xEG,the discrete logarithm of r in G with respect to g,denoted log r,is the smallest non-negative integer a such that ga =x. The discrete logarithm problem is the problem of calculating logr. Here are some simple examples of discrete logarithms: .For any G=(g),log 1=0 ·ForG=Z,log32=2 ·ForG=Z41,log126282=101 The discrete logarithm seems like a good candidate for a one-way function.We can efficiently compute ga,even if a is exponentially large (in log G),using repeated squaring.But given z,it is not immediately clear how to compute log,other than by checking exponentially many possibilities.(There are better algorithms than brute force search,but none is known that works in polynomial time.) 5.2 Diffie-Hellman key exchange The apparent hardness of the discrete logarithm problem is the basis of the Diffie-Hellman key exchange protocol,the first published public-key cryptographic protocol. The goal of key exchange is for two distant parties,Alice and Bob,to agree on a secret key using only an insecure public channel.The Diffie-Hellman protocol works as follows: 1.Alice and Bob publicly agree on a large prime p and an integer g of high order.For simplicity,suppose they choose a g for which (g)=Z(i.e.,a primitive root modulo p).(In general,finding such a g might be hard,but it can be done efficiently given certain restrictions on p.) 2a.Alice chooses some a Zp-1 uniformly at random.She computes A:=ga mod p and sends the result to Bob (keeping a secret). 2b.Bob chooses some bZp-1 uniformly at random.He computes B:=go mod p and sends the result to Alice (keeping b secret). 3a.Alice computes K:=Ba mod p=gab mod p. 3b.Bob computes A mod p=gab mod p=K
Chapter 5 Discrete log and the hidden subgroup problem In this lecture we will discuss the discrete logarithm problem and its relevance to cryptography. We will introduce the general hidden subgroup problem, and show how Shor’s algorithm solves a particular instance of it, giving an efficient quantum algorithm for discrete log. 5.1 Discrete log Let G = hgi be a cyclic group generated by g, written multiplicatively. Given an element x ∈ G, the discrete logarithm of x in G with respect to g, denoted logg x, is the smallest non-negative integer α such that g α = x. The discrete logarithm problem is the problem of calculating logg x. Here are some simple examples of discrete logarithms: • For any G = hgi, logg 1 = 0 • For G = Z × 7 , log3 2 = 2 • For G = Z × 541, log126 282 = 101 The discrete logarithm seems like a good candidate for a one-way function. We can efficiently compute g α, even if α is exponentially large (in log |G|), using repeated squaring. But given x, it is not immediately clear how to compute logg x, other than by checking exponentially many possibilities. (There are better algorithms than brute force search, but none is known that works in polynomial time.) 5.2 Diffie-Hellman key exchange The apparent hardness of the discrete logarithm problem is the basis of the Diffie-Hellman key exchange protocol, the first published public-key cryptographic protocol. The goal of key exchange is for two distant parties, Alice and Bob, to agree on a secret key using only an insecure public channel. The Diffie-Hellman protocol works as follows: 1. Alice and Bob publicly agree on a large prime p and an integer g of high order. For simplicity, suppose they choose a g for which hgi = Z × p (i.e., a primitive root modulo p). (In general, finding such a g might be hard, but it can be done efficiently given certain restrictions on p.) 2a. Alice chooses some a ∈ Zp−1 uniformly at random. She computes A := g a mod p and sends the result to Bob (keeping a secret). 2b. Bob chooses some b ∈ Zp−1 uniformly at random. He computes B := g b mod p and sends the result to Alice (keeping b secret). 3a. Alice computes K := Ba mod p = g ab mod p. 3b. Bob computes Ab mod p = g ab mod p = K