Докладчик: М.Н. Вялый (ВЦ РАН, Москва)

Дата: 4th October 2013

Время: 13:00

Место: зал ученого совета ИПС

Презентация: Скачать

Аннотация:

Одна из моделей вычисления — квантовые алгоритмы — привлекает большое внимание по двум причинам:

1. эта модель кажется физически реализуемой (хотя ясны огромные трудности на пути реализации таких алгоритмов);
2. в этой модели существуют эффективные алгоритмы решения «трудных» задач. Под «трудными» здесь имеются в виду задачи, трудность которых признается практически.

Самые известные примеры таких задач — факторизация чисел и вычисление дискретного логарифма. Эффективные квантовые алгоритмы решения этих задач, построенные П.Шором в 1994 году, стали отправной точкой бурного развития теории квантовых вычислений.

В докладе будут обсуждаться эффективные квантовые алгоритмы именно для этих задач. Основным предметом обсуждения будет процедура измерения фазы (собственного числа), предложенная А.Китаевым в 1995 году. Эта процедура стала одним из главных инструментов построения эффективных квантовых алгоритмов.