RUS  ENG
Full version
SEMINARS

Quantum computation
May 15, 2024 13:10, Steklov Mathematical Institute, Room 430 (8 Gubkina) + Zoom


Lecture 14. Factorization algorithm, brief conclusion

V. I. Yashin


https://youtu.be/hpA-08hBmAg

Abstract: At the last Lecture we finished talking about Shor's algorithm for factorisation of large numbers. Given a composite number $N$, it is possible to find a nontrivial divisor of this number in time $\tilde{\mathcal{O}}((\log N)^2)$ using Shor's algorithm. The classical complexity of this problem underlies the operation of some cryptosystems. The algorithm is based on reducing the factorization problem to the problem of period finding. Also, the lecture gave a brief overview of the course and a short commentary on the current research topics in quantum computing.


© Steklov Math. Inst. of RAS, 2024