Lecture 11. Quantum algorithms for modular arithmetics

In this Lecture we discussed how quantum computers can do arithmetic operations on the ring of numbers $\mathbb{Z}_N$. The operations of addition, multiplication, division, and taking powers are efficiently realized on classical circuits, and hence their reversible versions are realized on a quantum computers as well. However, additionally it is possible to effectively perform quantum Fourier transform on quantum circuits. Thanks to it, the problem of finding discrete logarithm is efficiently solvable on quantum computers. Practical realization of this possibility will allow to crack some cryptographic systems.