The Hidden Subgroup Problem
Introduction
Two of the best-known quantum algorithms are Shor’s algorithms for integer factorization and discrete logarithms. Their importance lies in the fact that an efficient factoring algorithm breaks RSA, while an efficient discrete log algorithm breaks the Diffie-Hellman key exchange.
This naturally leads to a question: are there other problems that are considered hard for classical computers, but can be solved efficiently using quantum algorithms?
As it turns out, both factoring and the discrete logarithm problem are special cases of a more general framework known as the Hidden Subgroup Problem (HSP). In fact, Shor’s algorithms are specific instances of a broader quantum approach to solving the HSP in commutative (abelian) groups.
Moreover, nearly all quantum algorithms that show exponential speedups over classical ones can be described as solutions to the HSP in abelian settings.
In this post, we will introduce the HSP and describe the quantum algorithm that efficiently solves it when the group is abelian. We will also look at how this framework applies to Simon’s Problem and the Discrete Logarithm Problem.
The Hidden Subgroup Problem
We begin by formally defining the HSP and exploring how it generalizes several foundational problems in quantum computing.
We start with the concept of a function hiding a subgroup.
Definition (Hiding a Subgroup)
Let G be a finite group and H a subgroup of G. Let X be a set and let f be a function from G to X. We say that f hides H if for all elements g1 and g2 in G, f(g1) equals f(g2) if and only if g1 and g2 are in the same left coset of H.
In simpler terms, f hides H if it defines a one to one mapping on the cosets of H.
The HSP asks us to find the hidden subgroup H, given access to a black box function f that hides it.
Definition (HSP)
Given a finite group G, a subgroup H, and a function f from G to a set X that hides H, the goal is to find a generating set for H using evaluations of the black box function f.
A brute force method can always solve the HSP using a number of evaluations equal to the size of G. One can compute f for each element of G and look for repeated values to identify the subgroup structure.
The more interesting question is whether there is a more efficient way to find H.
When G is abelian, there is a powerful method known as the standard method that solves the HSP using only a polynomial number of evaluations of f. For many such cases, the best known classical algorithms require exponentially more work.
Let’s now look at two important examples of the abelian HSP, then describe the standard method and apply it to both.
Simon’s Problem
Simon’s Problem was introduced by Daniel Simon in 1994. It served as an early example of a problem that is hard for classical computers but easy for quantum ones.
Let G be the group of n-bit binary strings with addition defined as bitwise XOR.
For example, if n equals 3, then the strings 101 and 011 belong to G, and their XOR is 110.
Simon’s problem is as follows:
We are given a black box that implements a function f from G to some set X. We are promised that there exists a secret string s such that for any pair of inputs x1 and x2, f(x1) equals f(x2) if and only if x1 XOR x2 equals s or zero. Our task is to discover s using as few queries to f as possible.
To understand this, suppose we define a function f on G such that f(x) equals f(x XOR s), for some secret s. The function is then two to one, and we can think of s as a kind of “bitmask” that tells us how the inputs are paired.
Solving Simon’s problem classically is hard. Without knowing anything about f or s, we must compute f on random inputs until we find a duplicate value. Based on the birthday paradox, we would need to evaluate f about the square root of the size of G times to find a match, which is exponential in n.
Simon’s quantum algorithm, however, solves the problem in polynomial time. The improvement is exponential.
To see how Simon’s problem fits into the HSP framework, define a subgroup H of G where H contains two elements: the identity and the secret string s. It is then clear that f hides H. Solving the HSP for this group and function recovers Simon’s algorithm.
Discrete Logarithms
Let p be a prime number and let G be the multiplicative group of integers modulo p. Suppose g is a generator of this group. That means every element in G can be written as g raised to some power.
Given an element x in the group, the discrete logarithm of x with respect to g is the exponent r such that g to the r equals x modulo p.
The discrete log problem asks us to compute r given g and x. This is classically hard and forms the basis of cryptographic systems like Diffie-Hellman.
To cast this problem as an HSP, define a function f on pairs of integers that sends (a, b) to g to the a times x to the minus b modulo p.
This function is a group homomorphism and its kernel contains all pairs (a, b) such that g to the a equals x to the b. If r is the discrete logarithm of x base g, then the kernel includes all scalar multiples of the vector (r, 1).
In this way, f hides a subgroup generated by the vector (r, 1), and solving the HSP for this function reveals the value of r.
The Standard Method
Let’s now look at the quantum algorithm known as the standard method, which efficiently solves the HSP for abelian groups.
Given a group G, we consider the vector space where each element of G is represented as a basis vector. Denote this by the notation used in quantum computing, where the basis vector corresponding to an element g is written as |g⟩.
The first step of the algorithm is to create a uniform superposition over all group elements:
(1 / sqrt(|G|)) * sum over g in G of |g⟩
We then apply the function f as a black box to each g, entangling the result with a second register:
(1 / sqrt(|G|)) * sum over g in G of |g⟩|f(g)⟩
Next, we measure the second register. This collapses the state into a superposition over a coset of H. That is, the remaining state looks like:
(1 / sqrt(|H|)) * sum over h in H of |g * h⟩
for some uniformly random element g from G.
At this point, we have a state that depends on H, but we cannot extract information from it directly by measuring in the standard basis.
The key insight is to change the basis using the quantum Fourier transform (QFT). In the Fourier basis, the hidden structure of the subgroup becomes visible.
This works because the QFT diagonalizes the shift operators associated with the group. For abelian groups, these operators commute, making diagonalization possible.
By applying the QFT and measuring, we obtain information that restricts the possible structure of H. Repeating this process several times yields enough information to fully reconstruct the subgroup.