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

Последнее изменение: 28/03/2021 15:27:47

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

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

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

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

В осеннем семестре 2020/21 учебного года спецкурс читается по вторникам 2-й парой (10:40-12:10) в MS Teams

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

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

Литература:

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

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

Видеозапись лекции

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

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

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

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

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

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

Лекция 2: Матричный формализм квантовой механики

Видеозапись лекции

Слайды лекции (исправлено)

Лекция 3: Алгоритмы Дойча и Дойча-Йожи

Слайды лекции (исправлено)

Оригинал статьи Дэвида Дойча (1985)

Оригинал статьи Дэвида Дойча и Ричарда Йожи (1992)

Русские переводы обеих статей включены в сборник Квантовый компьютер и квантовые вычисления, выпуск II, Ижевск, 1999.

Лекция 4: Алгоритм Саймона

Видеозапись лекции

Слайды лекции

Лекция 5: Алгоритм Гровера

Видеозапись лекции

Слайды лекции (исправлено)

Лекции 6-8: Алгоритм Шора

Видеозапись первой части

Видеозапись второй части

Видеозапись третьей части

Слайды первой части (исправлено)

Слайды второй части (исправлено)

Слайды третьей части (исправлено)

Лекция 9: Квантовая телепортация

Видеозапись лекции (есть проблемы со звуком)

Слайды лекции


Смотрите также: