Quantum Computing and the Hidden Subgroup Problem

Summary

The Hidden Subgroup Problem 23 Apr 2025 Introduction Two of the most famous quantum algorithms are Shor’s Algorithms for integer factorization and discrete logarithms. The significance of these algorithms is that efficient integer factorization breaks the RSA cryptosystem, and efficient discrete logarithm computation breaks the Diffie-Hellman key exchange protocol. It is natural to wonder what other types of problems that are classically considered to be hard can be efficiently solved with a quantum computer. Interestingly, both integer factorization and the discrete logarithm problem are special cases of a more general problem called the hidden subgroup problem (HSP). Furthermore, Shor’s algorithms can be generalized to an efficient quantum algorithm for the HSP whenever the group in question is commutative. Conversely, almost all known problems with significant quantum speedups are instances of the HSP for commutative groups. In this post we’ll introduce the hidden subgroup problem and the quantum algorithm that efficiently solves it in the commutative case. We’ll also apply this framework to the discrete logarithm problem and Simon’s Problem. The Hidden Subgroup Problem In this section we’ll formally define the hidden subgroup problem and then see how it generalizes some famous problems in quantum computing. We’ll start by defining the notion of a function on a group hiding a subgroup. Definition (Hiding A Subgroup). Let $G$ be a finite group, $H\subset G$ a subgroup of $G$, $A$ a set and \[f: G \rightarrow A\] a function from $G$ to $A$. We say that $f$ hides $H$ if, for all $g_1,g_2\in G$, $f(g_1) = f(g_2)$ if and only if $g_1H = g_2H$. In other words, $f$ hides $H$ if it defines an injective function on the cosets of $H$. The hidden subgroup problem is to find $H$ given an black box which allows us to evaluate $f$ on elements of $G$. Definition (Hidden Subgroup Problem). Let $G$ be a finite group, $H\subset G$ a subgroup and $f: G \rightarrow A$ a function tha...