We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses k = log 2 |G | registers, and each of the 2 k subsets of the registers contributes some information. While this does not, in general, yield an efficient algorithm, it generalizes the relationship between Subset Sum and the HSP in the dihedral group, and sheds some light on how quantum algorithms for Graph Isomorphism might work. 1
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses
k=log2∣G∣ registers, and each of the
2k subsets of the registers contributes some information. While this does not, in general, yield an efficient algorithm, it generalizes the relationship between Subset Sum and the HSP in the dihedral group, and sheds some light on how quantum algorithms for Graph Isomorphism might work.
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.
We establish a general method for proving bounds on the information that can be extracted via arbitrary entangled measurements on tensor products of hidden subgroup coset states. When applied to the symmetric group, the method yields an Omega(n log n) lower bound on the number of coset states over which we must perform an entangled measurement in order to obtain non-negligible information about a hidden involution. These results are tight to within a multiplicative constant and apply, in particular, to the case relevant for the Graph Isomorphism problem. Part of our proof was obtained after learning from Hallgren, Roetteler, and Sen that they had obtained similar results.
The hidden subgroup problem (HSP) unifies many of the best-known quantum speed-ups. For abelian groups it is solved efficiently by weak Fourier sampling, but for non-abelian groups, which include the cases relevant to graph isomorphism and lattice-based cryptography, the right measurement basis is crucial and often unknown. We experimentally study the HSP over the
q-hedral groups
Zq⋉Zp, which interpolate between the dihedral and affine groups and mark a boundary between instances that are efficiently solvable and those that are only information-theoretically solvable. On the IonQ Forte trapped-ion quantum computer, with
p≤7, we implement weak Fourier sampling, strong Fourier sampling in an adapted basis, strong Fourier sampling of adjacent pairs, and forgetful abelian sampling. We demonstrate that the theoretical predictions of Moore, Rockmore, Russell and Schulman survive on a noisy device: weak sampling reveals nothing about the hidden subgroup, the adapted basis succeeds for large
q, adjacent pairs succeed for small
q, and forgetful sampling saturates below unit success. For
p=7,
q=6, the hardware exceeds the success probability of an exhaustively optimised classical algorithm for up to three oracle queries.
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states.We show that the optimal measurement for solving this problem is the so-called pretty good measurement.We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density ν = k/ log 2 N , where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group.In particular, for ν < 1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N , while for ν > 1 the optimal measurement identifies the hidden subgroup with a probability of order unity.Thus the dihedral group provides an example of a group G for which Ω(log |G|) hidden subgroup states are necessary to solve the hidden subgroup problem.We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold.Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems.In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
We give an overview of the Hidden Subgroup Problem (HSP) as of July 2010, including new results discovered since the survey of arXiv:quant-ph/0411037v1. We recall how the problem provides a framework for efficient quantum algorithms and present the standard methods based on coset sampling. We study the Dihedral and Symmetric HSPs and how they relate to hard problems on lattices and graphs. Finally, we conclude with the known solutions and techniques, describe connections with efficient algorithms as well as miscellaneous variants of HSP. We also bring various contributions to the topic. We show that in theory, we can solve HSP over a given group inductively: the base case is solving HSP over its simple factor groups and the inductive step is building efficient oracles over a normal subgroup N and over the factor group G/N. We apply this analysis to the Dedekindian HSP to get an alternative abelian HSP algorithm based on a change of the underlying group. We also propose a quotient reduction by the normal group obtained via Weak Fourier Sampling. We compute the exact expression of Strong Fourier Sampling over the dihedral group, showing how the previous reduction is natural and matches the standard one. We also give a reduction of rigid graph isomorphism problem to HSP over the alternating group. For this group and other simple groups, we propose maximal subgroup reduction as a possible approach. We also analyse Regev's algorithm for the poly(n)-uniqueSVP, prove how the degree of the polynomial is related to the oracle complexity used and we suggest several variants.