22 Chapter 5.Discrete log and the hidden subgroup problem At the end of the protocol,Alice and Bob share a key K,and Eve has only seen p,g,A,and B. The security of the Diffie-Hellman protocol relies on the assumption that discrete log is hard.Clearly,if Eve can compute discrete logarithms,she can recover a and b,and hence the key.(Note that it is an open question whether,given the ability to break the protocol,Eve can calculate discrete logarithms,though some partial results in this direction are known. This protocol only provides a means of exchanging a secret key,not of sending private messages.However, very similar ideas can be used to create a public-key cryptosystem(similar in spirit to RSA). 5.3 The hidden subgroup problem It turns out that discrete logarithms can be calculated efficiently on a quantum computer,rendering cryp- tographic protocols such as Diffie-Hellman key exchange insecure.The quantum algorithm for discrete log solves a particular instance of the hidden subgroup problem(HSP) In the general HSP,we are given a black box function f:G-S,where G is a known group and S is a finite set.The function is promised to satisfy f(x)=f(y)if and only if yH (5.1) i.e.,y=ch for some h∈H for some unknown subgroup H<G.We say that such a function hides H.The goal of the HSP is to learn H(say,specified in terms of a generating set)using queries to f. It's clear that H can in principle be reconstructed if we are given the entire truth table of f.Notice in particular that f(1)=f(x)if and only if xE H:the hiding function is constant on the hidden subgroup, and does not take that value anywhere else. But the hiding function has a lot more structure as well.If we fix some element g EG with g H,we see that f(g)=f(r)if and only if xegH,a left coset of H in G with coset representative g.So f is constant on the left cosets of H in G,and distinct on different left cosets. In the above definition of the HSP,we have made an arbitrary choice to multiply by elements of H on the right,which is why the hiding function is constant on left cosets.We could just as well have chosen to multiply by elements of A on the left,in which case the hiding function would be constant on right cosets; the resulting problem would be equivalent.Of course,in the case where G is abelian,we don't need to make such a choice.For reasons that we will see later,this case turns out to be considerably simpler than the general case;and indeed,there is an efficient quantum algorithm for the HSP in any abelian group,whereas there are only a few nonabelian groups for which efficient algorithms are known. You should be familiar with Simon's problem,the HSP with G=Z2 and H ={0,s}for some s Z2 There is a very simple quantum algorithm for this problem,yet one can prove that any classical algorithm for finding s must query the hiding function exponentially many times (in n).The gist of the argument is that,since the set S is unstructured,we can do no better than querying random group elements so long as we do not know two elements z,y for which f(z)=f(y).But by the birthday problem,we are unlikely to see such a collision until we make (VIG/H)random queries. A similar argument applies to any HSP with a large number of trivially intersecting subgroups.More precisely,we have Theorem 5.1.Suppose that G has a set H of N subgroups whose only common element is the identity. Then a classical computer must make (vN)queries to solve the HSP. Proof.Suppose the oracle does not a priori hide a particular subgroup,but instead behaves adversarially, as follows.On the (th query,the algorithm queries ge,which we assume to be different from g1,...,g- without loss of generality.If there is any subgroup HE H for which g giH for all 1 <j<k <e(i.e., there is some consistent way the oracle could assign ge to an as-yet-unqueried coset of a hidden subgroup from H),then the oracle simply outputs e;otherwise the oracle concedes defeat and outputs a generating set for some HE H consistent with its answers so far (which must exist,by construction). The goal of the algorithm is to force the oracle to concede,and we want to lower bound the number of queries required.(Given an algorithm for the HSP in G,there is clearly an algorithm that forces this oracle to concede using only one more query.)Now consider an algorithm that queries the oracle t times before
22 Chapter 5. Discrete log and the hidden subgroup problem At the end of the protocol, Alice and Bob share a key K, and Eve has only seen p, g, A, and B. The security of the Diffie-Hellman protocol relies on the assumption that discrete log is hard. Clearly, if Eve can compute discrete logarithms, she can recover a and b, and hence the key. (Note that it is an open question whether, given the ability to break the protocol, Eve can calculate discrete logarithms, though some partial results in this direction are known.) This protocol only provides a means of exchanging a secret key, not of sending private messages. However, very similar ideas can be used to create a public-key cryptosystem (similar in spirit to RSA). 5.3 The hidden subgroup problem It turns out that discrete logarithms can be calculated efficiently on a quantum computer, rendering cryptographic protocols such as Diffie-Hellman key exchange insecure. The quantum algorithm for discrete log solves a particular instance of the hidden subgroup problem (HSP). In the general HSP, we are given a black box function f : G → S, where G is a known group and S is a finite set. The function is promised to satisfy f(x) = f(y) if and only if x −1 y ∈ H i.e., y = xh for some h ∈ H (5.1) for some unknown subgroup H ≤ G. We say that such a function hides H. The goal of the HSP is to learn H (say, specified in terms of a generating set) using queries to f. It’s clear that H can in principle be reconstructed if we are given the entire truth table of f. Notice in particular that f(1) = f(x) if and only if x ∈ H: the hiding function is constant on the hidden subgroup, and does not take that value anywhere else. But the hiding function has a lot more structure as well. If we fix some element g ∈ G with g /∈ H, we see that f(g) = f(x) if and only if x ∈ gH, a left coset of H in G with coset representative g. So f is constant on the left cosets of H in G, and distinct on different left cosets. In the above definition of the HSP, we have made an arbitrary choice to multiply by elements of H on the right, which is why the hiding function is constant on left cosets. We could just as well have chosen to multiply by elements of H on the left, in which case the hiding function would be constant on right cosets; the resulting problem would be equivalent. Of course, in the case where G is abelian, we don’t need to make such a choice. For reasons that we will see later, this case turns out to be considerably simpler than the general case; and indeed, there is an efficient quantum algorithm for the HSP in any abelian group, whereas there are only a few nonabelian groups for which efficient algorithms are known. You should be familiar with Simon’s problem, the HSP with G = Z n 2 and H = {0, s} for some s ∈ Z n 2 . There is a very simple quantum algorithm for this problem, yet one can prove that any classical algorithm for finding s must query the hiding function exponentially many times (in n). The gist of the argument is that, since the set S is unstructured, we can do no better than querying random group elements so long as we do not know two elements x, y for which f(x) = f(y). But by the birthday problem, we are unlikely to see such a collision until we make Ω(p |G|/|H|) random queries. A similar argument applies to any HSP with a large number of trivially intersecting subgroups. More precisely, we have Theorem 5.1. Suppose that G has a set H of N subgroups whose only common element is the identity. Then a classical computer must make Ω(√ N) queries to solve the HSP. Proof. Suppose the oracle does not a priori hide a particular subgroup, but instead behaves adversarially, as follows. On the `th query, the algorithm queries g`, which we assume to be different from g1, . . . , g`−1 without loss of generality. If there is any subgroup H ∈ H for which gk ∈/ gjH for all 1 ≤ j < k ≤ ` (i.e., there is some consistent way the oracle could assign g` to an as-yet-unqueried coset of a hidden subgroup from H), then the oracle simply outputs `; otherwise the oracle concedes defeat and outputs a generating set for some H ∈ H consistent with its answers so far (which must exist, by construction). The goal of the algorithm is to force the oracle to concede, and we want to lower bound the number of queries required. (Given an algorithm for the HSP in G, there is clearly an algorithm that forces this oracle to concede using only one more query.) Now consider an algorithm that queries the oracle t times before
5.4.Shor's algorithm 23 forcing the oracle to concede.This algorithm simply sees a fixed sequence of responses 1,2,...,t,so for the first t queries,the algorithm cannot be adaptive.But observe that,regardless of which t group elements are queried,there are at most(2)values of,whereas there are N possible subgroups in H.Thus,to satisfy the N conditions that for all H E H,there is some pair j,k such that ggE H,we must have (2)>N, i.e.,t=2(√N). Note that if the adversarial oracle cannot be beaten after t queries,there are two or more standard oracles that cannot be distinguished by the algorithm after t queries,so the lower bound applies in the setting where the algorithm encounters a fixed oracle. Note that there are cases where a classical algorithm can find the hidden subgroup with a polynomial number of queries.In particular,since a classical computer can easily test whether a certain subgroup is indeed the hidden one,the HSP is easy for a group with only a polynomial number of subgroups.Thus,for example,a classical computer can easily solve the HSP in Zp for p prime(since it has only 2 subgroups)and in Z2n(since it has only n+1 subgroups). 5.4 Shor's algorithm Now we will see how Shor's algorithm can be used to calculate discrete logarithms 97.This is a nice example because it's simpler than the factoring algorithm,but the problem it solves is actually at least as hard:factoring N can be reduced to calculating discrete log in Z.(Unfortunately,this does not by itself give a quantum algorithm for factoring,because Shor's algorithm for discrete log in G requires us to know the order of G-but computing=(N)is as hard as factoring N.) Recall that we are given some element x of a cyclic group G=(g),we would like to calculate log,the smallest integer a such that ga =x.For simplicity,let us assume that the order of G,N:=|Gl,is known. (For example,if G=Zy,then we know N=p-1.In general,if we do not know N,we can learn it using Shor's period-finding algorithm,but we will not discuss that here.)We can also assume that xg(i.e., logg1),since it is easy to check whether this is the case. The discrete log problem can be cast as an abelian HSP in the (additive)group ZN x ZN.Define a function f ZN X ZN-G as follows: f(a,B)=x“g3. (5.2) Since f(a,B)=ga lo+8,f is constant on the lines L:={(a,B)EZN a logo+8=Y}. (5.3) In other words,it hides the subgroup H=L0={(0,0),(1,-loga),(2,-2 loga,.,(N-1,-(N-1)logg T)} (5.4) The cosets of H in ZN x ZN are of the form(,6)+H with Y,6EZN.In particular,the set of cosets of the form (0,6)+H={(a,6-aloga x):aEZN}=L5 (5.5) varying over all 6 E ZN gives a complete set of cosets (so the set [0}x ZN is a complete set of coset representatives,i.e.,a transversal of H in ZN x ZN). Shor's algorithm for finding H proceeds as follows.We start from the uniform superposition over ZN xZN and compute the hiding function: 2w×2)=是a,→六e8fa,》 (5.6) a.BEZN Q.BEZN Next we discard the third register.To see what this does,it may be conceptually helpful to imagine that we actually measure the third register.Then the post-measurement state is a superposition over group
5.4. Shor’s algorithm 23 forcing the oracle to concede. This algorithm simply sees a fixed sequence of responses 1, 2, . . . , t, so for the first t queries, the algorithm cannot be adaptive. But observe that, regardless of which t group elements are queried, there are at most t 2 values of gkg −1 j , whereas there are N possible subgroups in H. Thus, to satisfy the N conditions that for all H ∈ H, there is some pair j, k such that gkg −1 j ∈ H, we must have t 2 ≥ N, i.e., t = Ω(√ N). Note that if the adversarial oracle cannot be beaten after t queries, there are two or more standard oracles that cannot be distinguished by the algorithm after t queries, so the lower bound applies in the setting where the algorithm encounters a fixed oracle. Note that there are cases where a classical algorithm can find the hidden subgroup with a polynomial number of queries. In particular, since a classical computer can easily test whether a certain subgroup is indeed the hidden one, the HSP is easy for a group with only a polynomial number of subgroups. Thus, for example, a classical computer can easily solve the HSP in Zp for p prime (since it has only 2 subgroups) and in Z2n (since it has only n + 1 subgroups). 5.4 Shor’s algorithm Now we will see how Shor’s algorithm can be used to calculate discrete logarithms [97]. This is a nice example because it’s simpler than the factoring algorithm, but the problem it solves is actually at least as hard: factoring N can be reduced to calculating discrete log in Z × N . (Unfortunately, this does not by itself give a quantum algorithm for factoring, because Shor’s algorithm for discrete log in G requires us to know the order of G—but computing |Z × N | = φ(N) is as hard as factoring N.) Recall that we are given some element x of a cyclic group G = hgi, we would like to calculate logg x, the smallest integer α such that g α = x. For simplicity, let us assume that the order of G, N := |G|, is known. (For example, if G = Z × p , then we know N = p − 1. In general, if we do not know N, we can learn it using Shor’s period-finding algorithm, but we will not discuss that here.) We can also assume that x 6= g (i.e., logg x 6= 1), since it is easy to check whether this is the case. The discrete log problem can be cast as an abelian HSP in the (additive) group ZN × ZN . Define a function f : ZN × ZN → G as follows: f(α, β) = x α g β . (5.2) Since f(α, β) = g α logg x+β , f is constant on the lines Lγ := {(α, β) ∈ Z 2 N : α logg x + β = γ}. (5.3) In other words, it hides the subgroup H = L0 = {(0, 0),(1, − logg x),(2, −2 logg x), . . . ,(N − 1, −(N − 1) logg x)}. (5.4) The cosets of H in ZN × ZN are of the form (γ, δ) + H with γ, δ ∈ ZN . In particular, the set of cosets of the form (0, δ) + H = {(α, δ − α logg x) : α ∈ ZN } = Lδ (5.5) varying over all δ ∈ ZN gives a complete set of cosets (so the set {0} × ZN is a complete set of coset representatives, i.e., a transversal of H in ZN × ZN ). Shor’s algorithm for finding H proceeds as follows. We start from the uniform superposition over ZN ×ZN and compute the hiding function: |ZN × ZN i := 1 N X α,β∈ZN |α, βi 7→ 1 N X α,β∈ZN |α, β, f(α, β)i. (5.6) Next we discard the third register. To see what this does, it may be conceptually helpful to imagine that we actually measure the third register. Then the post-measurement state is a superposition over group
24 Chapter 5.Discrete log and the hidden subgroup problem elements consistent with the observed function value,which by definition is some coset of H.In particular. if the measurement outcome is g,we are left with the coset state corresponding to (0,6)+H,namely 10,)+团=)=泰 1 >la,6-aloggt) (5.7) However,note that the measurement outcome is unhelpful:each possible value occurs with equal proba- bility,and we cannot obtain 6 from go unless we know how to take discrete logarithms.This is why we may as well simply discard the third register,leaving the system in the mixed state described by the ensemble of pure states(5.7)where 6 is uniformly random and unknown. Now we can exploit the symmetry of the quantum state by performing a QFT over ZN x ZN;then the state becomes 1 t6-a=n∑∑r-kn 1 N3/2 (5.8) a,4,ZN H.VEZN and using the identity =N6a.o,we have 六s (5.9) w∈ZN Now suppose we measure this state in the computational basis.Then we obtain some pair (vlog,v)for uniformly random vE ZN.If v has a multiplicative inverse modulo N,we can divide the first register by v to get the desired answer.If v does not have a multiplicative inverse,we simply repeat the entire procedure again.The probability of success for each independent attempt is o(N)/N=(1/loglog N),so we don't have to repeat the procedure many times before we find an invertible v. This algorithm can be carried out for any cyclic group G so long as we have a unique representation of the group elements,and we are able to efficiently compute products in G.(We need to be able to compute high powers of a group element,but recall that this can be done quickly by repeated squaring.)
24 Chapter 5. Discrete log and the hidden subgroup problem elements consistent with the observed function value, which by definition is some coset of H. In particular, if the measurement outcome is g δ , we are left with the coset state corresponding to (0, δ) + H, namely |(0, δ) + Hi = |Lδi = 1 √ N X α∈ZN |α, δ − α logg xi (5.7) However, note that the measurement outcome is unhelpful: each possible value occurs with equal probability, and we cannot obtain δ from g δ unless we know how to take discrete logarithms. This is why we may as well simply discard the third register, leaving the system in the mixed state described by the ensemble of pure states (5.7) where δ is uniformly random and unknown. Now we can exploit the symmetry of the quantum state by performing a QFT over ZN × ZN ; then the state becomes 1 N3/2 X α,µ,ν∈ZN ω µα+ν(δ−α logg x) N |µ, νi = 1 N3/2 X µ,ν∈ZN ω νδ N X α∈ZN ω α(µ−ν logg x) N |µ, νi, (5.8) and using the identity P α∈ZN ω αβ N = Nδβ,0, we have 1 √ N X ν∈ZN ω νδ N |ν logg x, νi. (5.9) Now suppose we measure this state in the computational basis. Then we obtain some pair (ν logg x, ν) for uniformly random ν ∈ ZN . If ν has a multiplicative inverse modulo N, we can divide the first register by ν to get the desired answer. If ν does not have a multiplicative inverse, we simply repeat the entire procedure again. The probability of success for each independent attempt is φ(N)/N = Ω(1/ log log N), so we don’t have to repeat the procedure many times before we find an invertible ν. This algorithm can be carried out for any cyclic group G so long as we have a unique representation of the group elements, and we are able to efficiently compute products in G. (We need to be able to compute high powers of a group element, but recall that this can be done quickly by repeated squaring.)
Chapter 6 The abelian HSP and decomposing abelian groups Here we describe an algorithm to solve the HSP in any finite abelian group of known structure.We also explain how related ideas can be used to determine the structure of a black-box abelian group. 6.1 The abelian HSP We now consider the HSP for a general abelian group.When the group elements commute,it often makes more sense to use additive notation for the group operation.We use this convention here,writing the condition that f hides H as f(x)=f(y)iff x-yEH. The strategy for the general abelian HSP closely follows the algorithm for the discrete log problem.We begin by creating a uniform superposition over the group, 1 G)= ∑ VIGI rea (6.1) Then we compute the function value in another register,giving 1 ∑，fo》. VIGlr (6.2) Discarding the second register then gives a uniform superposition over the elements of some randomly chosen coset x+H:=x+h:hEH of H in G, z+)=1 ∑z+h) (6.3) √▣ Such a state is commonly called a coset state.Equivalently,since the coset is unknown and uniformly random.the state can be described by the density matrix 阳=阿+e+ 1 (6.4) IEG Next we apply the QFT over G.Then we obtain the state +H):=FGx+H) (6.5) 1 面G ∑∑xg红+hl) (6.6) yEG hEH -V周amu (6.7) yEG
Chapter 6 The abelian HSP and decomposing abelian groups Here we describe an algorithm to solve the HSP in any finite abelian group of known structure. We also explain how related ideas can be used to determine the structure of a black-box abelian group. 6.1 The abelian HSP We now consider the HSP for a general abelian group. When the group elements commute, it often makes more sense to use additive notation for the group operation. We use this convention here, writing the condition that f hides H as f(x) = f(y) iff x − y ∈ H. The strategy for the general abelian HSP closely follows the algorithm for the discrete log problem. We begin by creating a uniform superposition over the group, |Gi := 1 p |G| X x∈G |xi. (6.1) Then we compute the function value in another register, giving 1 p |G| X x∈G |x, f(x)i. (6.2) Discarding the second register then gives a uniform superposition over the elements of some randomly chosen coset x + H := {x + h: h ∈ H} of H in G, |x + Hi = 1 p |H| X h∈H |x + hi. (6.3) Such a state is commonly called a coset state. Equivalently, since the coset is unknown and uniformly random, the state can be described by the density matrix ρH := 1 |G| X x∈G |x + Hihx + H|. (6.4) Next we apply the QFT over G. Then we obtain the state |x\+ Hi := FG|x + Hi (6.5) = 1 p |H| · |G| X y∈Gˆ X h∈H χy(x + h)|yi (6.6) = s |H| |G| X y∈Gˆ χy(x)χy(H)|yi (6.7)
26 Chapter 6.The abelian HSP and decomposing abelian groups where X(H)= (6.8) Note that applying the QFT was the right thing to do because the state Pr is G-invariant.In other words, it commutes with the regular representation of G,the unitary matrices U(r)satisfying U(z)y)=x+y)for allx,y∈G:we have UPm=何∑le+y+Hmg+川 (6.9) yEG +-+网 = (6.10) PHU(-x) (6.11) PHU(). (6.12) It follows that pr:=FcpF is diagonal (indeed,we verify this explicitly below),so we can measure without losing any information.We will talk about this phenomenon more when we discuss nonabelian Fourier sampling. Note that xy is a character of H if we restrict our attention to that subgroup.If x(h)=1 for all hEH, then clearly xy(H)=1.On the other hand,if there is any h'H with xu(h')1(i.e.,if the restriction of Xy to H is not the trivial character of H),then since h'+H=H,we have xy(H)=H ∑X(h) (6.13) 向名州+的 (6.14) =xy(h)xu(H) (6.15) which implies that x(H)=0.(This also follows from the orthogonality of characters of H, 面∑xwar=i, 1 6.16) 元CH taking y'to be the trivial character.)Thus we have z+H)= H ，Xg(z)ly） (6.17) :Xw(H)=1 or,equivalently,the mixed quantum state DH 皿 ∑ ww('1=I巴 ∑l) (6.18) x∈Gy,:Xy(H)=X(H)=1 :Xw(H)=1 Next we measure in the computational basis.Then we obtain some character xy that is trivial on the hidden subgroup H.This information narrows down the possible elements of the hidden subgroup:we can restrict our attention to those elements gEG satisfying xy(g)=1.The set of such elements is called the kernel of Xy, ker Xy={g∈G:Xy(g)=1: (6.19) it is a subgroup of G.Now our strategy is to repeat the entire sampling procedure many times and compute the intersection of the kernels of the resulting characters.After only polynomially many steps,we claim that the resulting subgroup is H with high probability.It clearly cannot be smaller than H(since the kernel of every sampled character contains H),so it suffices to show that each sample is likely to reduce the size of H by a substantial fraction until H is reached
26 Chapter 6. The abelian HSP and decomposing abelian groups where χy(H) := 1 |H| X h∈H χy(h). (6.8) Note that applying the QFT was the right thing to do because the state ρH is G-invariant. In other words, it commutes with the regular representation of G, the unitary matrices U(x) satisfying U(x)|yi = |x + yi for all x, y ∈ G: we have U(x)ρH = 1 |G| X y∈G |x + y + Hihy + H| (6.9) = 1 |G| X z∈G |z + Hihz − x + H| (6.10) = ρHU(−x) † (6.11) = ρHU(x). (6.12) It follows that ˆρH := FGρHF † G is diagonal (indeed, we verify this explicitly below), so we can measure without losing any information. We will talk about this phenomenon more when we discuss nonabelian Fourier sampling. Note that χy is a character of H if we restrict our attention to that subgroup. If χy(h) = 1 for all h ∈ H, then clearly χy(H) = 1. On the other hand, if there is any h 0 ∈ H with χy(h 0 ) 6= 1 (i.e., if the restriction of χy to H is not the trivial character of H), then since h 0 + H = H, we have χy(H) = 1 |H| X h∈h0+H χy(h) (6.13) = 1 |H| X h∈H χy(h 0 + h) (6.14) = χy(h 0 )χy(H), (6.15) which implies that χy(H) = 0. (This also follows from the orthogonality of characters of H, 1 |H| X x∈H χy(x)χy0 (x) ∗ = δy,y0 , (6.16) taking y 0 to be the trivial character.) Thus we have |x\+ Hi = s |H| |G| X y : χy(H)=1 χy(x)|yi (6.17) or, equivalently, the mixed quantum state ρˆH = |H| |G| 2 X x∈G X y,y0 : χy(H)=χy0 (H)=1 χy(x)χy0 (x) ∗ |yihy 0 | = |H| |G| X y : χy(H)=1 |yihy|. (6.18) Next we measure in the computational basis. Then we obtain some character χy that is trivial on the hidden subgroup H. This information narrows down the possible elements of the hidden subgroup: we can restrict our attention to those elements g ∈ G satisfying χy(g) = 1. The set of such elements is called the kernel of χy, ker χy := {g ∈ G: χy(g) = 1}; (6.19) it is a subgroup of G. Now our strategy is to repeat the entire sampling procedure many times and compute the intersection of the kernels of the resulting characters. After only polynomially many steps, we claim that the resulting subgroup is H with high probability. It clearly cannot be smaller than H (since the kernel of every sampled character contains H), so it suffices to show that each sample is likely to reduce the size of H by a substantial fraction until H is reached