Fourier transforms over finite abelian groups Subgroups and CosetsThe hidden subgroup problemFactoring and discrete logCS 294-2 Abelian HSP + Discrete Lo g 10/14/04Fall 2004 Lecture 11Abelian Hidden Subgroup Problem + Discrete Log1 Fourier transforms over finite abelian groupsLet G be a finite abelian group. The characters of G are homomorphismsχj: G → C. There are exactly |G|characters, and they form a group, called the dual group, and denoted byˆG. The Fourier transform over thegroup G is given by:g7→1p|G|∑jχj(g)jConsider, for example G = ZN. The characters are defined byχj(1) =ωjandχj(k) =ωjk. And the Fouriertransform is given by the familiar matrix F, with Fj,k=1√Nωjk.In general, let G∼=ZN1×ZN2×···×ZNl, so that any g ∈ G can be written equivalently as (a1,a2,...,al),where ai∈ ZNi. Now, for each choice of k1,...,klwe have a character given by the mapping:χk1,...,kl(a1,a2,...,al) =ωk1a1N1·ωk2a2N2·····ωklalNlFinally, the Fourier transform of (a1,a2,...,al) can be defined as(a1,a2,... , al) 7→1p|G|∑(k1,...,kl)ωk1a1N1ωk2a2N2·····ωklalNlk1···kl2 Subgroups and CosetsCorresponding to each subgroup H ⊆ G, there is a subgroup H⊥⊆ˆG, defined as H⊥= {k ∈ˆG | k(h) =1 ∀h ∈ H}, whereˆG is the dual group of G. |H⊥| =|G||H|. The Fourier transform over G maps an equalsuperposition on H to an equal superposition over H⊥:Claim1p|H|∑hFTG7→s|H||G|∑k∈H⊥kProof The amplitude of each element k ∈ H⊥is1√|G|√|H|∑h∈Hk(h) =√|H|√|G|. But since |H⊥|=|G||H|, the sumof squares of these amplitudes is 1, and therefore the amplitudes of elements not in H⊥is 0.The Fourier transform over G treats equal superpositions over cosets of H almost as well:CS 294-2, Fall 2004, Lecture 11 1Claim1p|H|∑h∈HhgFTG7→s|H||G|∑k∈H⊥χg(k)kProof This follows from the convolution-multiplication property of Fourier transforms. An equal superpo-sition on the coset Hg can be obtained by convolving the equal superposition over the subgroup H witha delta function at g. So after a Fourier transform, we get the pointwise multiplication of the two Fouriertransforms: namely, an equal superposition over H⊥, andχg.Since the phaseχg(k) has no effect on the probability of measuringk, Fourier sampling on an equalsuperposition on a coset of H will yield a uniformly random element k ∈H⊥. This is a fundamental primitivein the quantum algorithm for the hidden subgroup problem.Claim Fourier sampling performed onΦ=1√|H|∑h∈Hhggives a uniformly random element k ∈ H⊥.3 The hidden subgroup problemLet G again be a finite abelian group, and H ⊆ G be a subgroup of G. Given a function f : G → S whichis constant on cosets of H and distinct on distinct cosets (i.e. f(g) = f(g0) iff there is an h ∈ H such thatg = hg0), the challenge is to find H.The quantum algorithm to solve this problem is a distillation of the algorithms of Simon and Shor. It worksin two stages:Stage I Setting up a random coset state:Start with two quantum registers, each large enough to store an element of the group G. Initialize each ofthe two registers to0. Now compute the Fourier transform of the first register, and then store in the secondregister the result of applying f to the first register. Finally, measure the contents of the second register. Thestate of the first register is now a uniform superposition over a random coset of the hidden subgroup H:00FTG⊗I−→1p|G|∑a∈Ga0f−→1p|G|∑a∈Gaf(a)measure 2nd reg−→1p|H|∑h∈HhgStage II Fourier sampling:Compute the Fourier transform of the first register and measure. By the last claim of the previous section,this results in a random element of H⊥. i.e. random k : k(h) = 0 ∀h ∈ H. By repeating this process, we canget a number of such random constraints on H, which can then be solved to obtain H.Example Simon’s Algorithm: In this case G = Zn2, and H = {0,s}. Stage I sets up a random coset state1/√2x+ 1/√2x+ s. Fourier sampling in stage II gives a random k ∈ Zn2such that k ·s = 0. Repeat-ing this n−1 times gives n −1 random linear constraints on s. With probability at least 1/e these linearconstraints have full rank, and therefore s is the unique non-zero solution to these simultaneous linear con-straints.4 Factoring and discrete logRecall that factoring is closely related to the problem of order finding. To define this problem, recall that:CS 294-2, Fall 2004, Lecture 11 2The set of integers that are relatively prime to N form a group under the operation of multiplication moduloN: Z∗N= {x ∈ ZN: gcd(x,N) = 1}.Let x ∈Z∗N. The order of x (denoted by ordN(x)) is minr≥1xr≡ 1 mod N.The task of factoring N can be reduced to the task of computing the order of a given x ∈ Z∗N. Recall that|Z∗N| = Φ(N), where Φ(N) is the Euler Phi function. If N = pe11···pekkthenφ(N) = (p1−1)pe1−11···(pk−1)pek−1k. Clearly, ordN(x)|Φ(N).Consider the function f : ZΦ(N)→ ZN, where f(a) = xamod N. Then f(a) = 1 if a ∈ hri, where r =ordN(x), and hri denotes the subgroup of Z∗Ngenerated by r. Similarly if a ∈ hri+ k, a coset of hri, thenf(a) = xkmod N. Thus f is constant on cosets of H = h ri.The quantum algorithm for finding the order r or x first uses f to set up a random coset state, and then doesFourier sampling to obtain a random element from H⊥. Notice that the random element will have the formk = s·φ(N)rwhere s is picked randomly from {0,... ,r −1}. If gcd(s,r) = 1 (which holds for random s with reasonablyhigh probability), gcd(k,φ(N)) =φ(N)/r. From this it is easy to recover r. There is no problem discardingbad runs of the algorithm, since the correct value of r can be used to split N into non-trivial factors.Here we assumed that we knowφ(N) or at least a multiple of it. However, given N computingφ(N) is ashard as factoring N. Shor’s factoring algorithm relies on the fact that the result of doing a fourier transformover ZNmay be closely approximated by carrying out the fourier transform over ZMfor M >> N andreinterpreting results.Discrete Log Problem:Computing discrete logarithms is another fundamental problem in modern cryptography. Its assumed hard-ness underlies the Diffie-Helman cryptosystem.In the Discrete Log problem is the following: given a prime p, a
View Full Document
Unlocking...