Quantum Computation and Quantum Information: Shor’s Factoring Algorithm
Семинары
Семинар «Современная математическая физика»
Дата и время: среда, 23 мая 2018 г., в 15:00
Место: Конференц-зал им. Блохинцева (4-й этаж), Лаборатория теоретической физики им. Н.Н. Боголюбова
Тема семинара: «Quantum Computation and Quantum Information: Shor’s Factoring Algorithm»
Докладчик: Martin Bures (BLTP and IEAP, Prague)
Аннотация:
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.