Frédéric Wang Yet another non-exponentially growing weblog

About Me  Blog Archive

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 this 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 dedekindian 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=N=/NG=\mathbb{Z}_{N}=\mathbb{Z}/{N\mathbb{Z}} and a hidden subgroup H=dNH=d\mathbb{Z}_{N} for some 1dN1\leq d\leq N (we exclude the case H=0H=0, which is easy) 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}{\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=NH\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=akNG_{k}=a_{k}\mathbb{Z}_{N}. Since they contain H=dNH=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:GkNk\phi_{k}:G_{k}\overset{\sim}{\to}\mathbb{Z}_{N_{k}} defined by ϕk(x)=xak\phi_{k}(x)=\frac{x}{a}_{k}. Hence we can now work on Nk\mathbb{Z}_{N_{k}}, with a hidden subgroup Hk=ϕk(H)=dkNkH_{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=N,H1=H=dN,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 λk{0,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+1NG_{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 μk{0,ak-1}\mu_{k}\in\{0,...a_{k}-1\} and νk{0,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 it down…