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 ith 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.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s