The Hidden Subgroup Problem
20090566
Supervisor: Ivan Damgård
July 2010
Det Naturvidenskabelige Fakultet
Aarhus Universitet
Danmark
d'Informatique pour l'Industrie et l'Entreprise
Evry
France
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 stateoftheart 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}^{n1}}}\sum _{i=0}^{{2}^{n1}1}\mid f(2i,b)\u27e9$.
 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}\u22ca{\mathbb{Z}}_{2}$ using a "recursive DCP algorithm". However, we also provide an overview of latticebased problems in appendix E and warn that Regev's algorithm would only have small impact on latticebased cryptosystems. Hence, we propose to consider also HSP algorithms for stronger lattice problems.
 In appendix D, we give a reduction of Monotone 1in3 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.
Table of Contents
 Abstract ii
 Table of Contents iv
 Acknowledgments vi

Introduction1

Prerequisites 5

Efficient Quantum Algorithms and The Hidden Subgroup Problem7

The "Standard Method" for The Hidden Subgroup Problem15

The Dihedral and Symmetric Hidden Subgroup Problems28

The General Hidden Subgroup Problem41

Conclusion53

Appendix54

Appendix A: Table of Hidden Subgroup Problems54

Appendix B: Strong Fourier Sampling and the DHSP61

Appendix C: Attempts to solve DHSP by Fourier Sampling70

Appendix D: Reduction of Monotone 1in3 3SAT73

Appendix E: Table of Latticebased Cryptosystems78

Appendix F: Variant for the Abelian HSP algorithm80

Appendix G: Attempts to solve DHSP by superposition of oracle values83

Appendix A: Table of Hidden Subgroup Problems

Bibliography88
Acknowledgments
Jeg vil gerne sige tak til Ivan Damgård, for at have lært mig Quantum Information Processing på først semester og have accepteret at blive min vejleder. Mange tak for at have fulgt mit arbejde og have gjort alt for at jeg kunne have en mundtlig eksamen.
Jeg vil også give tak til alle folk, som har givet mig til at have et dejligt ophold i Danmark. Specialt tak til Mikkel Gravgaard, for sin hjælp med administrative ting da jeg kom. Mange tak til alle beboere på Skejbygårdkollegiet for alle hyggelige aftener samt sjove fodboldkampe.
Je tiens aussi à exprimer ma gratitude envers toutes les personnes de l'ENSIIE qui m'ont permis de passer ma troisième année à Århus dans les meilleurs conditions.
Enfin, je souhaite remercier ma famille pour son soutien tout le long de mon séjour au Danemark. Merci notamment à mon frère et ma sœur pour être venus me rendre visite quelques jours à Århus.