The Hidden Subgroup Problem is one of the most prominent topic in quantum computing. Most quantum algorithms running exponentially faster than their classical counterparts fall into this framework. It is expected that finding more solutions to Hidden Subgroup Problems will provide new efficient quantum algorithms.
The first example of a black-box algorithm of this kind was given by Simon [Sim1994]. Classical algorithms can not give the right answer to that black-box problem unless they use an exponential number of oracle calls. This result strengthened the earlier Deutsch–Jozsa algorithm, which is only exponentially more efficient than deterministic classical algorithm. Despite its theoretical importance for demonstrating the power of quantum computer, Simon's algorithm does not lead to practical applications.
However, shortly after Simon published his algorithm, Shor [Sho1995] extended it to find periods of functions over and . He used these period finding algorithms as key steps to solve two difficult problems: factoring integer and computing discrete logarithms. The hardness of both problems is the assumption on which some cryptographic systems such that the ubiquitous RSA system are based. Hence Shor's algorithms had a strong impact since they proved how quantum computers can break cryptographic systems and it has been one of the great success of quantum computing.
Simon's problem and Shor's algorithms can be better understood in the framework of the Hidden Subgroup Problem. We work on a group and try to find an unknown subgroup using calls to a function . This function is constant on cosets of and takes different values on distinct cosets. Ettinger, Høyer and Knill proved that the subgroup can always be determined using only calls to the oracle but the whole procedure is not necessarily efficient [EttHøyKni1999].
We recall the "historical" results as well as the definition of the Hidden Subgroup Problem in the first part of this report. Although they are well known by researchers working on this topic, they remain a good introduction and motivate the subsequent work.
Once the framework of the Hidden Subgroup Problem set, the special case of abelian group was addressed. Indeed, the algorithms given by Simon and Shor work on abelian groups and the main ingredients such that entanglement over a coset and Quantum Fourier Transform could easily be extended to solve the abelian Hidden Subgroup Problem. The algorithm requires the knowledge of a decomposition but if the group is given in a black box form, we can still determine that decomposition. Because the algorithm is fundamental, we start the second part of this report by recalling how the abelian HSP algorithm works. We also sketch the idea of Cheung and Mosca [CheMos2001] to get the decomposition for a black-box group.
The success of the Fourier Sampling to solve the abelian HSP naturally made the researchers study its generalization over non-abelian groups. This is quite technical, so we take care to define precisely Quantum Fourier Transform and Fourier Sampling. We study how they apply to non-abelian HSP in the remainder of the second part of this report.
We first extract the essential points from the reference book on group representation theory by Serre [Ser1971] to show that it is always possible to define a general Quantum Fourier Transform over finite groups as a unitary operation. We indicate how it extends the classical Quantum Fourier Transform used for abelian groups. In the non-abelian case, it turns out that each choice of basis for the set of irreducible representations gives rise to a specific Quantum Fourier Transform. We use the Schur's lemma to show that they are all described modulo basis changes in the space of each irreducible representation.
Next, we turn our attention to the Fourier Sampling over finite groups using the studies of [HalRusTa-2000] and [GriSchVaz2000]. It is the occasion to recall the standard method of coset sampling: we gather information on the hidden subgroup from coset states i.e. uniform superposition over a random coset of . Then, we apply several Fourier Samplings to these cosets states: a Quantum Fourier Transform followed by a measurement of an irreducible representation. We define the Weak and Strong versions and recall classical expressions on distribution probabilities. In particular, we give a detailed proof of the fact that measuring the row is not relevant for Strong Fourier Sampling.
We then see how the Weak Fourier Sampling is enough to solve the Dedekindian Hidden Subgroup Problem i.e. for groups that have only normal subgroups. In the new framework, the algorithm of the abelian case can be seen as computing the hidden subgroup as the intersection of the kernels of the representations measured by Fourier Sampling. Independently, [HalRusTa-2000] and [GriSchVaz2000] showed that this technique still works when the hidden subgroup is normal, thus solving the dedekindian in theory. [HalRusTa-2000] contains an explicit algorithm for the class of hamiltonian groups which are the only non-abelian dedekindian groups. We also mention briefly more results of [GriSchVaz2000] and [Gav2004] such that extensions to groups that are in some sense not too far from the dedekindian case as well as a black box result to find normal subgroups.
The third part of this report is dedicated to the two most important open non-abelian HSPs: those over the dihedral and symmetric groups. Regev showed that a solution to the Hidden Subgroup Problem over the dihedral group using coset samplings on a particular reduced case would provide an efficient algorithm for the -uniqueSVP [Reg2004]. uniqueSVP is an instance of lattice problems, which are involved in many tasks believed to be computationally hard. More specifically, some cryptographic systems are based on lattice problems and some of them use the -uniqueSVP. A solution to the Hidden Subgroup Problem over the symmetric group gives a polynomial algorithm to determine whether two given graphs are isomorphic, one of the very rare problems whose exact complexity has remained unknown for many decades.
The dihedral Hidden Subgroup Problem was first considered by Ettinger and Høyer as a first study of the non-abelian case [EttHøy1998]. They gave an interesting reduction of the problem to the case where the hidden subgroup is and showed that we can determine with efficient query and measurement but exponential post-processing. We describe the structure of the dihedral group and explain the techniques of Ettinger and Høyer. We also discuss whether the algorithms of the previous section work. In particular, we give a very detailed description of Fourier Sampling over the dihedral group in appendix B and present some attempts to solve DHSP using this method in appendix C. We introduce the Dihedral Coset Problem which is essentially asking whether we can solve the dihedral HSP using a black box that outputs coset states. This problem encapsulates all the previous approaches. However, we propose a totally new method in appendix G.
In another section, we study the results obtained from this dihedral coset black box. In [Kup2003], Kuperberg gave a subexponential time algorithm to determine the parity of from a dihedral coset black box, using a new combine-and-measure technique. This algorithm can be easily extended to get a solution to the dihedral HSP with subexponential time. Actually, Kuperberg's algorithm uses exponential space but Regev gave a modification that makes the space requirement polynomial [Reg2004]. More generally, Bacon, Childs and van Dam used tools from quantum-information theory to characterize the measurement on outputs of the black box that gives the optimal information [BacChiDam2005]. They showed that must be at least linear even for determining the parity of as in Kuperberg's algorithm. They also demonstrated a relation between the implementation of the optimal measurement and the subset sum problem. Actually, Regev had already shown such a relation in [Reg2003].
Next we look more carefully to Regev's algorithm [Reg2003] that establishes a connection between the polynomial uniqueSVP and a solution to the dihedral coset problem. We show how the degree of the polynomial complexity of a solution to the dihedral coset problem is related to the degree of the approximation in the uniqueSVP. We notice that mutatis mutandis his algorithm can be applied using more HSP problems over the family of generalized dihedral groups. Similarly, we indicate that the algorithm still holds for some kinds of recursive dihedral coset problem as in the case of Kuperberg's algorithm. We sum up in appendix E the overview of [MicReg2008] and notice that the problem considered is however not of major importance. We suggest some research directions to investigate.
Then we turn our attention to the case of the symmetric group. We recall the definition of the graph isomorphism problem as well as related problems. We describe the straightforward reduction of the equivalent graph automorphism problem to the symmetric hidden subgroup problem, or more specifically to the case where we want to determine whether the hidden subgroup is trivial or not. We also talk about another reduction for the case of rigid graphs given in [MooRusSch2005]: the underlying group is and the hidden subgroup . Moreover, we prove that the rigid graph isomorphism problem can actually be set in the reduced case of the simple group . Unfortunately, even these simpler cases have remained unsolved. We recall the negative results on the symmetric group and suggest to split the problem in more separate cases.
In a final part, we study the general hidden subgroup problem. We recall the two fundamental theorems describing how finite groups are built from simple groups using composition series. We state conditions to solve the general HSP: find a way to solve the HSP over simple group and to build efficient oracles when breaking down the group. For the second conditions, we isolate two particular reduction methods: subgroup reduction and quotient reduction. We propose iterative quotient reduction to make the hidden subgroup not contain any non-trivial normal subgroup. We also suggest iterative maximal subgroup reduction as a possible way to solve the HSP over the simple groups. We sum up our ideas in a general schema for a possible HSP algorithm. We notice how these ideas relate to an alternative abelian HSP algorithm proposed in appendix F and to dihedral and symmetric HSP. We explain how the classical attempts for dihedral HSP are using quotient and subgroup reductions. For the symmetric HSP, the reductions give two difficult problems: either solving HSP over the large simple group or building a oracle over from the big initial oracle over .
In the next section, we review the solutions and techniques obtained for non-abelian groups. We recall the Fourier Sampling techniques as well as all the methods that have been discovered in order to find a solution to the dihedral HSP. We mention other techniques relying on the blackbox paradigm. We give an overview of efficient HSP algorithms based on these methods. They can essentially be classified into three groups: the extensions to the Dedekindian HSP which apply to groups with a large amount of normal subgroups, the semi-direct products of two abelian groups which are broken down into the abelian groups and with respect to the description of the previous section and another category of groups whose normal series structure is simple enough to apply blackbox techniques. In some sense, they are all close to the abelian case. We mention a partial result for an exception which includes the simple group , namely finding 1-point stabilizer of some Lie groups.
The following section is devoted to relation between HSP and efficient algorithms with concrete applications. We recall the results for dihedral and symmetric HSP. We mention Hallgren's generalization to infinite groups which allowed him to solve Pell's equation and other number fields problems. We also mention more relationship between HSP an cryptography. Considering that the general HSPs are actually difficult, Moore, Russell, Vazirani constructed a one-way function which is as hard to invert as the graph isomorphism problem. [Dam1988] contains a proposal for a hard problem with application to cryptography: Given successive evaluations of the Legendre symbol predict the next value . We mention how a weaker problem can be set in the HSP framework and has been solved [DamHalIp2002]. The authors say that the solution to this weaker problem allows attacks to some cryptosystems, already broken by Shor's algorithm though. We also discuss the comparaison given in [LomKau2006] between Shor's algorithm and Grover's algorithm. We compare their method with the algorithms for the 1-point stabilizer given in [DenMooRus2008] and wonder whether they can be interpreted as exponentially fast solutions to some concrete search problems.
We conclude our study with some variants and extensions to the hidden subgroup problem which are also expected to yield new efficient quantum algorithms. We mention the generalization to hypergroups and infinite groups. Other extensions include the Hidden Symmetries Problem and the Hidden Covering Space Problem. We describe the quite popular variants of the Hidden Shift Problem which is related to the dihedral and symmetric HSP, as well as its generalizations the Generalized Hidden Shift Problem and the Hidden Coset Problem. We mention three problems introduced in [FriEtAl2002] to solve some instances of HSP: Hidden Stabilizer Problem, Orbit Coset Problem and Orbit Superposition Problem. We also talk about some decision/search versions of hidden subgroup problems. Next, we show how finding hyperplane subgroups of the vector space naturally generalizes to the Hidden Polynomial Problem. Finally, we discuss the category of Hidden Shifted Subset Problems.
