Get the latest tech news
Quantum Computing and the Hidden Subgroup Problem
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.
Recall from the previous section that our strategy for solving the hidden subgroup problem is to find a unitary transformation that diagonalizes all of the shift operators $L_g$ for $g\in G$. Deriving an efficient circuit for an arbitrary $N$ is outside the scope of this post, but a good reference is chapter 4 of Andrew Childs’ Lecture Notes. If we repeat the process $\mathcal{O}(N)$ times, we have a high chance of finding $N$ independent linear constraints on the length $N$ vector $\mathbf{s}$ which is sufficient to recover $\mathbf{s}$ and solve Simon’s problem.
Or read this on Hacker News
