• Quick access
  • Homepage (fr)
  • International
  • François's Blog
  • Frédéric's Blog
  • Maths (fr)
  • Computer Science (fr)
  • Programming (fr)
  • Our games (fr)
  • Video games (fr)
• Special pages
  • Log in (fr)
  • Forum
  • Authors (fr)
  • Site Map (fr)
• Parent directories
  • International
  • The Hidden Subgroup Problem
  • The Standard Method for The Hidden Subgroup Problem
• Current directory
  • Index
  • Report
  • Introduction
  • Prerequisites
  • Efficient Quantum Algorithms and The Hidden Subgroup Problem
  • The Standard Method for The Hidden Subgroup Problem
  • The Dihedral and Symmetric Hidden Subgroup Problems
  • The General Hidden Subgroup Problem
  • Conclusion
  • Appendix A
  • Appendix B
  • Appendix C
  • Appendix D
  • Appendix E
  • Appendix F
  • Appendix G
  • Bibliography

The "Standard Method" for The Hidden Subgroup Problem

The Abelian Hidden Subgroup Problem

This section deals with the abelian HSP and is mostly based on [Dam2001]. We just give the big picture of the general method and show how it generalizes the three previous examples. A more detailed presentation is given in [Lom2004].

In the previous chapter, we have seen three efficient quantum algorithms that fit into the framework of the hidden subgroup problem. Actually, these problems are also sharing the same kind of algorithm. First, they are all based on a particular case of HSP where the group is abelian. As it is well-known, such a group is isomorphic to a product of cyclic groups ${\mathbb{Z}}_{t_1}\times {\mathbb{Z}}_{t_2}\times {\mathbb{Z}}_{t_3}\times \dots \times {\mathbb{Z}}_{t_k}$ and this is clearly the case in the three previous algorithms. We can then describe the quantum circuit in a general way:

The first register is composed of a product of $k$ states of $\lceil \log \left(t_i\right)\rceil$ qubits and we apply to this register the operation $F_G=F_{t_1}\otimes F_{t_2}\dots \otimes F_{t_{\mathrm{k}}}$ i.e. the Fourier transform $F_{t_i}$ to the i-th state (note that for Simon's problem, $H=F_2$ ). First, let's consider the effect of $F_G$ on any element $g\in G$:

$$\begin{array}{rl}{F}_G\mid g⟩& =F_G\left({\otimes }_{i=1}^k\mid g_i⟩\right)\\ & ={\otimes }_{i=1}^k\left(F_{t_i}\mid g_i⟩\right)\\ & ={\otimes }_{i=1}^k\left(\frac{1}{\sqrt{t_i}}\sum _{g_i\prime =0}^{t_i-1}{e}^{\frac{2i\pi g_i{g}_i\prime }{t_i}}\mid g_i\prime ⟩\right)\\ & =\frac{1}{\sqrt{\prod _{i=1}^k{t}_i}}\sum _{g\prime \in G}\left(\prod _{i=1}^k{e}^{\frac{2i\pi g_i{g}_i\prime }{t_i}}\right)\left({\otimes }_{i=1}^k\mid g_i\prime ⟩\right)\\ & =\frac{1}{\sqrt{\mid G\mid }}\sum _{g\prime \in G}{\chi }_g(g\prime )\mid g\prime ⟩\end{array}$$

Where we have introduced the characters ${\chi }_g(g\prime )$. Note that $g\mapsto {\chi }_g$ is a group homomorphism i.e. ${\chi }_{g+g\text{'}}={\chi }_g{\chi }_{g\text{'}}$. We also have ${\chi }_g(g\prime ){=\chi }_{g\text{'}}(g)$ and so ${\chi }_g(g\prime +g\prime \prime )={\chi }_g(g\prime ){\chi }_g(g\prime \prime )$. Hence we can define the group $H^{\perp }=\left\{g\in G|{\chi }_g\left(H\right)=1\right\}$. By Theorem 3.10 of [Lom2004], $H^{\perp }$ is isomorphic to $\raisebox{1ex}{$G$}\!\left/ \!\raisebox{-1ex}{$H$}\right.$ and moreover ${\left(H^{\perp }\right)}^{\perp }=H$.

As we have already seen many times, the state after the gate $U_f$ is the following superposition:

$$\frac{1}{\sqrt{\mid G\mid }}\sum _{g\in G}\mid g⟩\mid f(g)⟩\text{where}\mid g⟩=\mid g_1⟩\dots \mid g_k⟩$$

Measuring the second register gives a value $y=f\left(g^0\right)$ and leaves the first register in the state

$$\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}\mid g^0+h⟩$$

Then we apply the Fourier transform $F_G$. Using the expression of formula 4.1 and the properties of the characters, we get

$$\begin{array}{rl}{F}_G\left(\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}\mid g^0+h⟩\right)& =\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}\left(F_G\mid g^0+h⟩\right)\\ & =\frac{1}{\sqrt{\mid H\mid \mid G\mid }}\sum _{h\in H}\sum _{g\in G}{\chi }_{(g^0+h)}(g)\mid g⟩\\ & =\frac{1}{\sqrt{\mid H\mid \mid G\mid }}\sum _{h\in H}\sum _{g\in G}{\chi }_g(g^0){\chi }_g(h)\mid g⟩\\ & =\frac{1}{\sqrt{\mid H\mid \mid G\mid }}\sum _{g\in G}\left({\chi }_g(g^0)\sum _{h\in H}{\chi }_g(h)\right)\mid g⟩\\ & \end{array}$$

If we measure the first register, the probability to get an element of $H^{\perp }$ is:

$$\begin{array}{rl}\frac{1}{\mid H\mid \mid G\mid }\sum _{g\in H^{\perp }}{\mid {\chi }_g(g^0)\sum _{h\in H}{\chi }_g(h)\mid }^2& =\frac{1}{\mid H\mid \mid G\mid }\sum _{g\in H^{\perp }}\left({\mid {\chi }_g(g^0)\mid }^2{\mid \sum _{h\in H}1\mid }^2\right)\\ & =\frac{1}{\mid H\mid \mid G\mid }\sum _{g\in H^{\perp }}\left(1^2{\mid H\mid }^2\right)\\ & =\frac{\mid H^{\perp }\mid {\mid H\mid }^2}{\mid H\mid \mid G\mid }\\ & =\frac{\mid G\mid {\mid H\mid }^2}{{\mid H\mid }^2\mid G\mid }\\ & =1\end{array}$$

Moreover, the previous calculation shows that each element of $H^{\perp }$ has the same probability to be measured. Hence, measuring the first register yields a uniformly random element of $H^{\perp }$. Repeating the previous circuit about $n=\lceil \log \mid G\mid \rceil$ times gives with high probability a set of generators $g^1,\dots ,g^{O\left(n\right)}$ of $H^{\perp }$. We have $h\in H={\left(H^{\perp }\right)}^{\perp }$ iff for all $j$, ${\chi }_h\left(g^j\right)=1=\prod _{i=1}^k{e}^{\frac{2i\pi h_i{g}_i^j}{t_i}}$. If we denote $e$ the lower common multiple of the $t_i$'s and ${\alpha }_i^{g^j}=\raisebox{1ex}{$e{g}_i^j$}\!\left/ \!\raisebox{-1ex}{$t_i$}\right.$, $h\in H$ iff $\sum _{i=1}^k{\alpha }_i^{g^j}{h}_i\equiv 0\text{ mod }\left(e\right)$. We can put this system in Smith normal form (i.e. write as a diagonal system) in time polynomial of $n$. Then get $O\left(n\right)$ linear congruences i.e. of the form $ax\equiv b\text{ mod }\left(e\right)$. The method to enumerate the list of solution to a linear congruence is well-known. We randomly pick one solution to each linear congruence to get a uniformly random element of $H$. Repeating this about $n$ times gives with high probability a set of generators of $H$.

As previously stated, we also need an efficient quantum circuit to compute the Fourier transform $F_G$. Note that such a circuit is known for $F_{2^x}$ and an approximate one (i.e. measuring the result gives a probability distribution very close to the exact version) for other $F_x$'s. See for instance [Lom2004]. This allows to have an approximate implementation of $F_G=F_{t_1}\otimes F_{t_2}\dots \otimes F_{t_{\mathrm{k}}}$ that does not change too much the measurement of the circuit of figure 4.1.

As a consequence, we have an efficient solution to the abelian HSP if we know a decomposition ${\mathbb{Z}}_{t_1}\times {\mathbb{Z}}_{t_2}\times {\mathbb{Z}}_{t_3}\times \dots \times {\mathbb{Z}}_{t_k}$ of $G$. Otherwise, we can get it if we are working in the black-box model with unique encoding. We describe the idea of [CheMos2001], without trying to optimize the computation. We choose randomly $k\text{'}=O\left(n\right)$ elements $a_1,\dots ,a_{k\text{'}}$ of $G$, so that they generate the group with high probability. Then we define $f:{\mathbb{Z}}_{\mid G\mid }^{k\text{'}}\to G$ by $f\left(x\right)=\sum _{i=1}^{k\text{'}}{x}_i{a}_i$. Each term $x_i{a}_i$ is computed using $O\left(\log x_i\right)=O\left(\log \mid G\mid \right)=\text{poly}\left(n\right)$ sums (by a double-and-add algorithm), so $f$ has a polynomial complexity. ${\mathbb{Z}}_{\mid G\mid }^{k\text{'}}$ is abelian and we know its decomposition so we can apply the HSP algorithm to find a set of generators for the hidden subgroup $H=\mathrm{Ker}f$. Alternatively, these generators can be obtained using the algorithm of [BucNei1996]. It can be shown that from this set of generators we can find (classically) in $\text{poly}\left(n\right)$ a set of generators $\overline{u_1},\dots ,\overline{u_k}$ of $\raisebox{1ex}{${\mathbb{Z}}_{\mid G\mid }^{k\text{'}}$}\!\left/ \!\raisebox{-1ex}{$H$}\right.$ that satisfies:$$\raisebox{1ex}{${\mathbb{Z}}_{\mid G\mid }^{k\text{'}}$}\!\left/ \!\raisebox{-1ex}{$H$}\right.=⟨\overline{u_1}⟩\oplus \dots \oplus ⟨\overline{u_k}⟩$$

Using the isomorphism $G\cong \raisebox{1ex}{${\mathbb{Z}}_{\mid G\mid }^{k\text{'}}$}\!\left/ \!\raisebox{-1ex}{$H$}\right.$, we get $G=⟨v_1⟩\oplus \dots \oplus ⟨v_k⟩$ where $v_i=f\left(u_i\right)$. We define an abelian HSP by $f_i:{\mathbb{Z}}_{\mid G\mid }\to G$ and $f_i\left(x\right)=x{v}_i$ (again, $f$ has a $\text{poly}\left(n\right)$ complexity). As in Shor's algorithm, the hidden subgroup is $t_i{\mathbb{Z}}_{\mid G\mid }$ where $t_i$ is the order of $v_i$. Finally, we get $G\cong {\mathbb{Z}}_{t_1}\times {\mathbb{Z}}_{t_2}\times {\mathbb{Z}}_{t_3}\times \dots \times {\mathbb{Z}}_{t_k}$.

Fourier Transform over Finite Groups

In order to generalize the previous algorithm to any finite group, we need a way to define Fourier Transform. First, we give a brief overview of representation theory of groups, based on [Ser1971].

In [Ser1971], it is shown that any finite group $G$ has only a finite number of irreducible pairwise non-isomorphic representations. More precisely, if we denote $\hat{G}$ a complete set of such representations and $V_{\rho }$ and $d_{\rho }$ the associated vector space and dimension (for any $\rho \in Ĝ$), we have the following equality from 2.4 Décomposition de la représentation régulière - Corollaire 2:

$$\frac{1}{\mid G\mid }\sum _{\rho \in Ĝ}{d}_{\rho }{\chi }_{\rho }\left(g\right)={\delta }_{g,1}$$

In particular for $g=1$, because ${\chi }_{\rho }\left(1\right)=\mathrm{tr}\left(I_{d_{\rho }}\right)=d_{\rho }$, we have:

$$\mid G\mid =\sum _{\rho \in Ĝ}{d_{\rho }}^2$$

For each $\rho$, we can choose a basis of $V_{\rho }$ and then $\rho \left(g\right)$ is represented by a matrix of size $d_{\rho }$. Again, in view of formula 4.8, we can group all the coefficients ${\left({\rho }_{ij}(g)\right)}_{1\le i,j\le d_{\rho },g\in G}$ in a square matrix of dimension $\mid G\mid$. To make this matrix unitary, we add the requirement that each $\rho \left(g\right)$ is unitary. We will see that it is always possible to choose the basis such that this requirement is satisfied. Once such a basis is chosen and when no confusion is possible, we will also denote $\rho \left(g\right)$ the matrix representation of $\rho \left(g\right)$ in this basis.

Let's see how the previous definition generalizes the abelian case:

The proposition 4.4 above shows that there is at least one basis of $V_{\rho }$. Actually, we obtain all of them by unitary change of basis:

In this section, we have defined an operation $F_G$ for any given group. We know that it is unitary so a valid quantum. However, if we want to to use it in a HSP algorithm, we need to implement it efficiently i.e. using $\text{poly}\left(n\right)$ elementary gates. As mentioned above, there is an approximate efficient implementation of $F_N$ for cyclic group. By taking the tensor product of such operations, we get an approximate efficient implementation for any abelian group $G$. Other efficient implementations are known for various groups, see [Lom2004] for an overview. The exact description of the quantum gate $F_G$ depends on the design used for the implementation. Nevertheless, we will suppose in what follows that the gate implementing $F_G$ works on $n$ qubits. The input $\mid g⟩$ and output $\mid \rho ij⟩$ are encoded by the integers $0,\dots ,\mid G\mid -1$. The possible remaining basis states are not touched by the gate.

Weak and Strong Fourier Sampling

For the generalized version of the Fourier Sampling circuit, we replace the first Fourier Transform by a gate $V$ that computes a superposition $\frac{1}{\sqrt{\mid G\mid }}\sum _{g\in G}\mid g⟩$ from the $\mid 0^n⟩$ state. There is no canonical implementation for $V$ but if the elements of $G$ are encoded by the integer $0,\dots ,\mid G\mid -1$ (as we have assumed in previous section) we can use the following circuit:

We use a hadamard gate to create a superposition over $0,\dots ,2^n-1$ and a function $g$ to select the values less than $\mid G\mid$: $g\left(i\right)=1$ if $0\le i<\mid G\mid$ and $g\left(i\right)=0$ otherwise (It can be implemented efficiently, just by comparing the binary decomposition of $i$ and $\mid G\mid$). We succeed to create the superposition if the result of the measurement is 1. We have $2^{n-1}<\mid G\mid \le 2^n$, so this happens with probability $\frac{\mid G\mid }{2^n}>\frac{1}{2}$.

The remaining of the circuit is similar to what we have previously seen, with the use of a general Fourier Transform gate $F_G$:

After applying the gate $U_f$ we have the superposition

$$\frac{1}{\sqrt{\mid G\mid }}\sum _{g\in G}\mid g⟩\mid f(g)⟩$$

We then measure the second register and get $y=f\left(g^0\right)$. We obtain a superposition on a coset $g^{0}H$:

$$\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}\mid g^{0}h⟩$$

Creating this superposition is the starting point for all HSP algorithms currently known. Hence we define:

For Fourier Sampling, the next step is to apply the Fourier Transform $F_G$. This gives the state $$\sum _{\rho \in \stackrel{̂^}{G}}\sum _{i,j=1}^{d_{\rho }}\sqrt{\frac{d_{\rho }}{\mid G\mid }}{\left(\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}\rho (g^{0}h)\right)}_{ij}\mid \rho ij⟩=\sum _{\rho \in \hat{G}}\sum _{i,j=1}^{d_{\rho }}\sqrt{\frac{d_{\rho }}{\mid G\mid }}{(\rho (g^{0}H))}_{ij}\mid \rho ij⟩$$

where we have introduced $\rho (g^{0}H)=\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}\rho (g^{0}h)$. Finally, we perform a measurement on the first register.

What is the distribution probability? First the conditional probability given $g^0$ is $P\left(\raisebox{1ex}{$\rho ,i,j$}\!\left/ \!\raisebox{-1ex}{$g^0$}\right.\right)=\frac{d_{\rho }}{\mid G\mid }{{\mid \rho (g^{0}H)\mid }_{ij}}^2$. Hence for the Weak Fourier Sampling, we have $P\left(\raisebox{1ex}{$\rho $}\!\left/ \!\raisebox{-1ex}{$g^0$}\right.\right)=\sum _{i,j=1}^{d_{\rho }}P\left(\raisebox{1ex}{$\rho ,i,j$}\!\left/ \!\raisebox{-1ex}{$g^0$}\right.\right)=\frac{d_{\rho }}{\mid G\mid }{\Vert \rho (g^{0}H)\Vert }_F^2$ and using $\rho \left(g^{0}H\right)=\rho \left(g^0\right)\rho \left(H\right)$ and the fact that $\rho \left(g^0\right)$ is unitary:

It was proven in [GriSchVaz2000] that $\rho (H)$ is $\sqrt{\mid H\mid }$ times a projection matrix $P$. Moreover, $\rho (H)$ is hermitian:

$${\rho (H)}^{†}=\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}{\rho (h)}^{†}=\frac{1}{\sqrt{\mid H\mid }}\sum _{h\in H}\rho (h^{-1})=\frac{1}{\sqrt{\mid H\mid }}\sum _{h^{\text{'}}\in H}\rho (h\text{'})=\rho (H)$$

Hence $\frac{1}{\mid H\mid }{\Vert \rho (H)\Vert }_F^2=\mathrm{tr}\left(P^{†}P\right)=\mathrm{tr}\left(P^2\right)=\mathrm{tr}\left(P\right)=\frac{1}{\sqrt{\mid H\mid }}\mathrm{tr}\left(\rho \left(H\right)\right)$ and formula 4.18 can be rewritten:

$$P\left(\rho \right)=\frac{d_{\rho }}{\mid G\mid }\sqrt{\mid H\mid }\mathrm{tr}\left(\rho \left(H\right)\right)$$

In particular, this probability does not depend on the choice of the basis of $V_{\rho }$!

For the Strong Fourier Sampling, we first note that the $\mid G\mid$-dimensional vectors ${\left({\rho (g^0)}_{ik}\right)}_{g^0\in G}$ for $1\le k\le d_{\rho }$ are orthogonal of norm $\sqrt{\frac{\mid G\mid }{d_{\rho }}}$:

$$\begin{array}{rl}⟨{\left({\rho \left(g^0\right)}_{ik}\right)}_{g^0\in G},{\left({\rho \left(g^0\right)}_{ik\prime }\right)}_{g^0\in G}⟩& =\sum _{g^0\in G}{\rho \left(g^0\right)}_{ik}^{*}{\rho \left(g^0\right)}_{ik\prime }\\ & =\sum _{g^0\in G}{\rho \left({\left(g^0\right)}^{-1}\right)}_{ki}{\rho \left(g^0\right)}_{ik\prime }\\ & =\frac{\mid G\mid }{d_{\rho }}{\delta }_{kk\prime }{\delta }_{ii}\end{array}$$

where the last line is 2.2 Le lemme de Schur ; premières applications - Corollaire 3 of [Ser1971]. We use this fact to simplify the expression of $P(\rho ,i,j)$ as described in [GriSchVaz2000]. Because $g^0$ has been chosen uniformly it is the mean of $P\left(\raisebox{1ex}{$\rho ,i,j$}\!\left/ \!\raisebox{-1ex}{$g^0$}\right.\right)$ over the elements of the group $G$:$$\begin{array}{rl}P(\rho ,i,j)& =\frac{d_{\rho }}{{\mid G\mid }^2}\sum _{g^0\in G}{\mid {\rho (g^{0}H)}_{ij}\mid }^2\\ & =\frac{d_{\rho }}{{\mid G\mid }^2}{\parallel {\left({\rho (g^{0}H)}_{ij}\right)}_{g^0\in G}\parallel }^2\\ & =\frac{d_{\rho }}{{\mid G\mid }^2}{\parallel {\left({(\rho (g^0)\rho (H))}_{ij}\right)}_{g^0\in G}\parallel }^2\\ & =\frac{d_{\rho }}{{\mid G\mid }^2}{\parallel {\left(\sum _{k=0}^{d_{\rho }}{\rho (g^0)}_{ik}{\rho (H)}_{kj}\right)}_{g^0\in G}\parallel }^2\\ & =\frac{d_{\rho }}{{\mid G\mid }^2}{\parallel \sum _{k=0}^{d_{\rho }}{\rho (H)}_{kj}{\left({\rho (g^0)}_{ik}\right)}_{g^0\in G}\parallel }^2\\ & =\frac{d_{\rho }}{{\mid G\mid }^2}\sum _{k=0}^{d_{\rho }}\left({\mid {\rho (H)}_{kj}\mid }^2\frac{\mid G\mid }{d_{\rho }}\right)\\ & =\frac{1}{\mid G\mid }{\parallel {\rho (H)}_j\parallel }^2\end{array}$$

and we finally obtain an expression which is totally independent of $i$:

$$\begin{array}{c}P(\rho ,i,j)=\frac{1}{\mid G\mid }{\parallel {\rho (H)}_j\parallel }^2\\ P(\rho ,.,j)=\frac{d_{\rho }}{\mid G\mid }{\parallel {\rho (H)}_j\parallel }^2\end{array}$$

This means that measuring the row provides no information and the Strong Fourier Sampling can be reduced to observing $\rho ,j$. Note that summing over all the $j$, we recover formula 4.18.

As said in remark 4.6, all the irreducible representations are 1-dimensional in the abelian case. Consequently, the Strong Fourier Sampling is the same as the Weak Fourier Sampling: we only take into account the irreducible representations ${\rho }_{g_j}$ measured. More precisely, we measure random elements $g^1,\dots ,g^{O\left(n\right)}$ in $H^{\perp }=\left\{g\in G|{\chi }_g\left(H\right)=1\right\}=\left\{g\in G|H\subseteq \mathrm{Ker}{\rho }_g\right\}$. Then we solve the systems of equations ${\chi }_{g^j}\left(h\right)={\chi }_h\left(g^j\right)=1$ to get elements $h$ in $H$. Said otherwise, we are looking to random elements in $H=\bigcap _{j=1}^{O\left(n\right)}\mathrm{Ker}{\rho }_{g_j}$. In the next section, we will see that more generally, considering the intersection of irreducible representations measured gives information on $H$ and allows to solve the HSP in some particular cases.

The Dedekindian Hidden Subgroup Problem and its extensions

In this section, we see how the Weak Fourier Sampling can be used to extend the abelian HSP. The idea is to measure ${\rho }_1,\dots {,\rho }_{O\left(n\right)}$ irreducible representations and to consider the intersection $\bigcap _{j=1}^{O\left(n\right)}\mathrm{Ker}{\rho }_j$. Let's consider first what is happening in an example:

Consequently, the direct application of the abelian method does not always work. Note that $H_2$ is normal (it is the of center $D_4$) but $H_1$ is not (for example $s\left(\mathrm{rs}\right)s^{-1}=\mathrm{sr}=r^{3}s\notin H_1$). In general, $\mathrm{tr}\left(\rho (g^{-1}Hg)\right)=\mathrm{tr}\left({\rho \left(g\right)}^{-1}\rho (H)\rho \left(g\right)\right)=\mathrm{tr}\left(\rho (H)\right)$ so by formula 4.20, the Weak Fourier Sampling can not distinguish $H$ with one of its conjugate $g^{-1}Hg$. However, we can still hope that it will work for a normal subgroup $H$. This is what Hallgren, Russel and Ta-Shma proved in [HalRusTa-2000]:

As a consequence, we can use this to solve the Dedekindian Hidden Subgroup Problem i.e. over groups that have only normal subgroups. Of course, this includes the Abelian HSP that we have previously studied. The non-abelian Dedekind groups are called Hamiltonian and they are of the form $G={\mathbb{Z}}_2^k\times A\times {\mathbb{Q}}_8$ where $A$ is an abelian group with all elements of odd order. The appendix B.2 of [HalRusTa-2000] gives a precise algorithm for the Hamiltonian HSP: an efficient implementation of the Weak Fourier Sampling over $G$ and a way to pick $O\left(n\right)$ random solutions to the system ${\rho }_i\left(h\right)=I_{d_{{\rho }_i}}$ in order to get a set of generators for $H$.

By calling several times the Weak Fourier Sampling (possibly over subgroups of $G$), the Dedekindian HSP can be generalized. However the possibility to compute the Fourier Transform, to solve systems ${\rho }_i\left(h\right)=I_{d_{{\rho }_i}}$ and to do the same for any of its subgroup involved in the algorithm, depends on the underlying group $G$. First, as noted in [GriSchVaz2000], running this algorithm for any $H$ (not necessarily normal) gives with high probability the highest subgroup of $H$ which is normal in $G$. We can also solve the case where "almost all" subgroups of $G$ are normal i.e. the intersection of normalizers $M_G$ is big enough or, equivalently, that $\frac{\mid G\mid }{\mid M_G\mid }$ is small. For example $M_G=G$ for an abelian group and $\frac{\mid G\mid }{\mid M_G\mid }=1$. In [GriSchVaz2000], Grigni et al. presented an efficient HSP algorithm when $\frac{\mid G\mid }{\mid M_G\mid }\in \exp \left(O\left(\sqrt{\log \left(\log \mid G\mid \right)}\right)\right)$. They give an application to the semi-direct product ${\mathbb{Z}}_3⋊{\mathbb{Z}}_{2^n}$. Gavinsky [Gav2004] strengthened their result to $\frac{\mid G\mid }{\mid M_G\mid }\in \text{poly}\left(\log \mid G\mid \right)$. Actually, he proved that we can even just assume $\frac{\mid G\mid }{\mid {HM}_G\mid }\in \text{poly}\left(\log \mid G\mid \right)$ so that the algorithm still works when $H$ is large.

Note that if the group is given as a black-box group without necessarily unique encoding, there is an alternative way to find the normal subgroup $H$ as described in [IvaMagSan2001]. The algorithm does not require the assumptions on Fourier Transform and systems above. Its complexity is given by the input size + a number $v\left(\raisebox{1ex}{$G$}\!\left/ \!\raisebox{-1ex}{$H$}\right.\right)$ that we will define later. We will come back to this method in the last part of this report.

This page is W3C-compliant - Author: Frédéric WANG