Quantum Computing and the Hidden Subgroup Problem

The Hidden Subgroup Problem 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 ... Read full article.