Lecture 13. Quantum algorithms for number theory problems

In this Lecture, we talked about efficient quantum algorithms for two important problems in number theory: the problem of finding the discrete logarithm and the problem of period finding. Computing the discrete logarithm in a cyclic group of order $N$ reduces to finding the hidden subgroup in the group $\mathbb{Z}_N\times\mathbb{Z}_N$ and the ability to efficiently perform exponentiation modulo $N$. The ability to find discrete logarithms allows us to break the Diffie-Hellman protocol of secret key generation between two agents. The problem of finding the period $r$ of some periodic function $f$ can be formulated as a hidden subgroup problem in $\mathbb{Z}$. By choosing a sufficiently large number $N > r^2$, one can follow the standard procedure for computing the hidden subgroup and take advantage of the analytic properties of continued fractions.