The hidden subgroup problem for finite abelian groups

In this post, we’ll talk about a generalization of Shor’s algorithm that I talked about in a previous post. The generalization discussed is a very powerful one, as we’ll see in the next paragraph.

Let $G$ be a finite group. The hidden subgroup problem (HSP) is the following. Given a map $f:G\to R$, such that $f(x) = f(y)$ if and only if $x+H = y+H$ for some subgroup $H\leq G$, using only queries of $f$, find the subgroup $H$. Therefore $f$ is constant on left cosets of $H$, and distinct on different left cosets. This problem subsumes multiple classical problems: If $G = (\mathbf{Z}/2\mathbf{Z})^n$ and $R = \{0,x\}$ for some $x\in(\mathbf{Z}/2\mathbf{Z})^n$, this reduces to Simon’s problem. If $G = \mathbf{Z}$, and $f:\mathbf{Z}\to\mathbf{Z}/N\mathbf{Z}$ is defined via $f(x) = a^x\bmod N$ for some $a\in(\mathbf{Z}/N\mathbf{Z})^\times$, and the HSP reduces to finding the period of $f$, which is (the quantum part of) Shor’s algorithm. If $N>0$, $g$ is a generator of $(\mathbf{Z}/N\mathbf{Z})^\times$, $a\in(\mathbf{Z}/N\mathbf{Z})^\times$, $R = |(\mathbf{Z}/N\mathbf{Z})^\times|$, find $k$ such that $g^k = a$. (This is the discrete logarithm problem.) Define $f:\mathbf{Z}/R\mathbf{Z}\times\mathbf{Z}/R\mathbf{Z}\to\mathbf{Z}/N\mathbf{Z}$ defined by $(x,y)\mapsto a^xg^y\bmod N$; this is constant on $\langle (1,-k)\rangle$. Lastly, let $(V,E)$ be a graph $\Gamma$, with $n=|V|$. Finding generators for $\mathrm{Aut}(\Gamma)$ is the graph automorphism problem. Let $S_n$ be the symmetric group on $n$ letters. Define $f:S_n\to\mathrm{Aut}(\Gamma)$ as $f:\sigma\mapsto\sigma(\Gamma)$. Then the solution to the hidden subgroup problem for $f$ is $\mathrm{Aut}(\Gamma)$. This is consistent with our use of left cosets, because $S_n$ is not abelian for $n\geq 3$ (so an arbitrary subgroup of $S_n$ need not be normal). Solving the HSP for finite abelian groups also breaks elliptic curve cryptography systems. (This leads to interesting post-quantum cryptography.)

Suppose $G$ is finite abelian, and let $\widehat{G}$ denote the set of irreducible representations of $G$. The quantum Fourier transform takes:

$\displaystyle|g\rangle\mapsto \frac{1}{\sqrt{|G|}}\sum_{\psi\in\widehat{G}}\psi(g)|\psi\rangle$

A classical result is that $|\widehat{G}|$ is the number of conjugacy classes of $G$. In particular, if $G$ is abelian, then $|\widehat{G}| = |G|$. If $g\in G$, denote by $\psi_g$ the correponding character in $\widehat{G}$. Since $G$ is finite abelian, it is isomorphic to the product $\prod^k_{i=1}\mathbf{Z}/N_i\mathbf{Z}$. Therefore, $\displaystyle\widehat{G} = \left\{\psi_t(g) = \exp\left(2\pi i\sum^k_{i=1}\frac{t_ig_i}{N_i}\right)|t_i,g_i\in\mathbf{Z}/N_i\mathbf{Z}\right\}$, where $(t_1,\cdots,t_k)$ and $(g_1,\cdots,g_k)$ are elements of $G$ under the isomorphism $G\cong \prod^k_{i=1}\mathbf{Z}/N_i\mathbf{Z}$. We can finally begin talking about the algorithm, which you will notice is very similar to Shor’s algorithm.

Start off with the initial state

$\displaystyle \frac{1}{\sqrt{|G|}}\sum_{g\in G}|g\rangle |0\rangle$

Now evaluate $f$; this shifts the quantum system into:

$\displaystyle \frac{1}{\sqrt{|G|}}\sum_{g\in G}|g\rangle |f(g)\rangle$

Measure the second register. With probability $|H|/|G| = |G/H|$, the system collapses to:

$\displaystyle \frac{1}{\sqrt{|H|}}\sum_{h\in H}|r+h\rangle |f(r)\rangle$

Here $r$ represents some coset of $H$. We can discard $|f(r)\rangle$, so the system is $\frac{1}{\sqrt{|H|}}\sum_{h\in H}|r+h\rangle$. Let’s now apply the quantum Fourier transform. This shifts the system into:

$\displaystyle \frac{1}{\sqrt{|H|\cdot|G|}}\sum_{h\in H}\sum_{\psi\in\widehat{G}}\psi(r+h)|\psi\rangle = \frac{1}{\sqrt{|G|}}\sum_{\psi\in\widehat{G}}|\psi\rangle\psi(r)\left(\frac{1}{\sqrt{|H|}}\sum_{h\in H}\psi(h)\right)$

Let us now evaluate the expression in the parentheses. If $\psi$ is trivial on $H$, then $\frac{1}{\sqrt{|H|}}\sum_{h\in H}\psi(h) = \frac{1}{\sqrt{|H|}}\sum_{h\in H}1 = \sqrt{|H|}$. If $\psi$ is not trivial on $H$, then:

$\displaystyle \frac{1}{\sqrt{|H|}}\sum_{h\in H}\psi(h) = \frac{1}{\sqrt{|H|}}\sum_{h\in H}\chi_{\mathbf{1}}(h)\chi_\psi(h)$

Where $\chi_{\mathbf{1}}$ is the trivial character on $H$, and $\chi_\psi$ is the character associated to $\psi$. Since both are irreducible (recall $\psi\in\widehat{G}$), and irreducible characters are orthogonal, this evaluates to $0$. Since characters that are trivial on $H$ are in bijection with characters of $G/H$ (proof is left as a (pretty trivial) exercise), we see that:

$\displaystyle\frac{1}{\sqrt{|G|}}\sum_{\psi\in\widehat{G}}|\psi\rangle\psi(r)\left(\frac{1}{\sqrt{|H|}}\sum_{h\in H}\psi(h)\right) = \sum_{\psi\in\widehat{G/H}}\left(\sqrt{\frac{|H|}{|G|}}\psi(r)\right)|\psi\rangle$

Measuring this state gives a certain $\psi\in\widehat{G/H}$ with probability:

$\displaystyle \left|\sqrt{\frac{|H|}{|G|}}\psi(r)\right|^2 = \frac{|H|}{|G|}.$

This collapses the system to $|\psi\rangle$, and since we observed $r$ with probability $|H|/|G|$, the probability of the system collapsing to $r$ and $\psi$ is $|H|^2/|G|^2$. Since the final state doesn’t depend on $r$, though, the actual probability of the system collapsing to $\psi$ is $|H|^2/|G|^2\times [H:G] = |H|^2/|G|^2\times |G|/|H| = |H|/|G|$.

We’ll need the following lemma for our discussion, which I won’t provide a rigorous proof of.

Lemma: Let $G$ be a finite group. Choosing $t+\left \lceil{\log|G|}\right \rceil$ elements of $G$ uniformly at random will generate $G$ with probability $1-\frac{1}{2^t}$.

Proof sketch. The idea of proof is to show, via induction, that if $|G|\leq 2^r$, then choosing $t$ elements of $G$ generates $G$ with a higher probability than choosing $t$ elements of $(\mathbf{Z}/2\mathbf{Z})^r$, and then showing that choosing $r+t$ elements of $(\mathbf{Z}/2\mathbf{Z})^r$ generates $(\mathbf{Z}/2\mathbf{Z})^r$ with probability $1-\frac{1}{2^t}$, which can be proved by viewing $(\mathbf{Z}/2\mathbf{Z})^r$ as an $r$-dimensional $\mathbf{Z}/2\mathbf{Z}$-vector space, which reduces to finding the probability that an $(r+t)\times r$ matrix has rank $r$.

Consider finite abelian $G\cong\prod^k_{i=1}\mathbf{Z}/N_i\mathbf{Z}$. Let $T$ be the matrix with $i$th row given by $\left(\frac{t_{i_1}}{N_1},\cdots,\frac{t_{i_k}}{N_k}\right)$. Sample $t+\left \lceil{\log|G|}\right \rceil$ solutions $Tx = 0\bmod\mathrm{lcm}(N_1,\cdots,N_k)$. Running the above algorithm $t+\left \lceil{\log|G|}\right \rceil$ times gives elements of $H^\perp = \{g\in G|\chi_g(h) = 1\text{ for all }h\in H\}$. Now, $(H^\perp)^\perp = H$, so this determines $H$ uniquely with probability $1-1/2^t$. Choosing $t = \left \lceil{\log|G|}\right \rceil + 1$ gives the generators with probability $1-1/|G|$. Each iteration of the algorithm (to produce elements of $H^\perp$) used only one query, so the query complexity is $O(\log|G|)$, and solving the matrix equation gives a total time of $O(\mathrm{poly}(\log|G|))$. This is significantly faster than the classical algorithms. How do we solve the case of nonabelian finite groups, like $S_n$? I’ll talk about this in the next post.

Best,
SKD