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 study permutation groups of given minimal degree without the classical primitivity assumption. We provide sharp upper bounds on the order of a permutation group H ≤ S_n of minimal degree m and on the number of its elements of any given support. These results contribute to the foundations of a non-commutative coding theory. A main application of our results concerns the Hidden Subgroup Problem for S_n in quantum computing. We completely characterize the hidden subgroups of S_n that can be distinguished from identity with weak Quantum Fourier Sampling, showing that these are exactly the subgroups with bounded minimal degree. This implies that the weak standard method for S_n has no advantage whatsoever over classical exhaustive search.
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined from a quantum state y uniformly supported on a left coset of H. These hidden subgroup problems are then solved by Fourier sampling: the quantum Fourier transform of y is computed and measured. When the underlying group is non-Abelian, 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 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 of semidirect products of Z_p by Z_q, where q divides (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. We extend this to an information-theoretic solution for the hidden subgroup problem over semidirect products of Z_p by \Z_q where q divides (p-1) and, in particular, the Affine groups A_p. Finally, we prove a closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem in general groups. Specifically, we show that the hidden subgroup problem in the symmetric group cannot be efficiently solved by strong Fourier sampling. Indeed we prove the stronger statement that no measurement of a single coset state can reveal more than an exponentially small amount of information about the identity of the hidden subgroup, in the special case relevant to the graph isomorphism problem.
The Hidden Subgroup Problem (HSP) provides the fundamental framework for most quantum algorithms. Until very recently, all known problems where quantum computation provides a super-polynomial speedup over classical algorithms have been variants of the HSP for particular abelian groups. Examples include factoring integers and computing the discrete log, for which Shor found efficient quantum algorithms. The algorithm for these problems may be viewed as consisting of the main HSP solution plus an ad hoc method of dealing with the particular variant. In this dissertation, we give a systematic way of dealing with all these variants. The key component of our solution is a new theorem about the robustness of Fourier sampling. The purpose of this theorem is to better understand the structure underlying existing algorithms as well as to provide an algorithmic tool for the construction of future quantum algorithms. In addition, we also derive a new algorithm for computing the quantum Fourier transform which is asymptotically faster than any previously known algorithm. By contrast, the nonabelian HSP is wide open. It includes as a special case the longstanding open question of graph isomorphism, where the group is the symmetric group, S n . It is natural to carry over the abelian HSP algorithm to the nonabelian case. We show that in the case that the hidden subgroup is normal, this algorithm succeeds in reconstructing the subgroup in polynomial time. On the other hand, we give evidence that this algorithm is inadequate to even distinguish a trivial subgroup from an involution in t...