Спецкурс "Основы квантовых алгоритмов"

Последнее изменение: 20/05/2024 08:43:28

В последнее время много говорится о квантовых компьютерах, квантовых вычислениях, квантовой телепортации и т.п. Что это - заря новой научной революции или очередной раздуваемый дилетантами мыльный пузырь? Приведут ли квантовые технологии к дискредитации общепринятых криптосистем или, наоборот, именно на основе таких технологий будут созданы принципиально невскрываемые системы хранения и передачи информации? Имеет ли всё это хоть какое-то отношение к математике и компьютерным наукам или, пока физики не доведут свои идеи до чего-нибудь реального, математикам и программистам в этой области делать нечего? И если даже вычислительные машины, основанные на новых принципах, возможны, чем плохи существующие компьютеры и в чём состоят преимущества квантовых алгоритмов?

В семестровом спецкурсе будут серьёзно обсуждаться сформулированные выше вопросы. Слово "серьёзно" означает, что

будут доступно, но математически строго описаны квантово-механические представления, лежащие в основе квантовых алгоритмов;
будут с полными доказательствами изложены основные квантовые алгоритмы, в том числе алгоритм поиска (алгоритм Гровера) и алгоритм факторизации (алгоритм Шора) и приведены оценки их быстродействия.

Для понимания спецкурса требуется владение базовым курсом линейной алгебры (2-й семестр 1-го курса), более точно, базовыми понятиями теории операторов в конечномерных унитарных пространствах. Желательно (но необязательно) представление об NP-полных задачах. Предварительные знания по квантовой механике не предполагаются. Отчётность - экзамен или зачёт (по выбору слушателя). Приглашаются все заинтересованные студенты бакалавриата и магистратуры.

Спецкурс читается по четвергам (начиная с 21.03) с 16:10 до 17:40 в ауд. 611 (кафедра алгебры и фундаментальной информатики).

Тест для зачета

План спецкурса

Эксперимент Штерна-Герлаха и его матричная интерпретация
Матричный формализм квантовой механики
Алгоритм Дойча-Йожи
Алгоритм Саймона
Алгоритм Гровера
Алгоритм Шора. Случай произведения двух простых чисел Ферма
Алгоритм Шора. Общий случай
Использование квантовой телепортации в криптографии.

Литература:

Arthur O. Pittenger. "An Introduction to Quantum Computing Algorithms". Birkhäuser, 2000.
С. Дасгупта, Х. Пападимитриу, У. Вазирани. "Алгоритмы". Перевод с английского А. С. Куликова под редакцией А. Шеня. Издательство МЦНМО, 2014.

Лекция 1: Введение. Эксперимент Штерна-Герлаха. Физико-математический словарь

Видеозапись лекции 2020/21 учебного года

Мы начнем с обсуждения того, почему изучать квантовые алгоритмы имеет смысл, несмотря на то, что устройств, способных имплементировать такие алгоритмы ("квантовые компьютеры"), пока не нет и не очевидно, появятся ли они когда-нибудь.

Презентация Скотта Аарансона, частично использованная в этой части лекции.

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

существо эксперимента легко объяснить;
его результаты контринтуитивны и не допускают разумного истолкования с точки зрения “классической” физики;
квантовые эффекты (такие как некоммутативность) проявляются в нем в очень явной форме.

Статья в английской Википедии про эксперимент Штерна-Герлаха очень содержательна и содержит хорошие иллюстрации, которые используются в лекции.

Физико-математический словарь
Квантовая система	(Конечномерное) гильбертово пространство H
Состояние системы	Неотрицательный оператор R:H → H со следом 1
Наблюдаемая	Самосопряженный оператор A:H → H
Возможные результаты наблюдения	Собственные значения оператора A
Ожидаемое значение наблюдаемой A в состоянии R	tr(RA)
Преобразование системы	Унитарный оператор на H