We show that measuring any two low rank quantum states in a random orthonormal basis gives, with high probability, two probability distributions having total variation distance at least a universal constant times the Frobenius distance between the two states. This implies that for any finite ensemble of quantum states there is a single POVM that distinguishes between every pair of states from the ensemble by at least a constant times their Frobenius distance; in fact, with high probability a random POVM, under a suitable definition of randomness, suffices. There are examples of ensembles with constant pairwise trace distance where a single POVM cannot distinguish pairs of states by much better than their Frobenius distance, including the important ensemble of coset states of hidden subgroups of the symmetric group (Moore at al., 2005). We next consider the random Fourier method for the hidden subgroup problem (HSP) which consists of Fourier sampling the coset state of the hidden subgroup using random orthonormal bases for the group representations. In cases where every representation of the group has polynomially bounded rank when averaged over the hidden subgroup, the random Fourier method gives a POVM for the HSP operating on one coset state at a time and using totally a polynomial number of coset states. In particular, we get such POVMs whenever the group and the hidden subgroup form a Gel'fand pair, e.g., Abelian, dihedral and Heisenberg groups. This gives a positive counterpart to earlier negative results about random Fourier sampling when the above rank is exponentially large (Grigni et al., 2004), which happens for example in the HSP in the symmetric group. The drawback of random POVMs is that they are not efficient to implement, since measuring in a random basis takes exponential time as can be seen by a counting argument. This leads us to the open question of efficiently implementable pseudorandom measurement bases
We show that measuring any two low rank quantum states in a random orthonormal basis gives, with high probability, two probability distributions having total variation distance at least a universal constant times the Frobenius distance between the two states. This implies that for any finite ensemble of quantum states there is a single POVM that distinguishes between every pair of states from the ensemble by at least a constant times their Frobenius distance; in fact, with high probability a random POVM, under a suitable definition of randomness, suffices. There are examples of ensembles with constant pairwise trace distance where a single POVM cannot distinguish pairs of states by much better than their Frobenius distance, including the important ensemble of coset states of hidden subgroups of the symmetric group (Moore at al., 2005). We next consider the random Fourier method for the hidden subgroup problem (HSP) which consists of Fourier sampling the coset state of the hidden subgroup using random orthonormal bases for the group representations. In cases where every representation of the group has polynomially bounded rank when averaged over the hidden subgroup, the random Fourier method gives a POVM for the HSP operating on one coset state at a time and using totally a polynomial number of coset states. In particular, we get such POVMs whenever the group and the hidden subgroup form a Gel'fand pair, e.g., Abelian, dihedral and Heisenberg groups. This gives a positive counterpart to earlier negative results about random Fourier sampling when the above rank is exponentially large (Grigni et al., 2004), which happens for example in the HSP in the symmetric group. The drawback of random POVMs is that they are not efficient to implement, since measuring in a random basis takes exponential time as can be seen by a counting argument. This leads us to the open question of efficiently implementable pseudorandom measurement bases
Part I of this paper showed that the hidden subgroup problem over the symmetric group--including the special case relevant to Graph Isomorphism--cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. In this paper, we extend these results to entangled measurements. Specifically, we show that the hidden subgroup problem on the symmetric group cannot be solved by any POVM applied to pairs of coset states. In particular, these hidden subgroups cannot be determined by any polynomial number of one- or two-register experiments on coset states.
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.
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.
Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.
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...