The Power of Basis Selection in Fourier Sampling: Hidden Subgroup Problems in Affine Groups
Cristopher Moore University of New Mexico moore@cs.unm.edu Daniel Rockmore Dartmouth College rockmore@cs.dartmouth.edu Leonard J. Schulman CalTech schulman@caltech.edu
Abstract Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a unknown subgroup H of a group G must be determined from a quantum state  over G that is uniformly supported on a left coset of H . These hidden subgroup problems are typically solved by Fourier sampling : the quantum Fourier transform of  is computed and measured. When the underlying group is nonabelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation as well as its name) occurs. It has remained open whether the strong method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of the form Zq Zp , where q | (p - 1) and q = p/polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the "forgetful" abelian method are insufficient for these groups so that, in fact, it appears that use of the corresponding nonabelian representation theory is crucial. We extend this to an informationtheoretic solution for the hidden subgroup problem over the groups Zq Zp where q | (p - 1) and, in particular, the affine groups Ap . Finally, we prove a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

Alexander Russell University of Connecticut acr@cse.uconn.edu

1 The hidden subgroup problem One of the principal quantum algorithmic paradigms is the use of the abelian Fourier transform to discover a function's hidden periodicities. In the examples relevant to quantum computing, a function h defined on an abelian group G has "hidden periodicity" if there is a "hidden" subgroup H of G so that h is precisely invariant under translation by H or, equivalently, h is constant on the cosets of H and takes distinct values on distinct cosets. The hidden subgroup problem is the problem of determining the subgroup H from such a function. Algorithms for these problems typically adopt the approach detailed below, called Fourier sampling [2]: Step 1. Prepare two registers, the first in a uniform superposition over the elements of a group G and the second with the value zero, yielding the state 1 = 1g | |g  |0 . G| G

Step 2. Calculate the (classical polynomial-time) function h defined on G and XOR it with the second register. This entangles the two registers and results in the state 2 = 1g | |g  |h(g ) . G| G

Step 3. Measure the second register. This produces a uniform superposition over one of h's level sets, i.e., the set of group elements g for which h(g ) takes the measured value h0 . As the level sets of h are the cosets of H , this puts the first register in a uniform distribution over superpositions on one of those cosets, namely cH where h(c) = h0 . Moreover, it

1113


disentangles the two registers, resulting in the state 3 = h 1 | |ch  |h0 . H | H

Step 4. Compute the Fourier transform of 3 and measure the result. For example, in Simon's algorithm [22] for the "XOR-mask" oracle problem, the "ambient" group G over which the Fourier transform is performed is Zn , and 2 H is a subgroup of order 2. In Shor's factoring algorithm [21] G is the group Z where n is the number we wish to n factor, h(x) = rx mod n for a random r < n, and H is the subgroup of Z of index order(r). (However, since n |Z | is unknown, Shor's algorithm actually performs the n transform over Zq where q is polynomially bounded by n; see [21] or [8, 9].) These are all abelian instances of hidden subgroup problems (HSPs). Interest in nonabelian versions of the HSP evolved from the relation to the elusive Graph Automorphism problem: it would be sufficient to solve efficiently the HSP over the permutation group Sn in order to have an efficient quantum algorithm for graph automorphism (see, e.g., Jozsa [13] for a review). This was the impetus behind the development of the first nonabelian quantum FFT [1] and is, to a large degree, the reason that the nonabelian HSP has remained such an active area of research in quantum algorithms. In general, we will say that the HSP for a family of groups has a Fourier sampling algorithm if a procedure similar to that outlined above works. Specifically, the algorithm prepares a superposition of the form 1h | |ch , H | H

basis to the information gleaned from the measurement is the sub ject of this article. Since we are typically interested in exponentially large groups, we will take the size of our input to be n = log |G|. Throughout, "polynomial" means polylogarithmic in the size of the group. Nonab elian HSPs: History and Context. Though a number of interesting results have been obtained on the nonabelian HSP, the groups for which efficient solutions are known remain woefully few and sporadic. On the positive side, Roetteler and Beth [18] give an algorithm for the wreath product Zk Z2 . 2 Ivanyos, Magniez, and Santha [12] extend this to the more general case of semidirect products K Zk where 2 K is of polynomial size, and also give an algorithm for groups whose commutator subgroup is of polynomial size. Friedl, Ivanyos, Magniez, Santha and Sen solve a problem they call Hidden Translation, and thus generalize this further to what they call "smoothly solvable" groups: these are solvable groups whose derived series is of constant length and whose abelian factors are each the direct product of an abelian group of bounded exponent and one of polynomial size [5]. (See also Section 5.) In another vein, Ettinger and Høyer [3] show that the HSP is solvable for the dihedral groups in an information-theoretic sense; namely, a polynomial number of quantum queries to the function oracle gives enough information to reconstruct the subgroup, but the best known reconstruction algorithm takes exponential time. More generally, Ettinger, Høyer and Knill [4] show that for arbitrary groups the HSP can be solved information-theoretically with a finite number of quantum queries, but do not give an explicit set of measurements to do so. Our current understanding of the HSP, then, divides group families into three classes.

where H is the hidden subgroup of G and c is an element I. Fully Reconstructible. Subgroups of a family selected at random from G (cf. Step 3 above), computes of groups G = {Gi } are ful ly reconstructible if the (quantum) Fourier transform of this state, and the HSP can be solved with high probability by measures the result. After a polynomial number of such a quantum circuit of size polynomial in log |Gi |. trials, a polynomial amount of classical computation, and, perhaps, a polynomial number of classical queries I I. Information-Theoretically Reconstructible. to the function h to confirm the result, the algorithm Subgroups of a family of groups G = {Gi } are produces a set of generators for the subgroup H with information-theoretical ly reconstructible if the soluhigh probability. When G is abelian, the notion of tion to the HSP for Gi is determined information"measuring" the resulting (Fourier transformed) state theoretically by the fully measured result of a quanhas a clear meaning: one observes the "frequency"  tum circuit of size polynomial in log |Gi |. with probability equal to the squared magnitude of the transform at that frequency. In the case where the I I I. Quantum Information-Theoretically Recontransform is taken over a non-abelian group, however, it structible. Subgroups of a family of groups G = is necessary to select bases for each representation of G {Gi } are quantum information-theoretical ly reconto perform full measurement. (This is explained in more structible if the solution to the HSP for Gi is dedetail in the sequel.) The relationship of this choice of termined by the quantum state resulting from a

1114


quantum circuit of polynomial size in log |Gi |, in subspaces are the trivial subspace Cd and {0}. the sense that there is a POVM that yields the For a function f : G  C and an irreducible ^ subgroup H with constant probability. (Note that representation , f () denotes the Fourier transform of there is no guarantee that this POVM can be im- f at  and is defined by plemented by a small quantum circuit.) d g  ^ In each case, the quantum circuit has oracle access to a f (g )(g ) . f () = |G| function h : G  S , for some set S , with the property that f is constant on each left coset of a subgroup H , Note that f takes values in C while  is matrixand distinct on distinct cosets. In this language, then, the result of [4] shows that valued. It is a fact that a finite group has a finite subgroups of arbitrary groups are quantum information- number of distinct irreducible representations (up to theoretically reconstructible, whereas it is known that isomorphism), and the Fourier transform of a function ^ subgroups of abelian groups are in fact fully recon- f : G  C is the collection of matrices f (), taken over structible. The other work cited above has labored to all distinct irreducible representations . Fixing a group G and a subgroup H , we shall focus place specific families of (nonabelian) groups into the primarily on the functions c : G  C of form more algorithmically meaningful classes I and II above. 1 All the above results use the abelian Fourier trans if g  cH, form, even in the cases in which the groups of interest |H | c (g ) = are nonabelian; it turns out that each of these groups 0 otherwise, are "close enough" to abelian that a "forgetful" abelian Fourier analysis, which treats the groups as though their as these correspond to the states resulting from Step 3 multiplication rule was commutative, suffices to detect above. The Fourier transform of such a function is then d subgroups. Nevertheless, as we shall see, there are situh  ations in which abelian Fourier analysis does not suffice c () = (c) · (h) . |G||H | and, instead, the full power of the nonabelian Fourier H transform associated with the group is required. Fourier analysis over a finite abelian group A pro- Note, as above, that c () is a d × d matrix. h ceeds by expressing a function f : A  C as a linear As H is a subgroup, it happens that (h) is combination of special functions  : A  C which are precisely |H | times a pro jection operator (see, e.g., [10]); homomorphisms of A into C. If A = Zp , for example, we write h the homomorphisms from A to C are the familiar basis (h) = |H | H () . t functions t : z  e2itz/p  pz , where p = e2i/p . Any function f : A  C can be uniquely expressed as (The rank of  () is determined by the number of H a linear combination of these t ; this change of basis is copies of the trivial representation in the representation precisely the Fourier transform. When G is a nonabelian IndG 1.) With this notation, we can express  () as c H group, however, this same procedure cannot work: in n (c) ·  () where n = d |H |/|G|. For a d × d  H   particular, there are not enough homomorphisms of G matrix M , we let M denote the matrix norm given into C to even span the space of all C-valued functions by M =i on G. The representation theory of finite groups con2 M 2 = tr M |Mij | , structs the ob jects (invertible matrices) which can be j used in place of the C-valued homomorphisms above to  develop a satisfactory theory of Fourier analysis over where M denotes the conjugate transpose of M . Then the probability that we observe the representation  is general groups. Nonab elian Fourier transforms. We only dis2  c () 2 = n (c)H () cuss enough details of the theory to set down notation, and refer to [20] for a more complete exposition. A = n H () 2 = n rk H () , representation of a finite group G is a homomorphism  : G  U(d), where U(d) denotes the group of uni- as (c) is unitary; here rk H () denotes the rank of the tary d × d matrices (with entries from C); the dimen- pro jection operator H (). See [10] for more discussion. sion d = d is referred to as the dimension of . If Since in this general setting Fourier transforms  : G  U(d) is a representation, a subspace W of Cd are matrix-valued, our Fourier sampling algorithm may is said to be invariant if (g )(W )  W for all g . A rep- require measurement of not just which representation resentation is said to be irreducible if the only invariant we are in, but also the row and column.

1115


In particular, Hallgren, Russell, and TaShma [10] show that by measuring only the names of representations--the so-called weak standard method in the terminology of [7]--it is possible to reconstruct normal subgroups (and thus solve the HSP for Hamiltonian groups, all of whose subgroups are normal). More generally, this method reconstructs the normal core of a subgroup, i.e. the intersection of all its conjugates. On the other hand, they show that this is insufficient to solve Graph Automorphism, since even in an information-theoretic sense this method cannot distinguish between the trivial subgroup of Sn and most subgroups of order 2. Grigni, Schulman, Vazirani and Vazirani [7] show that trivial and non-trivial subgroups are still information-theoretically indistinguishable, even if we do measure the rows and columns of the representation, under the assumption that a random basis is used for each representation. In other words, even the strong standard method, in which rows and columns are measured, cannot solve Graph Automorphism unless there exist bases for the representations of Sn with very special computational properties. (They also point out that since we can reconstruct normal subgroups, we can also solve the HSP for groups where the intersection of all normalizers (the Baer norm) has small index.) Finally, recent work of Kuperberg [15] shows that for the HSP over the dihedral groups, consideration of the "plethysm basis" in the representation    , after independent observation of  and  , can lead to a  subexponential (2O( n) ) quantum circuit for the HSP. It is interesting to ask if this method gives similar speedups for the q -hedral and affine groups, discussed below. Contributions of this pap er. An important open question, then, is whether there are cases in which the strong standard method offers any advantage over a simple abelian transform or the weak standard method. In this paper, we settle this question in the affirmative. Our results deal primarily with the q -hedral groups, i.e., semidirect products of the form Zq Zp , and in particular the affine groups Ap  Z Zp where q = p - 1. =p We begin in Section 2 by focusing on full reconstructibility. We define the Hidden Conjugate Problem as follows: given a group G, a non-normal subgroup H , and a function which is promised to be constant on the cosets of some conjugate bH b-1 of H (and distinct on distinct cosets), determine the subgroup bH b-1 by finding an element c  G so that cH c-1 = bH b-1 . We adopt the above classification (fully, information-theoretically, quantum information-theoretically) for this problem in the natural way. Then we show that given a subgroup of sufficiently small index, hidden conjugates in Ap are fully reconstructible (Theorem 2.1). This almost imme-

diately implies that (for prime q = (p - 1)/polylog(p)) subgroups of the q -hedral groups Zp Zp are fully reconstructible (Theorem 2.2). Moreover, our algorithms in Theorems 2.1 and 2.2 rely crucially on the high-dimensional representations of Zq Zp , and we show in Section 4 that abelian methods (in other words, treating the group as a direct product rather than a semidirect one) do not suffice. Section 3 concerns itself with information-theoretic reconstructibility. We generalize the results of Ettinger and Høyer on the dihedral group to the q -hedral groups and show that, assuming q |(p - 1), hidden conjugates are information-theoretically reconstructible in the q hedral groups (Theorem 3.1). We then use this to show that under the same assumptions all subgroups are information-theoretically reconstructible as well (Theorem 3.2). In particular, the subgroups of the affine group are information-theoretically reconstructible. We close in Section 5 by showing that the set of groups for which the HSP can be solved in polynomial time has the following closure property: if H = {Hn } is a family of groups for which we can efficiently solve the HSP and K = {Kn } is a family of groups for which |Kn | = polylog|Hn |, we can also efficiently solve the HSP for the family {Gn }, where each Gn is any extension of Kn by Hn . This subsumes the results of [10] on Hamiltonian groups, and also those of [12] on groups with commutator subgroups of polynomial size. 2 Full reconstructibility Let Ap be the affine group, consisting of ordered pairs (a, b)  Z × Zp , where p is prime, under the multiplip cation rule (a1 , b1 ) · (a2 , b2 ) = (a1 a2 , b1 + a1 b2 ). Ap can be viewed as the set of affine functions f(a,b) : Zp  Zp given by f(a,b) : x  ax + b where multiplication is given by function composition. Structurally, Ap is a semidirect product Z Zp . Its subgroups are as follows: p · Let N  Zp be the normal subgroup of size p = consisting of elements of the form (1, b). · Let H be the non-normal subgroup of size p - 1 consisting of the elements of the form (a, 0). Its conjugates H b = (1, b) · H · (1, -b) consist of elements of the form (a, (1 - a)b). (In the action on Zp , H b is the stabilizer of b.) · More generally, if a  Z has order q , let Na  = p Zq Zp be the normal subgroup consisting of all elements of the form (at , b), and let Ha be the nonnormal subgroup Ha = (a, 0) of size q . Then Ha consists of the elements of the form (at , 0) and its b conjugates Ha = (1, b) · Ha · (1, -b) consist of the elements of the form (at , (1 - at )b).

1116


The representation theory of Ap . Construction of the representations of Ap requires that we fix a generator  of Z . Define  : Z  Zp-1 to be the p p isomorphism ( t ) = t. Let p denote the pth root of unity e2i/p . Then Ap  Z Zp has p - 1 one=p dimensional representations s given by t ((a, b)) = t(a) p-1 , and one (p - 1)-dimensional representation  given by  bj k = aj mod p p ((a, b))j,k = , 1  j, k < p , 0 otherwise Z . p

first carry out a partial measurement on the columns, and then transform the rows by left-multiplying (cH ) by the quantum Fourier transform over Zp-1 , Q ,j =  - (1/ p - 1) p-j . This allows us to infer b by measur1 ing the frequency . In particular, we observe a given value of with probability 1 P( ) = p-1
p-1 j =1

2
- b pj p-j 1

p 2 j -1 1 = e2ij (p - 1)2 =1

where the indices i and j are elements of (The basis selected here is a Gel'fand-Tsetlin basis; see [16].) See [20, §8.2] for a more detailed discussion. where  b The affine group--and more generally, the q -hedral p - . = groups we discuss below--are metacyclic groups, i.e. p -1 extensions of a cyclic group Zp by a cyclic group Zq . In [11], Høyer shows how to perform the (nonabelian) Now note that for any b there is an such that ||  Fourier transform over such groups with a polynomial  /(2(p - 1)). Since (i.e. polylog(p)) number of elementary quantum opera(2x/ )2  sin2 x  x2 tions. (In fact, he does this only up to an overall phase factor, but this is sufficient for our purposes.) for |x|   /2, this gives P ( )  (2/ )2 . Theorem 2.1. Let p be prime. Then the hidden conRecall that the probability that we observed the jugates of Ha in Ap = Z Zp are ful ly reconstructible (p - 1)-dimensional representation  in the first place p if (p - 1)/| a | = polylog(p). is n = 1 - 1/p. Thus if we measure , the column, and then and then guess that b minimizes ||, we will Proof. Consider first the maximal non-normal subgroup be right (1) of the time. This can be boosted to high H = H (where  is a generator of Z ). Carrying out probability by repeating the experiment a polynomial p steps 1 through 3 of the Fourier sampling procedure number of times. outlined in the introduction results in a state over the Consider now the more general case, when the group G which is uniformly supported on a random left hidden subgroup is a conjugate of the subgroup H a coset of the conjugate H b = bH b-1 . We now compute where a's order q is a proper divisor of p - 1. Recall the quantum Fourier transform of this state according that a given conjugate of H consists of the elements of a to the basis above. The associated pro jection operator the form (at , (1 - at )b). Then we have is 1  b(j -k) H b ()j,k =  b(j -k) , 1 k = at j for some t p p-1 p Ha ()j,k = , b q 0 otherwise for 1  j, k < p. This is a circulant matrix of rank one. More specifically, every column is some root of unity for 1  j, k < p. In other words, the nonzero entries are times the vector those for which j and k lie in the same coset of a  Z . p 1 The rank of this pro jection operator is thus the number bj (ub )j = , p-1 p of cosets, which is the index (p - 1)/q of a in Z . Since p n is now q /p, we again observe  with probability 1  j < p. This is also true of (c) · H b (); since (c) has one nonzero entry per column, left multiplying n rk Ha () = (p - 1)/p = 1 - 1/p . by (c) simply multiplies each column of H b () by a phase. Note that in this case Following the same procedure as before, we carry out a partial measurement on the columns of , and then n = d |H |/|G| = (p - 1)/p = 1 - 1/p , Fourier transform the rows. After changing the variable so that upon measurement the (p - 1)-dimensional rep- of summation from t to -t and adding a phase shift resentation  is observed with overwhelming probabil- of e-i(p-1) inside the | · |2 , the probability we observe ity 1 - 1/p. Assuming that we observe , we can a frequency , assuming we find ourselves in the k th

=

1 sin2 (p - 1) (p - 1)2 sin2 

1117


column, is (2.1) 1 P( ) = q
q -1 t

Thus we observe the correct frequency with at least polynomially small probability; again this can be boosted to high probability by repetition.
- (at k mo d p) bt p(a k mod p) p-1

2

We remark that the q -hedral groups Zq Zp embed  naturally in Ap = Z Zp (when q | p - 1), and p that the representation theory of these groups follows immediately from that of the affine groups (see below). In particular, if q is prime then Ha (as above) is the only non-normal subgroup of Zq Zp (where a is a Now note that the terms in the sum are of the form ei generator of Z ) and the proof above implies that we q where (assuming w.l.o.g. that  is positive) can completely solve the Hidden Subgroup Problem for these groups. For instance, if q is a Sophie Germain   [-(p - 1), (p - 1)] . prime, i.e. one for which 2q + 1 is also a prime, we If we again take so that ||   /(2(p - 1)), then can solve the HSP for Zq Z2q+1 . Thus, we have the   [- /2,  /2] and all the terms in the sum have following: nonnegative real parts. We will obtain a lower bound the real part of the sum by showing that a constant Theorem 2.2. Let p and q be prime with q = (p - Zp are ful ly fraction of the terms have   (- /3,  /3), and thus 1)/polylog(p). Then subgroups of Zq reconstructible. have real part more than 1/2. This is the case whenever at k  (p/6, 5p/6), so it is sufficient to prove the following 3 Information-theoretic reconstructibility lemma: We focus now on general q -hedral groups Zq Zp , Lemma 2.1. Let a have order q = p/polylog(p) in Z , for generic values of q dividing p - 1. As above, we p p a prime. Then at least (1/3 - o(1))q of the elements consider the hidden conjugate problem for subgroups in the coset a k are in the interval (p/6, 5p/6). Ha = (a, 0) . We will later patch these results together to obtain results for the full hidden subgroup Proof. We will prove this using Gauss sums, which problem over the affine groups. In this section we show quantify the interplay between the characters of Zp and that the conjugates of Ha are information-theoretically the characters of Z . In particular, Gauss sums establish reconstructible. This generalizes the results of Ettinger p bounds on the distribution of powers of a. Specifically, if and Høyer [3] who show this for the case q = 2, i.e. the a has order q in Z then for any integer k  0 (mod p) dihedral groups. p we have q -1 Theorem 3.1. Let p be prime and q a divisor of p - 1. t at p k = O(p1/2 ) = o(p) . Then hidden conjugates in Zq Zp are information=0 theoretical ly reconstructible. (See [14] and Appendix A.) Proof. The representations of Zq Zp include the q oneNow suppose s of the elements x in a k are in dimensional representations of Zq given by  ((at , b)) = x the set (p/6, 5p/6), for which Re p  -1, and the q t ,  Zq and (p - 1)/q distinct q -dimensional other q - s elements are in [0, p/6]  [5p/6, p), for which representations k given by x Re p  1/2. Thus we have  k as b t = s + u mo d q u p q -1 , k ((a , b))s,t = t 0 otherwise at k Re   (q /2) - (3s/2). (p - 1) =0 q-1 2 t t 1 e2i(a k mod p) . = q (p - 1) =0
p

for each 0  s, t < q . Here k ranges over the elements   If s  (1/3 - )q for any > 0 this is (q ), a of Zp /Zq , or, to put it differently, k takes values in Zp a but k and k are equivalent if k and k re in the same contradiction. coset of a . These k are simply the (p - 1)/q diagonal Now that we know that a fraction 1/3 - of the blocks of the (p - 1)-dimensional representation  of Ap . terms in (2.1) have real part at least 1/2 and the others Note that all conjugates of Ha lie in the (unique) have real part at least 0, we can take = 1/12 (say) and subgroup isomorphic to Zq Zp , where q is the order of write a; thus without loss of generality we may assume that q2 we are working with the largest non-normal subgroup 1 1q 1 P( )  = = . Ha , where a is a generator of Zq . q (p - 1) 8 64 p - 1 polylog(p)

=0

1118


Then summing k over the elements (at , (1 - at )b) This we rewrite = c p gives the associated pro jection operator, 1m  mb  mb os2 - cos2 p-1 p Zp  s  c k(as -at )b m b 1 2 mb 2p b m Ha (k ) ,t = (1/q ) p os - cos 2(p - 1) p Zp c 2 m for 0  s, t < q . This is again a matrix of rank 1, where 2 mb 2 p b m 1 os - cos each column (even after left multiplication by k (c)) is 4(p - 1) p Zp kas b some root of unity times the vector (uk )s = (1/q ) p . p 1 Note that n = q /p. = > . 4(p - 1) 4 We now wish to show that there is a measurement whose outcomes, given two distinct values of b, have (Adding the m = 0 term contributes zero to the sum in large (1/poly(n)) total variation distance. First, we the second line. In the third line we use the facts that perform a series of partial measurements as follows: (i.) |x|  x2 /2 for all |x|  2, the average of cos2 is 1/2, and measure the name of the representation; (ii.) measure the two cosines have zero inner product.) the column of the representation; and (iii.) perform Since the total variation distance between any two a POVM with q outcomes, in each of which s is u or distinct conjugates is bounded below by a constant, u + 1 mod q for some u  Zq . The total probability we by standard results in probability theory we can disobserve one of the q -dimensional representations, since tinguish between the p different conjugates with only there are (p - 1)/q of them, is n (p - 1)/q = 1 - 1/p. O(log p) = poly(n) samples. Thus, hidden conjugates Then these three partial measurements determine k , in q -hedral groups are information-theoretically reconremove the effect of the coset, and determine that s has structible, completing the proof. one of two values, u or u + 1. Up to an overall phase we can write this as a two-dimensional vector What remains to be seen is that in a group of the form Zq Zp , where q | p - 1, it is possible to  k au b . determine the order of a hidden subgroup. Since there 1 p is a unique conjugacy class of subgroups of each order,  k u +1 2 p a b given Theorem 3.1 we can (information-theoretically) reconstruct arbitrary hidden subgroups of Zq Zp . Let H be a hidden subgroup of Zq Zp given by the oracle We now apply the Hadamard transform f : Zq Zp  S , and let p1 . . . pki be the prime 1 k i = O(log q ). factorization of q , in which case k  a 1 For each i  [k ] and 1    i , we will determine if 1 1  p | |H |. This suffices to determine |H |, at which point i 1 -1 2 the subgroup H can be determined by Theorem 3.1. nd measure s. The probability we observe u and u + 1 is then cos2  and sin2  respectively, where  = ( k au (a - 1)b)/p. Now when we observe a q -dimensional representation, the k we observe is uniformly distributed over Z /Zq , and when we perform the POVM, the u we p observe is uniformly distributed over Zq . It follows that the coefficient m = k au (u - 1) is uniformly distributed over Z . For any two distinct b, b , the total variation p distance is then m 1 2(p - 1) c
p  mb  mb os - cos2 p 2

Theorem 3.2. Let p be prime and q a divisor of p - 1. The subgroups of the q -hedral groups Zq Zp are information-theoretical ly reconstructible. In particular, the subgroups of the affine groups Ap = Z Zp are p information-theoretical ly reconstructible. Proof. By initially applying the techniques of [10] (the weak standard method), we may (fully) reconstruct H if H is a non-trivial normal subgroup. (This follows because these particular semidirect product groups have the special property that if A is a non-trivial normal subgroup and A  B , then B is normal; in particular, the normal core   C  -1
G

+

Z p

s p  mb  mb in2 - sin2 p

.

of any non-normal subgroup C is the identity group.) It remains to consider non-normal subgroups H . Recall

1119


that in this case, H is cyclic and |H | is equal to the This is the inner product of a multiplicative character order of a, where H = (a, b) . Now, for each i  [k ] with an additive one, which is another Gauss sum. In and 1    i , let  : Zq Zp  Zq/p be the particular, assuming b = 0, we have i i homomorphism given by P (0, 0) = 1/p   : (a, b)  api . i P (0, = 0) = 1/(p (p - 1)2 ) Then let P (k = 0, 0) = 0 i P (k = 0, = 0) = 1/(p - 1)2 Ai = ker  = {  Zq Zp |  pi = 1} ,
i i

where 1 denotes the identity element of Zq Zp . Ai is i the subgroup of Zq Zp consisting of all elements whose orders are a multiple of p . Consider now the function i (f ,  ) : Zq i Zp  S × Zq/p i

(see Appendix A). Since these probabilities don't b depend on b, the different conjugates Ha with b = 0 are indistinguishable from each other. Thus it appears essential to use the nonabelian Fourier transform and the high-dimensional representations of Ap . 5 Closure under extending small groups In this section we show that for any polynomial-size group K and any H for which we can solve the HSP, we can also solve the HSP for any extension of K by H . (Note that this is more general than split extensions, i.e. semidirect products H K.) This includes the case discussed in [10] of Hamiltonian groups, since all such groups are direct products (and hence extensions) by abelian groups of the quaternion group Q8 [19]. It also includes the case discussed in [5] of groups with commutator subgroups of polynomial size, such a as extra-special p-groups, since in that case K = G nd H  G/G is abelian. Indeed, our proof is an easy = generalization of that in [5]. Theorem 5.1. Let H be a group for which hidden subgroups are ful ly reconstructible, and K a group of polynomial size in log |H |. Then hidden subgroups in any extension of K by H , i.e. any group G with K G and G/K  H , are ful ly reconstructible. = Pro of. We assume that G and K are encoded in such a way that multiplication can be carried out in classical polynomial time. We fix some transversal t(h) of the left cosets of K . First, note that any subgroup L  G can be described in terms of i) its intersection L  K , ii) its pro jection LH = L/(L  K )  H , and iii) a representative  (h)  L  (t(h) · K ) for each h  LH . Then each element of LH is associated with some left h coset of L  K , i.e. L = LH  (h) · (L  K ). Moreover, if S is a set of generators for L  K and T is a set of generators for LH , then S   (T ) is a set of generators for L. We can reconstruct S in classical polynomial time simply by querying the function h on all of K . Then L  K is the set of all k such that h(k ) = h(1), and we construct S by adding elements of L  K to it one at a time until they generate all of L  K .

given by (f ,  )( ) = (f ( ),  ( )). Observe that i i (f ,  ) is constant (and distinct) on the left cosets of i H A and, furthermore, the subgroup H A has order i i p if and only if p divides the order of a. We may then determine if H  A has order p by assuming that it i does, applying the result of Theorem 3.1, and checking the result against the original oracle f . This allows us to determine the prime factorization of |H |, as desired. Therefore, all subgroups of the q -hedral groups Zq Zp are information-theoretically reconstructible. As in the dihedral case [3], we know of no polynomial-time algorithm which can reconstruct the most likely b from these queries. 4 Failure of the ab elian Fourier transform In [3] the abelian Fourier transform over Z2 × Zp is used in a reconstruction algorithm for the dihedral groups. Using this sort of "forgetful" abelian Fourier analysis it is similarly information-theoretically possible to reconstruct subgroups of the q -hedral groups, when q is small enough. However, it does not seem possible to reconstruct subgroups of Ap using the abelian Fourier transform over the direct product Z × Zp . Let us consider the p hidden conjugate problem for H , i.e., Ha where a is a generator of Z . p If a is a generator, the characters of Z × Zp are p kt simply k, (at , b) = p-1 pb . Summing these over Ha = {(at , (1-at )b} shows that we observe the character (k , ) with probability t 2 t 1 kt P (k , ) = p-1 p(1-a )b p (p - 1)2 Z/(p-1) x 2 1 k lo g x - = p-1 a p xb . p (p - 1)2 
Zp

1120


To identify LH , as in [5] we define a new function h on H consisting of the unordered collection of the values of h on the corresponding left coset of K : h (h) = {h(g ) | g  t(h) · K }. Each query to h consists of |K | = poly(n) queries to h. The level sets of h are clearly the cosets of LH , so we reconstruct LH by solving the HSP on H . This yields a set T of generators for LH . It remains to find a representative  (h) in L  (t(h) · K ) for each h  T . We simply query h(g ) for all g  t(h) · K , and set  (h) to any g such that h(g ) = h(1). Since |T | = O(log |H |) = poly(n) this can be done in polynomial time, completing the proof. U nfortunately, we cannot iterate this construction more than a constant number of times, since doing so would require a superpolynomial number of queries to h for each query of h . If K has superpolynomial size it is not clear how to obtain  (h), even when H has only two elements: this is precisely the difficulty with the dihedral group. References
[1] Robert Beals. Quantum computation of Fourier transforms over symmetric groups. In ACM, editor, Proceedings of the twenty-ninth annual ACM Symposium on the Theory of Computing, pages 48­53, El Paso, Texas, 4­6 May, 1997. ACM Press. [2] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory (preliminary abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 11­20, San Diego, California, 16­18 May 1993. [3] Mark Ettinger and Peter Høyer. On quantum algorithms for noncommutative hidden subgroups. Technical Report quant-ph/9807029, Quantum Physics ePrint Archive, 1998. [4] Mark Ettinger and Peter Høyer and Emmanuel Knill. Hidden subgroup states are almost orthogonal. Technical Report quant-ph/9901034, Quantum Physics ePrint Archive, 1999. [5] Katalin Friedl, G´bor Ivanyos, Fr´d´ric Magniez, Mika ee los Santha, and Pranab Sen. Hidden translation and orbit coset in quantum computing. Technical Report quant-ph/0211091, Quantum Physics e-Print Archive, 2002. [6] William Fulton and Joe Harris. Representation Theory: A First Course. Number 129 in Graduate Texts in Mathematics. Springer-Verlag, 1991. [7] Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, and Umesh Vazirani. Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 68­74, 2001.

[8] Lisa Hales and Sean Hallgren. Quantum fourier sampling simplified. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, 1­4 May 1999. [9] Lisa Hales and Sean Hallgren. An improved quantum fourier transform algorithm and applications. In 41st Annual Symposium on Foundations of Computer Science. IEEE, 2000. [10] Sean Hallgren, Alexander Russell, and Amnon TaShma. Normal subgroup reconstruction and quantum computation using group representations. In Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 627­635, 2000. [11] Peter Høyer. Efficient quantum transforms. Technical Report quant-ph/9702028, Quantum Physics e-Print Archive, 1997. [12] G´bor Ivanyos, Fr´d´ric Magniez, and Miklos Santha. a ee Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. Technical Report quant-ph/0102014, Quantum Physics e-Print Archive, 2001. [13] Richard Jozsa. Quantum factoring, discrete logarithms and the hidden subgroup problem. Technical Report quant-ph/0012084, Quantum Physics e-Print Archive, 2000. [14] Sergei V. Konyagin and Igor E. Shparlinski. Character sums with exponential functions and their applications. Number 136 in Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1999. [15] Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. Technical Report quant-ph/0302113, Quantum Physics e-Print Archive, 2003. [16] Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard Schulman. Generic quantum Fourier transforms. In Proceedings of the 15th Annual ACMSIAM Symposium on Discrete Algorithms, New Orleans, LA, 11­13 January 2004. [17] Rudolf Lidl and Harald Niederreiter. Finite Fields. Number 20 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1997. [18] Martin Roetteler and Thomas Beth. Polynomialtime solution to the hidden subgroup problem for a class of non-abelian groups. Technical Report quantph/9812070, Quantum Physics e-Print Archive, 1998. [19] Joseph Rotman. An Introduction to the Theory of Groups. Number 148 in Graduate Texts in Mathematics. Springer-Verlag, 1994. [20] Jean-Pierre Serre. Linear Representations of Finite Groups. Number 42 in Graduate Texts in Mathematics. Springer-Verlag, 1977. [21] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484­ 1509, October 1997. [22] Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474­1483, October 1997.

1121


Acknowledgements. We are grateful to Wim van See [14, §2] for a proof. Dam, Frederic Magniez, Martin R¨tteler, and Miklos o Note that in the body of the paper, we use Zp to Santha for helpful conversations, and to Sally Milius denote the additive group of integers modulo p and Z p and Tracy Conrad for their support. Support for this to denote the multiplicative group of integers modulo p. work was provided by the California Institute of Technology's Institute for Quantum Information (IQI), the Mathematical Sciences Research Institute (MSRI), the Institute for Advanced Study (IAS), NSF grants ITR0220070, ITR-0220264, CCR-0093065, EIA-0218443, QuBIC-0218563, the Charles Lee Powell Foundation, and the Bell Fund. A Notes on exp onential sums The basic Gauss sum bounds the inner products of additive and multiplicative characters of Fp , the finite field of prime cardinality p. Definitive treatments appear in [17, §5] and [14]. Considering Fp as an additive group with p elements, we have p additive characters s : Fp  C, for s  Fp , given by s : s z  pz , where, as above, p = e2i/p is a primitive pth root of unity. Likewise considering the elements of F = Fp \ {0} as a multiplicative group, we have p p - 1 characters t : F  C, for t  F , given by p p t t : g z  pz 1 , where p-1 = e2i/(p-1) is a primitive - (p - 1)th root of unity and g is a multiplicative generator for the (cyclic) group F . p With this notation the basic Gauss sum is the following: Theorem A.1. Let s be an additive character and t a multiplicative character of Fp . If s = 0 and t = 1 then = z s (z ) t (z ) p.
F p

Otherwise  p - 1  z s (z )t (z ) = -1   F p 0 if s = 0, t = 1, if s = 0, t = 1, if s = 0, t = 1.

See [17, §5.11] for a proof. This basic result has been spectacularly generalized. In the body of the paper we require bounds on additive characters taken over multiplicative subgroups of F . p Such sums are discussed in detail in [14]. The specific bound we require is the following. Theorem A.2. Let t be a nontrivial additive character of Fp and a  F an element of multiplicative order p q . Then  O(p1/2 ), if q  p 2 / 3 , q  z-1 z t (a ) = O(p1/4 q 3/8 ), if p1/2  q  p2/3 ,   =0 O(p1/8 q 5/8 ), if p1/3  q  p1/2 .

1122