The Hidden Subgroup Problem

Abstract

We review the Hidden Subgroup Problem (HSP), one of the most prominent topic in quantum computing. We start with some "historical" quantum algorithms which are exponentially faster than their classical counterparts, including the famous Shor's factoring algorithm. Then, we define HSP and show how the previous algorithms can be interpreted as solutions to this problem.

In a second part, we describe in detail the "standard method". We recall the solution to the abelian case as well as some representation theory background that allows to use Fourier Transform over Finite Groups. We also define Fourier Sampling and mention how the weak version extends the abelian case to find normal hidden subgroups and solve the dedekindian HSP.

In a third part, we discuss all the results known so far for the cases of the Dihedral and Symmetric groups, which are expected to provide new efficient algorithms. Solving the dihedral HSP in a particular way gives an algorithm for $\text{poly}\left(n\right)$-uniqueSVP while a solution to the symmetric HSP gives an algorithm for the graph isomorphism problem.

Finally, we conclude our study with the general HSP. We make some proposals for a general approach and discuss the solutions and techniques known so far. Next, we indicate how HSP relates to various efficient algorithms. We also give an overview of miscellaneous variants and extensions to the hidden subgroup problem that have been proposed.

In addition to gathering in a single document an introduction to the Hidden Subgroup problem as well as an overview of the state-of-the-art for this research topic, we also bring some contributions:

• We provide a detailed and corrected computation of the fact that, in the Strong Fourier Sampling, measuring the row yields no information. In the sketchy proof of Grigni et al., a family of vectors was claimed to be orthonormal whereas it is only orthogonal.
• In appendix B, we compute the exact expression of Strong Fourier Sampling over the dihedral group. When the hidden subgroup is reduced to $\{(0,0),\left(d,1\right)\}$, it has already been mentioned that Strong Fourier Sampling over $D_N$ is similar to using the Quantum Fourier Transform over ${\mathbb{Z}}_N\times {\mathbb{Z}}_2$ and hence a particular case of the dihedral coset problem. For a general hidden subgroup, we prove that the expression of the Strong Fourier Sampling is the same as if we were directly working in the quotient group $\raisebox{1ex}{$D_N$}\!\left/ \!\raisebox{-1ex}{$\left(H\cap \left({\mathbb{Z}}_N\times \left\{0\right\}\right)\right)$}\right.$.
• In appendix G, we propose an entirely new approach to try to find the slope $d$ of the dihedral HSP. Rather than using coset sampling, we consider uniform superpositions over large subsets of $f\left(D_N\right)$. In particular, we can solve the case $N=2^n$ if we have an efficient process to create for $b=0,1$ the states $\frac{1}{\sqrt{2^{n-1}}}\sum _{i=0}^{2^{n-1}-1}\mid f(2i,b)⟩$.
• We give more detail on the relation between HSP and lattice problems. In particular, we show that if Regev's algorithm is based on a solution to the dihedral coset problem with a query complexity $O\left(n^D\right)$ then it gives a solution to $\Theta \left(n^{\frac{1}{2}+2D}\right)$-uniqueSVP. We indicate that the relation still holds if we use a solution over $D_{2^n}$ or $\mathrm{Dih}\left({\mathbb{Z}}_{2^{4n}}^n\right)={\mathbb{Z}}_{2^{4n}}^n⋊{\mathbb{Z}}_2$ using a "recursive DCP algorithm". However, we also provide an overview of lattice-based problems in appendix E and warn that Regev's algorithm would only have small impact on lattice-based cryptosystems. Hence, we propose to consider also HSP algorithms for stronger lattice problems.
• In appendix D, we give a reduction of Monotone 1-in-3 3SAT to GapCVP^∞ where one step uses the abelian HSP algorithm to find the kernel of group homomorphism. Although the quantum part is not actually needed here, this provides another example where a hidden subgroup problem can be used.
• In appendix F, we give an alternative algorithm for the cyclic and abelian hidden subgroup problems, based on a change of the underlying group. Even if it does not generalize, it is a good example of subgroup reduction.
• We present a general approach to the Hidden Subgroup Problem and show that in theory, we can solve it if we have a solution to HSP over simple groups and a way to build efficient oracles for some reduction techniques. We also propose iterative subgroup and quotient reductions: using a maximal supergroup of $H$ for the former and the normal subgroup obtained by Weak Fourier Sampling for the latter. Maximal subgroup reduction is a possible approach for HSP over simple groups.
• We indicate how to reduce the rigid graph isomorphism problem to HSP over the alternating group $A_n$, which is simple for $n>4$.
• We notice how the Hidden Polynomial Problem is a natural extension of the abelian HSP over $G=F_q^m$, when the subgroup $H$ is promised to be a hyperplane.