# What are the ambient group $G$ and the hidden subgroup $H$ in Shor's order finding algorithm?

It is widely believed that Shor's order-finding algorithm is an example of hidden subgroup problem. However, there is a little trick here. The problem is what is the hidden subgroup in Shor's order finding algorithm?

In the order-finding algorithm, we try to find the period $$P$$ which is the smallest number satisfy $$a^P=1 \pmod N$$ and it is said in some book that the circuit will use $$n$$-qubit such that $$Q=2^n\geq N^2$$ so we have three numbers:$$1.Q, 2.N$$ 3.$$\psi(N)$$, while $$\psi$$ is the euler totient function.

So what is group here, since $$f(x)$$ is defined to be $$f(x)=a^x\pmod N$$. And $$f(x)$$ is constant on each coset of the hidden group. So this group should be $$Z_{\psi(N)}$$ we see that $$f(P)=f(2P)=...$$ the group should have $$P$$ cosets, the representation of them are $$0,1,...,P-1$$ since $$a^0,a^1,...,a^{P-1}$$ are different mod N. And since $$P|\psi(N)$$, so the group should be $$Z_{\psi{N}}$$ the hidden group is $$\{0,P,2P,...,\psi(N)-P\}$$.

However, in that aglrotihm, $$\psi(N)$$ didn't appear at all. But may papers said the group is $$Z_Q$$,or $$Z_N$$, and the qft is acted on $$Z_Q$$ not $$Z_{\psi(N)}$$. So this makes the general framework of hidden subgroup problem doesn't fit the Shor's order-finding algorithm well.

To make things clearer, my issue is that in Shor's algorithm, it use a QFT with $$e^{\frac{j2\pi}{Q}}$$,but $$Q$$ is not the order of the group $$Z_{\psi(N)}$$, this is not consistent with the framework of the HSP, which use a QFT with $$e^{\frac{j2\pi}{|G|}}$$

• Euler's totient function is usually $\phi$, not $\psi$. Commented Apr 24 at 14:10

TL;DR: There are a few slightly different ways to cast period-finding as a Hidden Subgroup Problem (HSP). The conceptually simplest formulation uses $$G=\mathbb{Z}$$, but it is not practical from quantum programmer's perspective since then $$G$$ has $$\aleph_0$$ elements$$^1$$. We can preserve conceptual simplicity with a finite group by setting $$G=\mathbb{Z}_{rd}$$ where $$d$$ is any positive integer and $$r$$ is the order of the given $$a\in\mathbb{Z}_N^\times$$. In the context of Shor's algorithm, $$N$$ is the integer to be factored and $$a\in\{2,\dots,N-1\}$$ is a randomly chosen integer. Anyway, this is of course rather unsatisfying since $$r$$ is what we're trying to compute. Finally, it turns out that we can arrive at a practical algorithm by replacing $$\mathbb{Z}_{rd}$$ with $$\mathbb{Z}_{q}$$ for a sufficiently large integer $$q$$. In this last formulation, period finding is no longer strictly speaking an instance of the HSP, but it is a good approximation (in terms of output probabilities). Below, I briefly describe the two formulations of period finding as an HSP.

## Hidden Subgroup Problem

We say that a function $$f:G\to X$$ from a finitely generated group $$G$$ to a finite set $$X$$ hides the subgroup $$H\subset G$$ if $$f(g_1)=f(g_2)\iff g_1g_2^{-1}\in H$$. Then, the Hidden Subgroup Problem is the following: given access to an oracle for $$f$$, find a subset of $$G$$ that generates the hidden subgroup $$H$$.

## Period finding problem

Given an element $$k\in K$$ of a finite group $$K$$, find the smallest positive integer $$r$$ such that $$k^r=e$$ where $$e\in K$$ is the neutral element of $$K$$. In Shor's algorithm $$K=\mathbb{Z}_N^\times$$, the multiplicative group of integers modulo $$N$$ whose order is $$\varphi(N)$$, the Euler's totient function.

## Period finding as HSP in an infinite group

Set $$G=(\mathbb{Z},+)$$ and define $$f:G\to K$$ by $$f_k(n)=k^n$$. Note that $$H=r\mathbb{Z}$$ is a subgroup of $$G$$. Moreover, $$k^{n_1}=k^{n_2}$$ if and only if $$n_1-n_2\in H$$, so $$f$$ hides $$H$$. Finally, from the knowledge of a generating set for $$H$$, such as say $$\{r\}$$ or $$\{6r, 35r\}$$, we can efficiently recover the period $$r$$.

## Period finding as HSP in a finite group

Set $$G=(\mathbb{Z}_{rd},+)$$ and define $$f:G\to K$$ by $$f_k(n)=k^n$$ as before. In the context of Shor's algorithm, Lagrange theorem implies that $$r$$ divides $$\varphi(N)$$, so we can indeed choose $$d$$ so that $$rd=\varphi(N)$$ as anticipated in the question, but this is not necessary. Anyway, similarly to the infinite case, $$H=r\mathbb{Z}_d$$ is a subgroup of $$G$$. Moreover $$k^{n_1}=k^{n_2}$$ if and only if $$n_1-n_2\in r\mathbb{Z}_d$$, so $$f$$ hides $$H$$. Once again, from the knowledge of a generating set for $$H$$, such as say $$\{r\}$$ or $$\{2r, 3r\}$$, we can recover $$r$$.

$$^1$$ An even more important complication is that the dual group $$\widehat{\mathbb{Z}}$$ of $$\mathbb{Z}$$ is the circle group $$\mathbb{T}$$, in contrast to the finite case where $$\widehat{G}$$ and $$G$$ are isomorphic.

• the solution of hsp asume we know the order of the group but in fact we don't Commented May 3 at 0:13

The group is $$G=(\{1,...,\phi(N)\},+)$$, and the subgroup is $$H=$$, where $$r$$ is the period of the function $$f$$.