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 $G$ , an unknown subgroup $H$ and an "oracle" $f$ hiding $H$ (i.e. a function on $G$ which factorizes on the coset space $G/H$ in a function with pairwise distinct values) - to determine the subgroup $H$ using a number of oracle calls polynomial in the size of $G$ .

In the standard Dedekindian HSP algorithm, $G$ is a dedekindian group and we use Fourier Sampling to measure a polynomial number of representations $\rho_{1},...\rho_{m}$ of $G$ such that $H\subseteq\operatorname{Ker}{\rho_{k}}$ . One proves that with high probability $H=\cap_{k}\operatorname{Ker}{\rho_{k}}$ . In my alternative algorithm, we measure $\rho_{1}$ and set $G_{1}=\operatorname{Ker}{\rho_{1}}$ . Then instead of continuing to work on the whole group $G$ , the idea is to move to a HSP problem on $G_{1}$ with hidden subgroup $H$ . Then do a Fourier Sampling on $G_{1}$ to move to a new subgroup $G_{2}$ and so forth. If $H\subsetneq G_{k}$ then there is a probability at least one half, that $G_{k+1}$ is at least twice smaller and so we see that we reach $H$ in an exponentially fast way.

Let’s now consider the cyclic HSP. We are given a cyclic group $G=\mathbb{Z}_{N}=\mathbb{Z}/{N\mathbb{Z}}$ and a hidden subgroup $H=d\mathbb{Z}_{N}$ for some $1\leq d\leq N$ (we exclude the case $H=0$ , which is easy) and an oracle $f$ . With this setting, one call to $f$ allows to get a Fourier sample $\lambda\frac{N}{d}$ for some random $\lambda\in\{0,1,...,d-1\}$ , with uniform probability. In the standard cyclic HSP, we repeat Fourier sampling to get $\lambda_{1}\frac{N}{d},\lambda_{2}\frac{N}{d},...\lambda_{m}\frac{N}{d}$ and deduce $d$ . For example, one can show that

P(\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 $H\subseteq G_{m}\subseteq G_{m-1}\subseteq...\subseteq G_{1}=G=\mathbb{Z}_{N}$ such that with high probability, $H=G_{m}$ . Clearly, all the $G_{k}$ ’s are cyclic groups and can be written $G_{k}=a_{k}\mathbb{Z}_{N}$ . Since they contain $H=d\mathbb{Z}_{N}$ , we have $a_{k}|d$ . From $a_{k}$ , we set $d_{k}=\frac{d}{a}_{k}$ and $N_{k}=\frac{N}{a}_{k}$ . We have the isomorphism $\phi_{k}:G_{k}\overset{\sim}{\to}\mathbb{Z}_{N_{k}}$ defined by $\phi_{k}(x)=\frac{x}{a}_{k}$ . Hence we can now work on $\mathbb{Z}_{N_{k}}$ , with a hidden subgroup $H_{k}=\phi_{k}(H)=d_{k}\mathbb{Z}_{N_{k}}$ and oracle $f_{k}=f\circ\phi_{k}^{-1}$ .

We start with $G_{1}=G=\mathbb{Z}_{N},H_{1}=H=d\mathbb{Z}_{N},a_{1}=1,d_{1}=d,N_{1}=N$ . At step $k$ , we perform a Fourier sampling that provides a random $\lambda_{k}\frac{N_{k}}{d_{k}}$ for some $\lambda_{k}\in\{0,1,...,d_{k}-1\}$ . Then, applying the Continued Fraction Algorithm on $\lambda_{k}\frac{N_{k}}{d_{k}}\frac{a_{k}}{N}=\frac{\lambda_{k}}{d_{k}}$ we get an irreducible fraction $\frac{p_{k}}{q_{k}}$ and a divisor $q_{k}$ of $d_{k}$ . Set $a_{k+1}=q_{k}a_{k}$ . Then $G_{k+1}=a_{k+1}\mathbb{Z}_{N}$ is a subgroup of $G_{k}$ . Because $q_{k}|d_{k}$ , we have ${a_{k}q_{k}}|{a_{k}d_{k}}=d$ and so $H$ is a subgroup of $G_{k+1}$ .

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

We can prove that we get the same procedure using only Fourier sampling on the initial group $G$ . Suppose we have measured Fourier samples $\lambda_{1}\frac{N}{d},\lambda_{2}\frac{N}{d},...\lambda_{m}\frac{N}{d}$ . We want to construct the same sequence $a_{k}$ . Set $a_{1}=1$ . For each $1\leq k<m$ , we let $d_{k}=\frac{d}{a}_{k}$ and compute the irreducible fraction $\lambda_{k}\frac{N}{d}\frac{a_{k}}{N}=\frac{\lambda_{k}}{d_{k}}=\frac{p_{k}}{q% _{k}}$ . As above, we have ${a_{k}q_{k}}|{a_{k}d_{k}}=d$ and set $a_{k+1}={q_{k}a_{k}}$ . Now, write the euclidean division $\lambda_{k}=d_{k}\mu_{k}+\nu_{k}$ where $\mu_{k}\in\{0,...a_{k}-1\}$ and $\nu_{k}\in\{0,...d_{k}-1\}$ (with uniform probability for $\mu_{k}$ and $\nu_{k}$ too). We have $\frac{p_{k}}{q_{k}}=\frac{\lambda_{k}}{d_{k}}=\mu_{k}+\frac{\nu_{k}}{d_{k}}$ so $q_{k}$ is actually the denominator obtained when we compute the irreducible fraction $\frac{\nu_{k}}{d_{k}}$ . With this description, it becomes obvious that the two algorithms are equivalent (where $\nu_{k}$ corresponds to $\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…