Blog de Frédéric

To content | To menu | To search

Tag - group theory

Entries feed - Comments feed

Sunday, April 22 2012

Cyclic HSP based on Subgroup Reduction

In my master thesis on quantum computing, I designed a version of the Abelian HSP algorithm based on subgroup reduction. In a previous blog post, I wondered whether this algorithm could be extended to the Dedekindian HSP and if it would be more efficient than the standard one. I’m going to prove that the latter is false in the cyclic case, where the two algorithms have exactly the same associated Markov chain.

Recall that the HSP is - given a finite group GG, an unknown subgroup HH and an "oracle" ff hiding HH (i.e. a function on GG which factorizes on the coset space G/HG/H in a function with pairwise distinct values) - to determine the subgroup HH using a number of oracle calls polynomial in the size of GG.

In the standard Dedekindian HSP algorithm, GG is a dedekind group and we use Fourier Sampling to measure a polynomial number of representations ρ1,ρm\rho _{1},...\rho _{m} of GG such that HKerρkH\subseteq\operatorname{Ker}{\rho _{k}}. One proves that with high probability H=kKerρkH=\cap _{k}\operatorname{Ker}{\rho _{k}}. In my alternative algorithm, we measure ρ1\rho _{1} and set G1=Kerρ1G_{1}=\operatorname{Ker}{\rho _{1}}. Then instead of continuing to work on the whole group GG, the idea is to move to a HSP problem on G1G_{1} with hidden subgroup HH. Then do a Fourier Sampling on G1G_{1} to move to a new subgroup G2G_{2} and so forth. If HGkH\subsetneq G_{k} then there is a probability at least one half, that Gk+1G_{{k+1}} is at least twice smaller and so we see that we reach HH in an exponentially fast way.

Let’s now consider the cyclic HSP. We are given a cyclic group G=ZN=Z/NZG=\mathbb{Z}_{N}=\mathbb{Z}/{N\mathbb{Z}} and a hidden subgroup H=dZNH=d\mathbb{Z}_{N} for some 1dN1\leq d\leq N and an oracle ff. With this setting, one call to ff allows to get a Fourier sample λNd\lambda\frac{N}{d} for some random λ0,1,,d-1\lambda\in\{ 0,1,...,d-1\}, with uniform probability. In the standard cyclic HSP, we repeat Fourier sampling to get λ1Nd,λ2Nd,λmNd\lambda _{1}\frac{N}{d},\lambda _{2}\frac{N}{d},...\lambda _{m}\frac{N}{d} and deduce dd. For example, one can show that

P(Ngcd(λkNd)1km=d)1-2-m/2P(\frac{N}{\operatorname{gcd}{\left(\lambda _{k}\frac{N}{d}\right)}_{{1\leq k\leq m}}}=d)\geq 1-2^{{-m/2}}

In the algorithm I proposed, we build a sequence of polynomial length HGmGm-1G1=G=ZNH\subseteq G_{m}\subseteq G_{{m-1}}\subseteq...\subseteq G_{1}=G=\mathbb{Z}_{N} such that with high probability, H=GmH=G_{m}. Clearly, all the GkG_{k}’s are cyclic groups and can be written Gk=akZNG_{k}=a_{k}\mathbb{Z}_{N}. Since they contain H=dZNH=d\mathbb{Z}_{N}, we have ak|da_{k}|d. From aka_{k}, we set dk=dakd_{k}=\frac{d}{a}_{k} and Nk=NakN_{k}=\frac{N}{a}_{k}. We have the isomorphism ϕk:GkZNk\phi _{k}:G_{k}\overset{\sim}{\to}\mathbb{Z}_{{N_{k}}} defined by ϕkx=xak\phi _{k}(x)=\frac{x}{a}_{k}. Hence we can now work on ZNk\mathbb{Z}_{{N_{k}}}, with a hidden subgroup Hk=ϕkH=dkZNkH_{k}=\phi _{k}(H)=d_{k}\mathbb{Z}_{{N_{k}}} and oracle fk=fϕk-1f_{k}=f\circ\phi _{k}^{{-1}}.

We start with G1=G=ZN,H1=H=dZN,a1=1,d1=d,N1=NG_{1}=G=\mathbb{Z}_{N},H_{1}=H=d\mathbb{Z}_{N},a_{1}=1,d_{1}=d,N_{1}=N. At step kk, we perform a Fourier sampling that provides a random λkNkdk\lambda _{k}\frac{N_{k}}{d_{k}} for some λk0,1,,dk-1\lambda _{k}\in\{ 0,1,...,d_{k}-1\}. Then, applying the Continued Fraction Algorithm on λkNkdkakN=λkdk\lambda _{k}\frac{N_{k}}{d_{k}}\frac{a_{k}}{N}=\frac{\lambda _{k}}{d_{k}} we get an irreducible fraction pkqk\frac{p_{k}}{q_{k}} and a divisor qkq_{k} of dkd_{k}. Set ak+1=qkaka_{{k+1}}=q_{k}a_{k}. Then Gk+1=ak+1ZNG_{{k+1}}=a_{{k+1}}\mathbb{Z}_{N} is a subgroup of GkG_{k}. Because qk|dkq_{k}|d_{k}, we have akqk|akdk=d{a_{k}q_{k}}|{a_{k}d_{k}}=d and so HH is a subgroup of Gk+1G_{{k+1}}.

The general remark about the algorithm being exponentially fast is easy to see in the cyclic case. Indeed if qk=1q_{k}=1 above, then λk=pkdk\lambda _{k}=p_{k}d_{k} which happens only if λk=0\lambda _{k}=0. If at step kk, we have HGkH\subsetneq G_{k} then λk\lambda _{k} can take a non-zero value with probability at least one half. In that case qk2q_{k}\geq 2 and ak+12aka_{{k+1}}\geq 2a_{k}. Hence aka_{k} grows exponentially fast until it becomes stationary and thus am=da_{m}=d with very high probability.

We can prove that we get the same procedure using only Fourier sampling on the initial group GG. Suppose we have measured Fourier samples λ1Nd,λ2Nd,λmNd\lambda _{1}\frac{N}{d},\lambda _{2}\frac{N}{d},...\lambda _{m}\frac{N}{d}. We want to construct the same sequence aka_{k}. Set a1=1a_{1}=1. For each 1k<m1\leq k<m, we let dk=dakd_{k}=\frac{d}{a}_{k} and compute the irreducible fraction λkNdakN=λkdk=pkqk\lambda _{k}\frac{N}{d}\frac{a_{k}}{N}=\frac{\lambda _{k}}{d_{k}}=\frac{p_{k}}{q_{k}}. As above, we have akqk|akdk=d{a_{k}q_{k}}|{a_{k}d_{k}}=d and set ak+1=qkaka_{{k+1}}={q_{k}a_{k}}. Now, write the euclidean division λk=dkμk+νk\lambda _{k}=d_{k}\mu _{k}+\nu _{k} where μk0,ak-1\mu _{k}\in\{ 0,...a_{k}-1\} and νk0,dk-1\nu _{k}\in\{ 0,...d_{k}-1\} (with uniform probability for μk\mu _{k} and νk\nu _{k} too). We have pkqk=λkdk=μk+νkdk\frac{p_{k}}{q_{k}}=\frac{\lambda _{k}}{d_{k}}=\mu _{k}+\frac{\nu _{k}}{d_{k}} so qkq_{k} is actually the denominator obtained when we compute the irreducible fraction νkdk\frac{\nu _{k}}{d_{k}}. With this description, it becomes obvious that the two algorithms are equivalent (where νk\nu _{k} corresponds to λk\lambda _{k} in the previous algorithm).

I conjecture that the same phenomenon happens for a general Dedekindian group, but this may be more difficult to write down…

Friday, December 10 2010

Maximal Subgroup Reduction and HSP over Projective Linear Groups

-- 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 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 = 1 K k 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 { } 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 G G G

The idea of the paper is to restrict an oracle hiding G a to the subgroup G and thus get a HSP over G with hidden subgroup G a G . Now, G is isomorphic to some "friendly" semidirect product of abelian groups and thus the authors are able to determine G a G 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 . However, the paper describes only the case of G a G G and I am not sure that the authors mean they have an algorithm for finding arbitrary subgroups of G ...

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...

Wednesday, December 1 2010

Can transfinite numbers be extended to more general algebraic structures?

Infinite ordinals and cardinals are beautiful mathematical objects, extending in a natural way and sharing most of its properties. I have always wondered whether it would be possible to generalize the constructions of or to get transfinite integers or rationals. In general, putting a group structure on classes extending Ord or Card is not possible as I indicated some years ago (fr). Basically, we would have 1 + 0 = 0 (and also 1 + ω = ω ) which would imply 1 = 0 . However, we can consider a slightly modified problem with weaker constraints, as follows. First we assume we have a class of cardinals C Card containing zero and stable by addition.

(1) { 0 C κ , λ C , κ + λ C

We define the class Z C = C C , where C = { κ κ C , κ 0 } is a representation of "negative" cardinals. As we have seen, the class Z C need not be a group. Nevertheless, we can try to find an equivalence class R over Z C such that G C = Z C R is a group. Moreover, we want this equivalence class to be compatible with addition and opposite i.e.

(2) κ , λ C , κ + λ ¯ = κ ¯ + λ ¯ κ C , κ ¯ = κ ¯

Of course this implies that 0 ¯ is the identity element 0 of the expected group. Similarly, we can settle the same problem for a class C Ord and + is now understood as the ordinal addition. Can we follow this schema to contruct interesting infinite algebraic structures?

For C Card , we have for any infinite κ C the relation κ ¯ = κ + κ ¯ = κ ¯ + κ ¯ so κ ¯ = 0 . Hence G C ω = G C and the initial problem is reduced to the case where C ω contains only finite cardinals (= finite ordinals) and so the problem is still not really exciting. What about the case C Ord ? In general it is possible to have β 1 + γ = β 2 + γ without β 1 , β 2 being equal and so for any α such that β 1 α , β 2 α , γα C , we get that β 1 α ¯ = β 2 α ¯ . In particular for any infinite ordinal γ and α C such that γα C we obtain α ¯ = 0 because 1 + γ = γ (if this is not obvious to you, a more general statement is proved below). As a consequence, more general assumptions on the class C strongly limit the structure of the group. For example if C is closed under an infinite sum ( C = Ord for example) then G C is trivial. Similarly, if we require C to be stable by multiplication (in order to define a ring structure for example) then G C is trivial whenever C contains an infinite ordinal γ (hence the remaining case is again C ω ). If G C is not trivial, we denote α 0 C the least element such that α 0 ¯ 0 (in particular α 0 > 0 ).

One additional natural hypothesis should be added. We know that for any ordinal α < β there exists a unique ordinal γ such that α = β + γ . We would very like γ ¯ to match the difference " β ¯ + α ¯ ". For that purpose, we only require γ to belong to C . Hence we assume that

(3) α , β C , γ Ord , α = β + γ γ C

Let's come back to the case C ω with the new assumption (3) and suppose that G C is not trivial. Then α 0 < ω and any finite m C and be written m = α 0 q + r with r < α 0 . By (3), r C and because C is stable by finite sums, m ¯ = α 0 ¯ q + r ¯ = α 0 ¯ q . Thus G C is the monogenic group generated by α 0 ¯ .

What about the general case? Unfortunately, it turns out that if G C is not trivial it is still a monogenic group generated by α 0 ¯ . To prove this, we need to recall some equalities on ordinals. First, for any α > 0 , we have 1 + ω α = ω α . This is clearly true for α = 1 and we prove the general case by induction on α : 1 + ω α + 1 = 1 + ω ω α = 1 + ( 1 + ω ) ω α = ( 1 + ω α ) + ω α + 1 = ω α + ω α + 1 = ( 1 + ω ) ω α = ω ω α = ω α + 1 and 1 + ω λ = sup 0 < α < λ ( 1 + ω α ) = sup 0 < α < λ ω α = ω λ . Now, if we have two ordinals α < β and if γ > 0 is such that β = α + γ we have ω α + ω β = ω α ( 1 + ω γ ) = ω α ω γ = ω β . Finally, if we have two ordinals γ 1 < γ 2 we can write their Cantor Normal Forms:

(4) γ 1 = ω β 1 1 k 1 1 + ω β 2 1 k 2 1 + + ω β n 1 k n 1 γ 2 = ω β 1 2 k 1 2 + ω β 2 2 k 2 2 + + ω β n 2 k m 2

where β 1 2 β 1 i > β 2 i > > β 2 i and k j i are positive integers. Using the equality ω α + ω β = ω β for α < β it is clear that γ 1 + γ 2 = γ 2 if β 1 2 > β 1 1 .

Now our element α 0 C can be written α 0 = ω β k + γ where ω β k is the first term of its Cantor Normal Form. For any δ C , we can write its euclidean division by α 0 : δ = α 0 l + ε where ε < α 0 . By the previous discussion, if l ω then we can write the Cantor Normal Forms of the two elements α 0 < δ as in (4) and see that β 1 2 > β 1 1 . Hence α 0 + δ = δ and so α 0 ¯ = 0 , which is a contradiction. So l < ω and because C is stable by finite sums, α 0 l C and by the property (3) we get ε C . This means that δ ¯ = α 0 ¯ l + ε ¯ = α 0 ¯ l and hence G C is generated by α 0 ¯ as claimed above.

As a conclusion, if C Card satisfies the properties (1), (2) above and G C = Z C R is a group then C ω Ord . If C Ord satisfies properties (1), (2), (3) above and G C = Z C R is a group then G C is isomorphic to or to n . Conversely, we can build these groups from C = ω by defining the relation R as the equality (respectively the equality modulo n ). But we do not get any new groups...

Thursday, August 5 2010

Two Open Problems for the Subgroup-Reduction based Dedekindian HSP Algorithm

One of my main idea after having studied the Hidden Subgroup Problem is that subgroup simplification is likely to play an important role. Basically, rather than directly finding the hidden subgroup H by working on the whole initial group G , we only try to get partial information on H in a first time. This information allows us to move to a simpler HSP problem and we can iterate this process until the complete determination of H . Several reductions of this kind exist and I think the sophisticated solution to HSP over 2-nil groups illustrates well how this technique can be efficient.

Using only subgroup reduction, I've been able to design an alternative algorithm for the Dedekindian HSP i.e. over groups that have only normal subgroups. Recall that the standard Dedekindian HSP algorithm is to use Weak Fourier Sampling, measure a polynomial number of representations ρ 1 , , ρ m and then get with high probability the hidden subgroup as the intersection of kernels H = i Ker ρ i . When the group is dedekindian, we always have H Ker ρ i . Hence my alternative algorithm is rather to start by measuring one representation ρ 1 , move the problem to HSP over Ker ρ 1 and iterate this procedure. I've been able to show that we reach the group H after a polynomial number of steps, the idea being that when we measure a non-trivial representation the size of the underlying group becomes at least twice smaller. One difficulty of this approach is to determine the structure of the new group Ker ρ i so that we can work on it. However, for the cyclic case this is determination is trivial and for the abelian case I've used the group decomposition algorithm, based on the cyclic HSP. Finally I've two open questions:

  1. Can my algorithm work for the Hamiltonian HSP i.e. over non-abelian dedekindian groups?
  2. Is my algorithm more efficient than the standard Dedekindian HSP?

For the first question, I'm pretty sure that the answer is positive, but I admit that I've not really thought about it. For the second one, it depends on what we mean by more efficient. The decomposition of the kernel seems to increase the time complexity but since we are working on smaller and smaller groups, we decrease the space complexity. However, if we are only considering the numbers of sample, my conjecture is that both algorithms have the same complexity and more precisely yield the same markov process. In order to illustrate this, let's consider the cyclic case G = 18 and H = 6 18 . The markov chain of the my alternative algorithm is given by the graph below, where the edge labels are of course probabilities and the node labels are the underlying group. We start at G = 18 and want to reach H 3 .

1 Z18 1->1 1/6 2 Z9 1->2 1/6 3 Z6 1->3 1/3 4 Z3 1->4 1/3 2->2 1/3 2->4 2/3 3->3 1/2 3->4 1/2 4->4 1

One can think that moving to smaller and smaller subgroups will be faster than the standard algorithm which always works on 18 . However, it turns out that the markov chain of the standard algorithm is exactly the same. The point being that while it is true that working over 9 or 6 provides less possibilities of samples (3 and 2 respectively, instead of 6 for 18 ) the repartition of "good" and "bad" samples is the same and thus we get the same transition probabilities. I guess it would be possible to formalize this for a general cyclic group. The general abelian case seems more difficult, but I'm sure that the same phenomenon can be observed.

Friday, July 30 2010

Master's Project - The Hidden Subgroup Problem

I've submitted my report on The Hidden Subgroup Problem to and I expect it to be published soon.

Comments are welcome on this blog entry.

--update 03/08/2010: a pdf version is available on You can still find a Web version as well as my slides on my website.

- page 1 of 2