Quantum Computation and Quantum Information: Shor’s Factoring Algorithm
Seminars
Seminar “Modern Mathematical Physics”
Date and Time: Wednesday, 23 May 2018, at 3:00 PM
Venue: Blokhintsev Hall (4th floor), Bogoliubov Laboratory of Theoretical Physics
Seminar topic: «Quantum Computation and Quantum Information: Shor’s Factoring Algorithm»
Speaker: Martin Bures (BLTP and IEAP, Prague)
Abstract:
Shor’s factoring algorithm is perhaps the most impressive example of a quantum algorithm and its discovery drew great attention to the field of quantum computing. It has been widely conjectured that classical algorithms cannot solve the problem of integer factorization in polynomial time. However, a quantum computer breaks this spell. A machine with enough qubits (quantum bits) would thus undermine the security of public key cryptographic systems (such as RSA) which rely on the infeasibility of factorization of integers which are product of large prime numbers. We will provide some necessary background from quantum computing/quantum information theory and explain how the “miracle” of computational complexity reduction happens in the case of Shor’s algorithm.