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 ℤq × ℤp, 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 ℤq × ℤp 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.
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which an 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, in a suitably chosen basis, as well as its name) occurs. It has remained open whether the strong standard 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 H of the q-hedral groups, i.e., semidirect products
Zq⋉Zp, where
q∣(p−1), and in particular the affine groups
Ap, can be information-theoretically reconstructed using the strong standard method. Moreover, if
∣H∣=p/polylog(p), these subgroups can be fully reconstructed with a polynomial amount of quantum and classical computation. We compare our algorithms to two weaker methods that have been discussed in the literature—the “forgetful” abelian method, and measurement in a random basis—and show that both of these are weaker than the strong standard method. Thus, at least for some families of groups, it is crucial to use the full power of representation theory and nonabelian Fourier analysis, namely, to measure the high-dimensional representations in an adapted basis that respects the group's subgroup structure. We apply our algorithm for the hidden subgroup problem to new families of cryptographically motivated hidden shift problems, generalizing the work of van Dam, Hallgren, and Ip on shifts of multiplicative characters. Finally, we close by proving a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form /spl Zopf//sub p/ /sup r/ /spl times/ /spl Zopf//sub p/ fixed r (including the Heisenberg group, r = 2). In particular our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.