Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Квантовые алгоритмы: возможности и ограничения
Санкт-Петербург / весна 2011, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

Два основных вопроса, вытекающих из этих открытий: насколько велики возможности квантовых алгоритмов? возможно ли создание устройств, реализующих эти алгоритмы? Эти вопросы интенсивно изучались последние два десятилетия. Получены интересные частичные результаты, но до полных ответов еще очень далеко.

В данном курсе будет рассказано об основных идеях построения и анализа квантовых алгоритмов. Для понимания курса помимо базовых знаний по теоретической информатике крайне желательно знание основ линейной алгебры.

Дата и время Название Место Материалы
02 апреля
17:20–18:55
Стандартная модель, Лекция ПОМИ РАН слайды,  видеофайлы
02 апреля
19:05–20:40
Квантовые запросы к "чёрному ящику", Лекция ПОМИ РАН слайды,  видео
03 апреля
11:15–12:50
Сложность булевых функций в модели запросов, Лекция ПОМИ РАН слайды,  видео
03 апреля
13:00–14:35
Полиномиальная эквивалентность числа квантовых и классических запросов. Коммуникационная сложность, Лекция ПОМИ РАН слайды,  видео
03 апреля
15:35–17:10
Нижние оценки квантовой коммуникационной сложности. Другие модели коммуникации, Лекция ПОМИ РАН слайды,  видео
09 апреля
17:20–18:55
Квантовые схемы, Лекция ПОМИ РАН слайды,  видео
09 апреля
19:05–20:40
Конечные базисы, Лекция ПОМИ РАН слайды,  видео
10 апреля
11:15–12:50
Факторизация чисел, Лекция ПОМИ РАН слайды,  видео
10 апреля
13:00–14:35
Класс BQP, Лекция ПОМИ РАН слайды,  видео
10 апреля
15:35–17:10
Моделирование квантовых схем классическими средствами. О реализации квантового компьютера, Лекция ПОМИ РАН слайды,  видео