Maximal Subgroup Reduction and HSP over Projective Linear Groups

10 Dec 2010

-- updated the 12th of December.

Among the recent algorithms for the Hidden Subgroup Problem, two are particularly interesting: one to find hidden subgroups of nil-2 groups by Ivanyos, Sanselme and Santha ; and another one to find conjugate stabilizer subgroups of $PSL (2, q)$ (and also those of the related groups $SL (2, q)$ and $PGL (2, q)$ ) by Denney, Moore and Russell. The idea of both algorithms is to reduce the initial problem to a HSP over a group for which we already know an efficient algorithm. However, the former only relies on Fourier Sampling over abelian groups while the latter requires Strong Fourier Sampling over some semidirect products of abelian groups. Also, considering the general approach to HSP that I have described in my Master Project, the technique of the former is only likely to work for solvable groups while the composition series of groups considered in the latter contain non-abelian simple groups... but can their ideas be combined together to get new HSP algorithms?

First, let's recall the concept of quantum hiding functions, which is a key ingredient of the first paper. In general, HSP algorithms use a classical oracle $f$ over $G$ which hides a subgroup $H$ i.e. is constant over each coset of $H$ and takes different values on different cosets. The quantum counterpart of $f$ is implemented by a quantum operator $U_{f}$ which takes $∣ g ⟩ ∣ 0 ⟩$ to $∣ g ⟩ ∣ f (g) ⟩$ . Some HSP algorithms use the so-called Strong Fourier Sampling: we create a uniform superposition of the states $∣ g ⟩ ∣ f (g) ⟩$ over all $g \in G$ , apply a Fourier Tranform on the first register and measure it. The idea of quantum hiding functions is to replace $U_{f}$ by any other quantum operator sending $∣ g ⟩ ∣ 0 ⟩$ to $∣ g ⟩ ∣ Ψ_{g} ⟩$ . In order to make the procedure works, we only need the $∣ Ψ_{g} ⟩$ 's to be unit states taking the same value over one coset of $H$ and orthogonal values on different cosets. These states may even change at each sampling.

To solve the general HSP and in particular the difficult case of simple groups, I have proposed maximal subgroup reduction. Basically, the idea is to find a maximal subgroup $K$ containing $H$ (there is always one except in the trivial case $H = G$ , which can be checked directly) using an HSP algorithm over $G$ and thus we reduce the problem to HSP over $K$ . Nevertheless, It is not clear at all how to build an efficient oracle hiding $K$ from an oracle $f$ hiding $H$ : the natural choice for $f (g)$ would be something gathering the values of $f$ over all the cosets of $H$ inside the coset $g K$ ... but unfortunately there can be exponentially many of them! Hence, it would maybe help to consider quantum hiding functions instead. For example, the states

$∣ Ψ_{g} ⟩ = \frac{1}{\sqrt{∣ K ∣}} \sum_{k \in K} ∣ f (g k) ⟩$ satisfy the expected properties. However it is not clear how to produce $∣ Ψ_{g} ⟩$ efficiently and even less without knowing the subgroup $K$ . But it is open whether we can find another method, maybe involving other states $∣ Ψ_{g} ⟩$ .

Let's turn our attention to HSP over $G = PSL (2, q)$ (or the other groups described in the paper of Denney, Moore and Russell) and see whether we can apply a maximal subgroup reduction. Note that the group $G$ acts on the projective line $F_{q} \cup {\infty}$ and thus we can define the stabilizer $G_{a}$ of a point $a$ , which is a maximal subgroup. Now, we assume that the hidden subgroup $H$ is included in some $G_{a}$ and that we have a way to build a quantum function hiding $G_{a}$ from an oracle hiding $H$ . Note that we have the inclusions

$G_{a} \cap G_{\infty} \subseteq G_{\infty} \subseteq G$

The idea of the paper is to restrict an oracle hiding $G_{a}$ to the subgroup $G_{\infty}$ and thus get a HSP over $G_{\infty}$ with hidden subgroup $G_{a} \cap G_{\infty}$ . Now, $G_{\infty}$ is isomorphic to some "friendly" semidirect product of abelian groups and thus the authors are able to determine $G_{a} \cap G_{\infty}$ by Strong Fourier Sampling and thus find the stabilizer $G_{a}$ . Note that their algorithm still works if we use quantum hiding function instead! Hence, with the hypothesis above, we are able to determine a maximal subgroup $G_{a}$ containing $H$ . To complete the algorithm, we need to find the hidden subgroup $H$ of $G_{a} ≅ G_{\infty}$ . However, the paper describes only the case of $G_{a} \cap G_{\infty} \subseteq G_{\infty}$ and I am not sure that the authors mean they have an algorithm for finding arbitrary subgroups of $G_{\infty}$ ...

Another open question: can we generalize this maximal subgroup technique to solve HSP over $PSL (2, q)$ ? We would like a way to distinguish among exponentially many (maximal) subgroups. Note that the list of (maximal) subgroups of $PSL (2, q)$ and $PGL (2, q)$ are known (see Dickson's book). Among the exponentially large subgroups (i.e. for which we would need an efficient HSP algorithm), there are subgroups isomorphic to $PSL (2, q_{0})$ , $PGL (2, q_{0})$ or to a semidirect product of a p-group and a cyclic group (including the famous dihedral group!). Note also that $PSL (2, q)$ is a normal subgroup of $PGL (2, q)$ , and so we could also imagine the use of a quotient reduction...