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

Последнее изменение: 08/01/2014 00:00:00

Ближайшие даты, когда можно сдать экзамен или зачёт:

  • Четверг, 09.01, с 16:00 до 18:00
  • Пятница, 17.01, с 12:00 до 14:00

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


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

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

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

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

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

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

Литература: Arthur O. Pittenger. An Introduction to Quantum Computing Algorithms. Birkhäuser, 2000.


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