Докладчик: М.Н. Вялый (ВЦ РАН, Москва)
Дата: 4 октября 2013
Время: 13:00
Место: зал ученого совета ИПС
Презентация:
Скачать
Аннотация:
Одна из моделей вычисления - квантовые алгоритмы - привлекает большое внимание по двум причинам:
- эта модель кажется физически реализуемой (хотя ясны огромные трудности на пути реализации таких алгоритмов);
- в этой модели существуют эффективные алгоритмы решения "трудных" задач. Под "трудными" здесь имеются в виду задачи, трудность которых признается практически.
Самые известные примеры таких задач - факторизация чисел и вычисление дискретного логарифма. Эффективные квантовые алгоритмы решения этих задач, построенные П.Шором в 1994 году, стали отправной точкой бурного развития теории квантовых вычислений.
В докладе будут обсуждаться эффективные квантовые алгоритмы именно для этих задач. Основным предметом обсуждения будет процедура измерения фазы (собственного числа), предложенная А.Китаевым в 1995 году. Эта процедура стала одним из главных инструментов построения эффективных квантовых алгоритмов.