1
$\begingroup$

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|}}$

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

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ the solution of hsp asume we know the order of the group but in fact we don't $\endgroup$
    – tangyao
    Commented May 3 at 0:13
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.