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

Последнее изменение: 21/03/2018 06:06:40

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

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

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

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

Спецкурс читается по средам 6-й парой (17:50-19:20) в ауд. 601.

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

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

Литература:


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