The General Hidden Subgroup Problem

General approach to the Hidden Subgroup Problem

In this section, we recall the two fundamental theorems of group theory describing all finite groups. We show how they can be used to solve the general HSP under certain conditions. We study the special cases of dedekindian, dihedral and symmetric groups in that framework.

A group $G$ is said to be simple, if it contains no other normal subgroups than ${1}$ and $G$ . Finite simple groups are the "building blocks" for all finite groups and their classification are given by a theorem of group theory. More precisely, the theorem states that the possibilities for a finite simple group are:

Cyclic groups $ℤ_{p}$ for $p$ prime.
Alternating groups $A_{n}$ for $n \geq 5$ .
Simple groups of Lie type.
26 sporadic simple groups.

For an arbitrary finite group $G$ , a composition series is a sequence of subgroups of $G$

${1} = H_{0} ⊲ H_{1} ⊲ H_{2} ⊲ \dots ⊲ H_{n} = G$

such that each $H_{i}$ is a maximal normal subgroup of $H_{i + 1}$ . The integer $n$ is called the composition length, and is clearly $O (\log ∣ G ∣)$ . Each $\frac{H_{i + 1}}{H_{i}}$ is called a composition factor and is by definition a simple group. Any finite group has a composition series: informally, we can start with ${1} ⊲ G$ and insert normal subgroup $H_{i}$ until we get a composition series. Moreover, the Jordan–Hölder theorem says that all the composition series of a group are equivalent i.e. they all have the same length and are made of the same composition factors (up to isomorphism and permutation).

The consequence of these two theorems is that we know how any finite group $G$ is built. Let's see how they can be used to solve the general HSP. Suppose $H$ is a subgroup hidden by $f$ and $N ⊲ G$ a normal subgroup. Then $\bar{H} = {h N, h \in H}$ is a subgroup of $\frac{G}{N}$ and $H \cap N$ a subgroup of $N$ . We can consider the HSPs over $\frac{G}{N}$ and $H \cap N$ respectively and get two sets of generator $\bar{H} = ⟨ h_{i} N ⟩$ and $H \cap N = ⟨ x_{i} ⟩$ . Finally we obtain a set of generators $⟨ h_{i}, x_{j} ⟩ = \bar{H} H \cap N = H$ for the hidden subgroup. Of course, this quotient reduction is only relevant if ${1} ⊈ N ⊊ G$ i.e. is only possible if the group is not simple. Moreover, if $n_{1}, n_{2}$ are the length of two composition series for $\frac{G}{H}$ and $H \cap N$ we have $n = n_{1} + n_{2}$ . Hence if we repeat the previous quotient reduction to these subgroups we will reach simple groups in $O (\log ∣ G ∣)$ steps. Note that the Jordan–Hölder theorem essentially says that there are no privileged choice for the normal subgroup $N$ at each step. Finally, we have the following theorem:

(solution to the general HSP)

We have a solution to the general HSP if

We have an efficient algorithm for HSP over simple groups.
For any hidden subgroup problem $G, H, f$ over a non-simple group and a normal subgroup ${1} ⊈ N ⊊ G$ , we have an efficient way to build polynomial-time oracles $\bar{f}$ and $f_{∣ H \cap N}$ over $\frac{G}{N}$ and $N$ hiding the subgroups $\bar{H}$ and $H \cap N$ .

Thus, one research direction is to try to solve HSP over simple groups. We can also restrict in a first time to solvable groups (i.e. such that the composition factors are abelian, or more precisely cyclic groups of prime order) and use the HSP algorithm that we already have for the composition factors.

The second research direction is to find reduction methods. We have already seen many times the following subgroup and quotient reduction:

(subgroup reduction, quotient reduction)

Let $G, H, f$ be a HSP problem. We have the following reductions:

Subgroup reduction: Suppose we can find in polynomial time a subgroup $G_{1} \subseteq G$ that contains $H$ and an isomorphism $G_{2} \overset{g}{≅} G_{1}$ such that $g$ has polynomial complexity. The oracle $f \circ g$ over $G_{2}$ hides the group $g^{-1} (H)$ . A solution to HSP over $G_{2}$ gives a set of generators $u_{1}, \dots, u_{n}$ for $g^{-1} (H)$ and so a set of generators $g (u_{1}), \dots, g (u_{n})$ for $H$ .
Moreover, if $G_{1} ⊊ G$ , then $∣ G_{1} ∣ \leq \frac{1}{2} ∣ G ∣$ .
Quotient reduction: Suppose we can find in polynomial time a normal subgroup $H_{1} \subseteq H \subseteq G$ , a set of generators $u_{1}, \dots, u_{n}$ for $H_{1}$ and an isomorphism $G_{2} \overset{g}{≅} \frac{G}{H_{1}}$ such that $g$ has polynomial complexity. The oracles $f \circ g$ hides the group $g^{-1} (\frac{H}{H_{1}})$ . A solution to HSP over $G_{2}$ gives a set of generators $v_{1}, \dots, v_{n}$ for $g^{-1} (\frac{H}{H_{1}})$ and so a set of generators $g (v_{1}), \dots, g (v_{n})$ for $\frac{H}{H_{1}}$ . Then the union of $u_{i}, g (v_{j})$ generates $H$ .
Moreover, if $H_{1} \neq {1}$ then $∣ \frac{G}{H_{1}} ∣ \leq \frac{1}{2} ∣ G ∣$ .

Note that the theorem 6.1 uses a combination of generalized versions of these reduction methods with $N = G_{1} = H_{1}$ and without the constraints $H \subseteq G_{1} = N$ and $N = H_{1} \subseteq H$ . For the subgroup reduction part, the oracle does not need to be changed and will hide the expected group $H \cap N$ instead. However, it is less clear how to build the oracle for the quotient reduction part because two elements $g_{1} {, g}_{2} \in G$ that belong to the same class in $\frac{G}{N}$ may not belong to the same preimage of $f$ . Note that if $H \neq G$ , then it is always included in a maximal subgroup $G_{1}$ and thus subgroup reduction is always possible. This is particularly interesting in the case of the simple group, where quotient reduction is not possible. However, the complete description of maximal groups is only known for some groups.

(iterative maximal subgroup reduction)

We have a solution to HSP over a group $G$ if we have an algorithm to find a maximal subgroup $G_{1}$ containing $H$ , apply subgroup reduction to $G_{1}$ and repeat the operation inductively. We stop when we no longer can find a maximal subgroup i.e. $H = G$ .

Let's consider the groups we have previously studied. First, in the Dedekindian HSP we work on a group whose subgroups are all normal. An algorithm is given in appendix F for the particular case of abelian group, but should also work for hamiltonian ones. The idea is to use Weak Fourier Sampling to get a sequence of subgroups of $G$ containing $H$ that become smaller and smaller. Because all groups are normal, we have a subsequence of a composition series: ${1} ⊲ H ⊲ G_{m} ⊲ \dots ⊲ G_{0} = G$

In that case, $\frac{H}{G_{k}}$ is the trivial group and $H \cap G_{k} = G_{k}$ , so the algorithm of theorem 6.1 is really only using subgroup reduction. The abelian algorithm of appendix F also shows the importance of "nice" description of groups, such that the one provided by black box groups. In our definition 3.3 of the hidden subgroup problem, we say that we want to determine the hidden subgroup $H$ and definition 3.5 asks for a set of generating elements. However in the abelian case, to be able to iterate the reductions we use at each step a direct decomposition $G_{k} = \oplus_{i = 1}^{d_{k + 1}} ⟨ a_{i}^{k + 1} ⟩$ so that we can have the polynomial-time isomorphism mentioned in definition 6.2 and thus efficient oracles on the new groups.

Another interesting case is the reduction we have made so far for the dihedral group. The possible composition series are given in figure 6.1, where the dots correspond to composition series of the isomorphic groups indicated.

As usual, we consider the case $H = H_{r, d}$ which contains the normal subgroup $H_{r}$ . Because $H_{r} = H_{1} \cap H$ , we can apply a subgroup reduction to determine $r$ : we move in $H_{1}$ which is isomorphic to $ℤ_{N}$ and apply a cyclic HSP algorithm. Since we now have a normal subgroup included in $H$ , we can use a quotient reduction. We have $\frac{G}{H_{r}} ≅ \frac{D_{N}}{ℤ_{\frac{N}{r}}} ≅ D_{r}$ so we still have a similar composition series diagram and we now assume $r = N$ . The hidden subgroup becomes $H_{N, d}$ and we want to determine $d$ . It easy to see that none of the candidates for quotient reduction (i.e. normal subgroups of $G$ included in the hidden subgroup) provide any further simplification. As a consequence, we are turning our attention to subgroup reduction. The possibilities are $H_{a, b}$ where $a$ is a divisor of $N$ and $d \equiv b mod (a)$ . In that case, we have $H_{a, b} ≅ D_{\frac{N}{a}}$ and the new hidden subgroup is generated by a slope $(q, 1)$ where $q$ is the quotient of the division of $d$ by $a$ . We repeat subgroup reduction until we have determined entirely $d$ and again we need only $O (\log ∣ G ∣)$ reduction steps. Note that variations of this kind are proposed in Kuperberg's paper [Kup2003]. The key step for solving DHSP is thus to determine the remainder of $d$ modulo a divisor $a$ of $N$ . For $N = 2^{n}$ the procedure will be to determine the bits of $d$ , from the least to the most significant ones. Finally, we recover the techniques that have been used so far. Note that the dihedral is solvable, so we already have a solution for the simple groups involved. Hence a solution to DHSP will either be an algorithm to find the parity of $d$ (or any other remainder of $d$ ) or by new reduction techniques.

There is an alternative way to see the first quotient reduction by $H_{r}$ . Using theorem 9.9 one can see that, except in the degenerated cases $H = H_{2, d}$ , the intersection of the kernels of the representations measured by a Weak Fourier Sampling over the dihedral group is exactly $H_{r}$ . Actually, we know that in general the Weak Fourier Sampling gives the largest normal subgroup of $G$ which is included in $H$ . Hence a general method is to apply Weak Fourier Sampling to find that subgroup and then use a quotient reduction. In the quotient group, we can still repeat this procedure. After $O (\log ∣ G ∣)$ reductions of this kind, we will not be able to reduce the underlying group any further: the largest hidden subgroup of $H$ normal in $G$ is the trivial group ${1}$ . If this group is also $H$ , then we can determine the original hidden subgroup. Otherwise, $H$ is not necessarily simple and we need to use subgroup reduction or other methods as in the case of the dihedral group. We have:

(iterative quotient reduction)

A repetition of quotient reduction using the largest normal subgroup included in the hidden subgroup leads to a hidden subgroup problem where the reduced hidden subgroup $H$ does not contain any non-trivial normal subgroup. If the reduced hidden subgroup is trivial then we can solve HSP using this method.

Finally, let's consider the symmetric group $S_{n}$ . We may discard small values of $n$ and assume $n \geq 5$ . In that case, ${Id} ⊲ A_{n} ⊲ S_{n}$ is a composition series and in particular $S_{n}$ is not solvable. Moreover, consider the case of our reduction of rigid graph isomorphism problem in $S_{2 n}$ , where $H$ is trivial or $H = ⟨ σ ⟩$ for some involution $σ = (φ, φ^{- 1}) s_{n}$ with signature $ε (σ) = {(- 1)}^{n}$ . If we split the HSP problem between $\frac{S_{2 n}}{A_{2 n}} ≅ ℤ_{2}$ and $A_{2 n}$ , we have two cases:

$n$ is even, so $H \cap A_{2 n} = H \subseteq A_{2 n}$ and all the information is in $A_{2 n}$ . However, this group is simple so we can not reduce it any further using quotient groups.
$n$ is odd, so $H \cap A_{2 n} = {Id}$ and all the information is in $\frac{S_{2 n}}{A_{2 n}} ≅ ℤ_{2}$ . The HSP is trivial on this group and all the hardness consists in the construction of an oracle.

Actually, we have even seen in the previous section that we can reduce the rigid graph isomorphism problem to the simple group $A_{2 n}$ .

Possible algorithm for the general HSP

Input: The group $G$ the oracle $f$ . Output: The hidden subgroup $H$ .

Use at most $k$ coset measurements (remark 4.10) to determine whether $H = G$ with probability of success at least $1 - 2^{k}$ or $H$ is a proper subgroup of $G$ with certainty. In the former case, return $G$ .
If we have an efficient HSP algorithm over $G$ , execute it and return the subgroup $H$ found.
If $G$ is simple, determine a maximal subgroup $G'$ containing $H$ , and use it to apply subgroup reduction. Call this algorithm recursively and return $H$ .
Apply Weak Fourier Sampling to determine a maximal normal subgroup $H'$ of $G$ included in $H$ . If $H'$ is non-trivial, use it to apply quotient reduction. Call this algorithm recursively and return $H$ .
Otherwise, find a way to reduce the problem by using a normal subgroup ${1} ⊈ N ⊊ G$ , subgroup reduction or any other methods... Call this algorithm recursively and return $H$ .

As a conclusion of this section, we have seen a general approach to the HSP based on solution to the simple HSP and various reduction methods. A possible algorithm is proposed in figure 6.2. For the problems related to the dihedral and symmetric groups, it seems however that all the known reductions have already been used.

Known solutions to the Hidden Subgroup Problem

In this section, we review miscellaneous solutions and techniques obtained for non-abelian groups. The HSP table of appendix A completes this section with a good overview of the state of the art.

The groups for which an efficient algorithm is known are mainly semi-direct products of abelian groups, so we start by recalling the definition. Given two groups $G_{1}, G_{2}$ and an automorphism $φ : G_{2} \to G_{1}$ , the semi-direct product $G_{1} ⋊_{φ} G_{2}$ is the group with the operation

$(a_{1}, b_{1}) (a_{2}, b_{2}) = (a_{1} (φ (b_{2}) (a_{2})), b_{1} b_{2})$

For example, we have seen the dihedral group $D_{N} ≅ ℤ_{N} ⋊_{φ} ℤ_{2}$ where $φ (b) (a) = {(- 1)}^{b} a$ and a subgroup of the symmetric group $S_{n} ≀ ℤ_{2} = (S_{n} \times S_{n}) ⋊_{φ} ℤ_{2}$ where $φ (c) (a, b) = τ^{c} (a, b)$ and $τ$ permutes the two coordinates. The latter is an example of a wreath product $G_{1} ≀ G_{2}$ . Each element $b \in G_{2}$ defines a permutation of the elements of $G_{2}$ by $x \mapsto b x$ . Hence we can identify it with a permutation $σ_{b}$ of $S_{∣ G_{2} ∣}$ . We then define $φ (b) (a_{1}, \dots, a_{∣ G_{2} ∣}) = (a_{σ_{b} (1)}, \dots, a_{σ_{b} (∣ G_{2} ∣)})$ and $G_{1} ≀ G_{2} = {G_{1}}^{∣ G_{2} ∣} ⋊_{φ} G_{2}$ .

The first non-abelian HSP considered was DHSP. Although still unsolved, many methods were introduced, so let's recall them:

enumerating all the subgroups of $G$ : they can all be described by two parameters $d < r$ .
using the abelian Fourier Sampling on abelian subgroups: working on $ℤ_{N} \times {0}$ allows to find $r$ .
using quotient reduction: using the normal subgroup $H_{r}$ yields the standard reduction for DHSP.
applying the abelian Fourier Sampling on the whole group, viewed as a cartesian product: this produces coset states and reduces the problem to DCP.
using group reduction: as we have seen in previous section, determining the remainder of $d$ modulo a divisor $a$ of $N$ is like moving to a subgroup isomorphic to $D_{\frac{N}{a}}$ .
pipeline of coset states: this allows to determine $d$ in subexponential time.
pretty good measurement: we consider the tensor product of $k$ coset states $ρ_{d}^{\otimes k}$ and use the optimal measurement to identify it among an equiprobable repartition of $d \in ℤ_{N}$ . If it is efficiently implementable for some $k > \log (N)$ then we can find $d$ .
superposition of many oracle values: a new approach to determine $d$ proposed in appendix G.

We have presented in details Fourier Sampling based on Fourier Transform over finite groups. It is a natural and elegant extension of the abelian case and was presented as a promising method in the review paper of Lomont [Lom2004]. The non-abelian Fourier Transform has been used as a key element for the Dedekindian HSP [HalRusTa-2000], $ℤ_{2}^{n} ≀ ℤ_{2}$ [RötBet1998], $ℤ_{3} ⋊_{φ} ℤ_{2^{n}}$ [GriSchVaz2000], the affine group $Aff (1, p)$ as well as some particular cases of $q$ -hedral groups [MooEtAl2005]. More recently it has been used to solve the Weyl-Heisenberg group [KroRöt2008] and to find 1-point stabilizer of some finite Lie groups [DenMooRus2008]. However, most efficient non-abelian HSP algorithms currently known do not require it and we know that it would not work for all groups. Again, we recall the methods:

Weak Fourier Sampling to find normal subgroups or more generally the largest normal subgroup of $G$ contained in $H$ . As previously said, it is $H_{r}$ for the dihedral group (except for $H = H_{2, d}$ ) and so it is an alternative way to determine $r$ .
Strong Fourier Sampling. It was proved in [MooEtAl2005] that it helps to solve some HSPs on which the weak version fails.
Weak Fourier Sampling over subgroups. They are used in the extensions proposed in [GriSchVaz2000] and [Gav2004].

The other fundamental methods are given by black box results and we refer to [Lom2004] for a review. Recall that the degree of a group $G$ is defined to be the smallest integer $k > 0$ such that there is a one-to-one homomorphism $φ : G \to S_{k}$ . For example, we have $k \leq ∣ G ∣$ by Cayley's theorem, $k = p$ for a cyclic group $G = ℤ_{p}$ of prime order and more generally $k = \sum_{i = 1}^{m} ∣ A_{i} ∣$ for an abelian group with decomposition $A = A_{1} \times A_{2} \times \dots \times A_{m}$ where each $A_{i}$ is cyclic of prime order. We have seen in previous section that every group has a composition series and we define:

(nu of G)

For any group $G$ , $ν (G) > 0$ is the smallest positive integer bounding the degrees of the nonabelian composition factors.

In particular, if $G$ is solvable all the composition factors are abelian (and even cyclic) so we have $ν (G) = 1$ . In general, we will be interested in groups for which $ν (G) = poly (\log ∣ G ∣)$ . [IvaEtAl2001] contains various interesting algorithms, including:

For a blackbox group with unique encoding, we can find generators of a hidden normal subgroup $N$ in time $ν (\frac{G}{N})$ + input size.
For a blackbox group with unique encoding, we can solve HSP in time the input size + $[G, G]$ .

Actually, an extension of the second point is given in [MooEtAl2005].

Let $G_{1} ⊲ G$ , $\frac{G}{G_{1}} ≅ G_{2}$ . Assume that $G_{1}$ is of size polynomial in $\log ∣ G_{2} ∣$ and that we have an efficient HSP algorithm for $G_{2}$ , then we also have an efficient HSP algorithm for $G$ .

Unfortunately, this construction can not be iterated more than a constant number of times whereas we would like to repeat this a polynomial number of time for the algorithm of figure 6.2. This extension was used in [DenMooRus2008] to solve some particular cases of $Aff (1, p^{m})$ . Note that the particular case of the commutator is $G_{1} = G^{'}$ , $G_{2}$ is the abelianization of $G$ , to which we can apply the abelian HSP and we have $∣ G_{1} ∣ = poly (\log ∣ G ∣) = poly (\log ∣ G_{1} ∣, \log ∣ G_{2} ∣) = poly (\log ∣ G_{2} ∣)$ .

Inui and Le Gall studied the case $ℤ_{p^{n}} ⋊_{φ} ℤ_{q}$ for $p, q$ prime [InuLeG2004] and gave a complete classification. One of the class contains groups isomorphic to $ℤ_{p^{n}} ⋊_{φ} ℤ_{p}$ ( $p^{n} \neq 2^{2}$ and $φ (b) (a) = a {(p^{n - 1} + 1)}^{b}$ ) which they solved using enumeration of subgroups and blackbox techniques. Chi, Kim and Lee [ChiKimLee2006] noted that the algorithm also works for some groups $ℤ_{{2 p}^{n}} ⋊_{φ} ℤ_{p}$ and extended the algorithm to the class $ℤ_{N} ⋊_{φ} ℤ_{p}$ under some conditions. The idea is to use a factorization of $N$ to factor out the group and then apply Inui and Le Gall's algorithm. Using a similar approach, Cosme and Portugal [CosPor2007] solved some HSPs over $ℤ_{N} ⋊_{φ} ℤ_{p^{2}}$ . Inui and Le Gall also proposed a different approach for some cases of $ℤ_{p^{m}}^{n} ⋊_{φ} ℤ_{p}$ , based on blackbox techniques [InuLeG2004].

A general proposal for the semi-direct products $A ⋊_{φ} ℤ_{p}$ for some abelian group $A$ and $p$ prime is made in [BacChiDam2005bis]. The first step is similar to the reduction of the dihedral HSP: you use the abelian HSP algorithm over $A$ to find $H_{1} = H \cap (A \times {0})$ and use a "quotient reduction" ( $H_{1}$ may not be normal, but they find a way to workaround that issue). This reduces the problem to a semi-direct product $A_{2} ⋊_{φ} ℤ_{N}$ with $A_{2}$ a subgroup of $A$ . The hidden subgroup is either trivial or the subgroup of size $N$ generated by $(d, 1)$ for some $d \in A_{2}$ . Next, we use the pretty good measurement with a product of $m$ coset states and reduce the problem to finding equations of a system with $m$ unknowns and some parameters uniformly chosen at random. The authors called it the matrix sum problem and solved it for various groups $A$ . In particular, they obtained efficient HSP for $G = ℤ_{p}^{k} ⋊_{φ} ℤ_{p}$ ( $p$ prime, $k$ constant) and $ℤ_{N} ⋊_{φ} ℤ_{q}$ ( $\frac{N}{q} = poly (\log N)$ and $q$ prime).

More blackbox techniques have also been developed. Using the hidden shift problem, the HSP over some semi-direct products $ℤ_{p^{k}}^{n} ⋊_{φ} ℤ_{2}$ was solved in [FriEtAl2002]. They also introduced orbit coset and orbit superposition problems and use it to solve HSP over some solvable groups. More precisely, they defined:

(smoothly solvable)

An abelian group is smoothly solvable if it can be decomposed into the direct product of a subgroup of bounded exponent and a subgroup of polylogarithmic size. A solvable group is smoothly solvable if its derived series is of bounded length and has smoothly abelian factor groups.

They obtained:

HSP can be solved in solvable groups having smoothly solvable commutator subgroups

Ivanyos, Sanselme, Santha solved HSP over extraspecial groups [IvaSanSan2007] and later extended their result to nil-2 groups [IvaSanSan2007bis] i.e. such that $[[G, G], G] = {1}$ . They first used the concept of hiding procedure defined in [FriEtAl2002] which generalizes the hiding oracle $f$ :

hiding procedure for a subgroup $H$ of $G$ : for every $g_{1}, \dots, g_{n} \in G$ , given the input $∣ g_{1} ⟩ ∣ g_{2} ⟩ \dots ∣ g_{N} ⟩ ∣ 0 ⟩$ it outputs $∣ g_{1} ⟩ ∣ g_{2} ⟩ \dots ∣ g_{N} ⟩ ∣ Ψ_{g_{1}}^{1} ⟩ ∣ Ψ_{g_{2}}^{2} ⟩ \dots ∣ Ψ_{g_{N}}^{N} ⟩$ , where ${∣ Ψ_{g}^{i} ⟩, g \in G}$ form a hiding set of unit states i.e. $∣ Ψ_{g}^{i} ⟩, ∣ Ψ_{g'}^{i} ⟩$ are orthogonal if $g, g'$ are in distinct left cosets of $H$ and equal otherwise.

The abelian HSP algorithm still works when the oracle is replaced by such a procedure. Then, they reduced the HSP over nil-2 groups to those having exponent $p$ . They showed that in that case we can find a hidden subgroup $H$ if we have a hiding procedure for $H [G, G]$ and succeeded in constructing such a hiding procedure.

Finally, note that all the positive results previously mentioned in this section work for groups which are in some sense almost abelian. This is the case for the extensions of the Dedekindian HSP which work for groups with a large amount of normal subgroups, of the semi-directs product of abelian groups $G = A ⋊ B$ which can be broken down into $A ≅ A \times {0} ⊲ G$ and $\frac{G}{A \times {0}} = {0} \times B ≅ B$ . More generally, the results obtained from the black box methods break down the groups into abelian pieces through a normal series. However, it does not seem possible to apply this method for groups which contain a non-cyclic simple group in their composition series such that $A_{n}$ or $S_{n}$ . One attempt in that direction is [DenMooRus2008], with algorithms to find some hidden subgroups over the simple group $PGL (2, p^{m})$ and other related finite groups of Lie type. More precisely, we have a group $G$ acting on a set $S$ and have the promise that $H$ is a one point stabilizer $G_{s}$ , $s \in S$ . Their idea is to restrict to one of this stabilizer $G_{s_{0}}$ , apply a Strong Fourier Sampling on this group to determine $G_{s_{0}} \cap G_{s}$ and deduce $s$ . However to make this work, they need some additional hypotheses that do not seem to be satisfied by many groups. Moreover, it is still open whether we can find an efficient HSP taking into account the other subgroups. This may be hard, for example some maximal subgroups of $PGL (2, p^{m})$ are dihedral groups for which we do not have solutions yet.

The Hidden Subgroup Problem and Efficient Algorithms

In this section we discuss how HSP is related to some efficient algorithms with concrete applications. We have already mentioned in the first part of this report how particular abelian HSP have been used by Shor to make efficient algorithms for factoring numbers and computing discrete logarithms. 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 a group homomorphism. Although the quantum part is not actually needed here, this provides another example where a HSP can be used. Hallgren solved particular cases of HSP over the infinite abelian groups $ℝ$ and $ℝ^{r}$ [Hal2002], [Hal2005]. This allowed him to design polynomial-time algorithms for finding solutions $(x, y) \in ℤ^{2}$ to Pell's equation $x^{2} - d y^{2} = 0$ (where $d$ is a positive non-square integer) to which the factoring problem reduces. He also solved many important number fields problems.

The two non-abelian cases always mentioned are dihedral and symmetric groups. The HSP over these groups (or their variants: generalized dihedral HSP, alternating HSP etc) is expected to solve a lattice problem used in cryptography and the graph isomorphism problem. However, the first application requires the dihedral HSP to be solved by coset sampling while the second looks like out of the scope of all the techniques currently known. Hence, there is another point of view which consists in building cryptographic tools assuming the hardness of the HSP. For example, a classical one-way function is proposed in [MooRusVaz2007] and is at least as hard to invert as solving the Graph Isomorphism Problem. Also, inverting the function reduces to HSP over $GL (n, q)$ which is believed to be hard, given the negative results on its subgroup $S_{n}$ .

[Dam1988] contains a proposal for a hard problem with application in cryptography: Given $l + 1 = O (\log p)$ successive evaluations of the Legendre symbol $(\frac{s}{p}), (\frac{s + 1}{p}), \dots, (\frac{s + l}{p})$ predict the next value $(\frac{s + l + 1}{p})$ . The authors of [DamHalIp2002], proposed the related shifted Legendre symbol problem: given access to an oracle $f (x) = (\frac{x + s}{p})$ determine the hidden shift $s$ . Obviously, an algorithm to solve the shifted Legendre symbol problem using only oracle calls for values $0 \leq x \leq l$ provides a solution to the problem of [Dam1988]. The authors of [DamHalIp2002] solved the shifted Legendre symbol problem as well as other related hidden shift problems. They indicate that they can break certain cryptosystems by a reduction to the shifted Legendre symbol problem. They say that these cryptosystems can also be broken by Shor’s algorithm, but the two attacks on the cryptosystems appear to use completely different ideas. Hence this shifted Legendre symbol problem shows another relation between cryptosystems and HSP: it can be reduced to the HSP over $G = D_{p}$ (under certain assumptions) and as we will see in the next section it can also be reduced to a HSP over $G = ℤ_{p} ≀ ℤ_{2}$ .

Recall that in Grover's algorithm we have $N$ elements indexed from 0 to $N - 1$ , an oracle $φ : {0, \dots, N - 1} \to {0, 1}$ taking the value 1 for $M \leq \frac{N}{2}$ elements and we want to find one of these elements. Here, we take $M = 1$ and denote $j_{0}$ the element that satisfies $φ (j_{0}) = 1$ . Lomonaco and Kauffman proposed a comparaison between this case and Shor's algorithm [LomKau2006]. They described Shor's algorithm as an infinite HSP over $ℤ$ with a subgroup $p ℤ$ hidden by an oracle $f$ . They defined a "push" method, used to reduce the problem to some HSP over $ℤ_{q}$ (for some integer $q$ ) and a new oracle $\tilde{f}$ . Next, they considered the HSP over $S_{N}$ with hidden subgroup $H = {Stab}_{j_{0}}$ of permutations stabilizing $j_{0}$ . They used the subgroup ${Stab}_{0}$ and their "push" method to get a new problem where the oracle $\tilde{f} = φ$ is just Grover's oracle. However, from the definition of a "push" given of their paper, it is not obvious that their algorithm is applyable since we are loosing the group structure. They say that the definitions of the "push" and Fourier Sampling can be generalized but still the algorithm fails to provide a solution [Lom2010] . Anyway, Grover's algorithm can be interpreted as an efficient HSP algorithm for otherwise we would have an exponential speedup instead of the known optimal quadratic speedup [Zal1997]. Here, we are working over $G = S_{N}$ and an efficient algorithm is expected to be polynomial in $N \log N$ . With the promise $H = {Stab}_{j_{0}}$ , we only need to find the $j$ satisfying $f (σ_{j}) = f (Id)$ where we use the cycle $σ_{j} = (0,1, \dots, j - 1, j + 1, \dots, N - 1)$ moving all elements but $j$ . This can be done in $O (N)$ time classically (brute-force search) or even in $O (\sqrt{N})$ time quantumly (Grover's algorithm) and thus the HSP in that case is efficiently solvable. This was actually noted in [DenMooRus2008], where efficient algorithms are provided for 1-point stabilizer subgroups of $SL (2, q), PGL (2, q), PSL (2, q)$ . Interestingly, the big picture of their algorithm is similar to the "push" method above: rather than working over the whole group, they reduce the sampling to a particular 1-point stabilizer for which they can apply the non-abelian Fourier Sampling. Note that the size (or number of 1-point stabilizers) of these three groups is polynomial in $q$ and the efficient HSP algorithm polynomial in $\log q$ . Thus, the following open question: can we interpret these algorithms as concrete search problems with an exponentially fast solution?

Variants and Extensions

In this section, we present various problems related to the Hidden Subgroup Problem. Indeed, there have been several proposals to interpret the efficient algorithms of the first part of this report, other than the abelian HSP. New problems have been defined and solved for some particular cases. These problems are often related to HSP and their study has sometimes lead to solutions to instances of HSP. More generally, it is expected that these problems will also provide new quantum algorithms exponentially faster than the classical ones.

One extension is to allow $G$ to be an infinite group: it was actually already the case for the original Shor's algorithm which reduces the HSP over the infinite group $G = ℤ$ to the HSP over some cyclic group $ℤ_{q}$ , for some $q$ large enough. In general, the abelian HSP algorithm works for any finitely generated abelian group such that $G = ℤ^{n}$ . In order to solve various problem, Hallgren had to introduce HSP over $ℝ$ and $ℝ^{r}$ [Hal2002], [Hal2005]. The HSP he considered is finding a hidden subgroup $H = ⟨ τ ⟩$ of $ℝ$ generated by an irrational $τ$ (or said otherwise, determining an irrational period $τ$ of a function $f$ ) as well as finding a hidden lattice $H$ of $ℝ^{r}$ . In both cases, the rough idea is to construct a computable discretized version of the oracle $f$ and show that we can approximate generators for $H$ .

Other extensions to HSP have been proposed in three different papers, but they do not seem to have subsequently been studied. One proposal is the Hidden Subhypergroup Problem [AmiKalRoo2006] where the group $G$ is generalized to an hypergroup i.e. the product of two elements is a subset of $G$ rather than a single element. A second proposal is the Hidden Symmetries Problem [SchUnr2003] where we generalize the condition that $f$ is constant on each left coset to a more general property $\forall x \in G, V (f (x), f (U (x)))$ . For example, saying that $f$ hides $H$ is simply taking $V$ to be the equality and $U (x) = x H$ . The third proposal is the Hidden Covering Space Problem [OsbSev2004] which generalizes the version of HSP given as a coset sampling black-box. This proposal involves topological spaces and is a bit more complicated to define. We will just say that we consider Cayley graph of groups endowed with their natural topology.

A variation that has been extensively studied is the Hidden Shift Problem. In this problem, we have two injective functions $f_{0}, f_{1}$ on $G$ satisfying $\forall x \in G, f_{1} (x) = f_{0} (x + s)$ for some $s \in G$ . The purpose is to determine the hidden shift $s$ . The problem was solved for many cases, including smoothly solvable groups [FriEtAl2002], bent functions [Röt2008], functions close to a quadratic [Röt2009], Legendre symbol [DamHalIp2002] as well as more general multiplicative characters on finite fields and on ideals $\frac{ℤ}{n ℤ}$ [DamHalIp2002]. When $G$ is abelian, the problem is equivalent to HSP over the generalized dihedral group $G ⋊ ℤ_{N}$ . In particular, for $G = ℤ_{N}$ the problem is equivalent to DHSP. A decision version is considered in [ChiWoc2005]: either a shift $s$ exists or the images of $f_{0}, f_{1}$ are disjoint. We are asked to determine in which case we are. A solution to this decision version for the symmetric group $G = S_{n}$ would provide an efficient algorithm for the rigid graph isomorphism problem. A Generalized Hidden Shift Problem is considered in [ChiDam2005] and solve for the cyclic group $G = ℤ_{N}$ under certain conditions. The generalization consists in having $M$ injective functions $f_{0}, \dots, f_{M - 1}$ satisfying $\forall x \in G, f_{i} (x) = f_{0} (x + i s)$ . Note that the generalized hidden shift problem reduces to HSP over the wreath product $G ≀ ℤ_{M}$ [FenZha2006]. Hence, the two solutions to the hidden shift problem from Rötteler mentioned above are particular case of $G = ℤ_{2}^{n}$ which is solved from the efficient algorithm he obtained with Beth [RötBet1998]. When the functions $f_{0}, f_{1}$ are not injective, the set of elements $s \in G$ satisfying the shift equality can be proved to be a coset of some subgroup $H$ [DamHalIp2002]. Finding this set is then called the Hidden Coset Problem. It turns out that this problem is actually polynomial-time equivalent to HSP [FenZha2006]. If $H$ is normal, we can work in the quotient group $\frac{G}{H}$ and reduce the problem to the hidden shift problem [Ip2002], [DamHalIp2002].

To solve some HSP instances, Friedl et al. [FriEtAl2002] used several HSP-related problems. In addition to the Hidden Shift Problem discussed above (which is called hidden translation in their paper), they introduced the Hidden Stabilizer Problem, Orbit Coset Problem, and Orbit Superposition Problem. For the first one, we have a group $G$ acting on a set of pairwise orthogonal quantum states. Given such a state we are asked to find its stabilizer subgroup. The second one is a generalization: given two states $∣ Ψ_{0} ⟩$ and $∣ Ψ_{1} ⟩$ we have to answer whether the intersection of their orbits is empty or find an element $g \in G$ sending $∣ Ψ_{0} ⟩$ to $∣ Ψ_{1} ⟩$ as well as the stabilizer subgroup of $∣ Ψ_{1} ⟩$ . One interesting feature of Orbit Coset Problem on a group $G$ is the following self-reductibility property: if $N$ is a solvable normal subgroup of $G$ , then the problem reduces to the Orbit Coset Problem on $\frac{G}{N}$ and on subgroups of $N$ . Notice that such a property would be really appreciated for HSP to design an algorithm similar to the one of figure 6.2. Finally, the Orbit Superposition Problem asks to create the uniform superposition over the orbit of a given state $∣ Ψ ⟩$ . For solvable groups, it reduces to Orbit Coset Problem. Again, in [FenZha2006] it is proved that Orbit Coset is polynomial-time equivalent to the Hidden Subgroup Problem when we allow the oracle $f$ to be a quantum function.

As many other problems, decision and search versions of HSP have also been imagined. [FenZha2006] defines ${HSP}_{D}$ to be the problem of deciding whether $H$ is trivial and ${HSP}_{S}$ to be the problem of findind a nontrivial element of $H$ , if there is one. As we have previously seen, this is of particular importance for the dihedral and symmetric HSP. In the paper, they give a reduction of HSP to ${HSP}_{D}$ for the dihedral group (under certain conditions) and a polynomial-time equivalence between ${HSP}_{S}$ and ${HSP}_{D}$ for permutation groups. The latter equivalence suggests that the problem is hard, since we have this property for problems considered to be difficult such that NP-complete or graph isomorphism. Another proposal for a decision version of HSP is the Hidden Subgroup Test Function where we are given $G, H$ , as well as a function $f$ on $G$ and want to decide whether the function hides the subgroup $H$ . In [AblVas2009], the function $f$ is encoded as a particular "input sequence". Similarly in [FriEtAl2002bis], the Large Period Problem is studied: we are given $G$ , a subgroup $K$ and a function $f$ . We want to decide whether $K$ is a proper superset of some subgroup $H \subseteq G$ hidden by $f$ . The problem is solved for abelian subgroups. The paper also defines the Common Coset Range Problem: given $H \subseteq G$ and two functions $f_{0}, f_{1}$ on $G$ do we have the equality $\forall x \in G, f_{1} (x H) = f_{0} (x H)$ ? Again, the problem is solved for some particular cases.

Let's consider now the case of the abelian HSP dealing with the vector space $G = F_{q}^{m}$ over the finite field $F_{q}$ , which is studied in [ChiSchVaz2007]. Any subgroup $H$ is a linear subspace of $G$ and cosets $g + H$ are parallel affine subspaces. Thus in the abelian HSP over $F_{q}^{m}$ we have an oracle constant on each affine subspace, taking distinct values on different ones and want to find a subspace $H$ . If $H$ is a hyperplane, there are coefficients $q_{i} \in F_{q}$ such that the linear polynomial $P (x) = \sum_{i = 0}^{m} q_{i} x_{i}$ satisfies $H = KerP$ . Moreover, $P$ is constant on each coset and takes distinct values on different ones. Thus the oracle can be written $f (x) = π (P (x))$ for some fixed unknown permutation $π$ of $F_{q}$ . The Hidden Polynomial Problem is to determine the polynomial $P$ whose degree is still bounded, but we now allow this degree to be greater than 1. Similarly to the case of the hyperplane $H$ , we assume that the constant term is $P (0) = 0$ , for otherwise that term can not be determined, since $π$ is arbitrary. The problem can also be viewed as finding the hidden hypersurface defined by the equation $P (x) = 0$ and the cosets are replaced by level hypersurfaces (defined by equations $P (x) = k$ ). One special case is when the polynomial is of the form $P (x) = x_{m} - Q (x_{1}, \dots, x_{m - 1})$ i.e. the hidden hypersurface is defined by the parametric equation $x_{m} = Q (x_{1}, \dots, x_{m - 1})$ . In that case, the level hypersurfaces are just obtained by translating along the $x_{m}$ -axis. This problem, called Hidden Polynomial Function Graph Problem is considered in [DecWoc2007], [DecDraWoc2007] and solved for quadratic and cubic polynomial $Q$ .

The authors of [ChiSchVaz2007] also consider other hidden structure problems on $G = F_{q}^{m}$ . They define the Hidden Radius Problem: determine an unknown radius $r$ given a blackbox that outputs superposition over the points of a sphere of radius $r$ whose center is chosen uniformly at random. Similarly they define the Hidden Flat of Center: determine a flat given a blackbox that outputs superposition over unit sphere whose center is chosen uniformly at random in the hidden flat. They give a partial solution to the former and a complete solution to the latter. Other algorithms of this kind are given in [Mon2008] for the group $G = {0, 1}^{n}$ . All these problems are included in the more general category of Hidden Shifted Subset Problems. We have a group $G$ , a subset of elements $S$ and a subset of shifts $T$ the black box outputs uniform superposition of element over the set $S + t$ for a $t \in T$ chosen uniformly at random. The purpose is to determine some property of $S$ or $T$ . To compare their power with the one of a classical computer, we would like an approach similar to HSP where we just have an oracle $f$ whose preimages are the possible superpositions output by the black box. This does not seem possible in the general case, since the superpositions considered may intersect but some workarounds are used for the particular problems mentioned above.

back to index