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

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

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

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

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

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

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

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

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

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

Литература:

  • 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

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

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

Слайды лекции (версия для печати)

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

Слайды лекции (версия для печати)

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

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

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

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

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

Слайды лекции (версия для печати)

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

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

Слайды лекции (версия для печати)

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

Воспоминания Шора о том, как и почему был придуман квантовый алгоритм факторизации

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

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

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

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

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

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

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

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

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

Слайды лекции (версия для печати)


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