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 be a finite group. The hidden subgroup problem (HSP) is the following. Given a map , such that if and only if for some subgroup , using only queries of , find the subgroup . Therefore is constant on left cosets of , and distinct on different left cosets. This problem subsumes multiple classical problems: If and for some , this reduces to Simon’s problem. If , and is defined via for some , and the HSP reduces to finding the period of , which is (the quantum part of) Shor’s algorithm. If , is a generator of , , , find such that . (This is the discrete logarithm problem.) Define defined by ; this is constant on . Lastly, let be a graph , with . Finding generators for is the graph automorphism problem. Let be the symmetric group on letters. Define as . Then the solution to the hidden subgroup problem for is . This is consistent with our use of left cosets, because is not abelian for (so an arbitrary subgroup of 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 is finite abelian, and let denote the set of irreducible representations of . The quantum Fourier transform takes:
A classical result is that is the number of conjugacy classes of . In particular, if is abelian, then . If , denote by the correponding character in . Since is finite abelian, it is isomorphic to the product . Therefore, , where and are elements of under the isomorphism . 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
Now evaluate ; this shifts the quantum system into:
Measure the second register. With probability , the system collapses to:
Here represents some coset of . We can discard , so the system is . Let’s now apply the quantum Fourier transform. This shifts the system into:
Let us now evaluate the expression in the parentheses. If is trivial on , then . If is not trivial on , then:
Where is the trivial character on , and is the character associated to . Since both are irreducible (recall ), and irreducible characters are orthogonal, this evaluates to . Since characters that are trivial on are in bijection with characters of (proof is left as a (pretty trivial) exercise), we see that:
Measuring this state gives a certain with probability:
This collapses the system to , and since we observed with probability , the probability of the system collapsing to and is . Since the final state doesn’t depend on , though, the actual probability of the system collapsing to is .
We’ll need the following lemma for our discussion, which I won’t provide a rigorous proof of.
Lemma: Let be a finite group. Choosing elements of uniformly at random will generate with probability .
Proof sketch. The idea of proof is to show, via induction, that if , then choosing elements of generates with a higher probability than choosing elements of , and then showing that choosing elements of generates with probability , which can be proved by viewing as an -dimensional -vector space, which reduces to finding the probability that an matrix has rank .
Consider finite abelian . Let be the matrix with th row given by . Sample solutions . Running the above algorithm times gives elements of . Now, , so this determines uniquely with probability . Choosing gives the generators with probability . Each iteration of the algorithm (to produce elements of ) used only one query, so the query complexity is , and solving the matrix equation gives a total time of . This is significantly faster than the classical algorithms. How do we solve the case of nonabelian finite groups, like ? I’ll talk about this in the next post.