На главную страницу НМУ

Классическое и квантовые вычисление (весна 1998)

А.Шень, А.Китаев

Записки лекций (выполнены М.Н.Вялым)
(Lecture notes, by M.Vyalyi)

Gzipped postscript (may be viewed directly by some versions of Ghostview)

[Лекция 2 (40 K)|Лекция 3 (37K)|Лекция 4 (39K)|
Лекция 5 (43K)|Лекция 6 (47K)|Лекция 7 (32K)|
Лекция 8 (54K)|Лекция 9 (41K)|Лекция 10 (45K)|
Лекция 11 (38K)|Лекция 12 (44K)|Лекция 13 (43K)]

Запакованные zip-ом postscript-файлы (Zipped Postscript)

[Лекция 2 (40 K)|Лекция 3 (37 K)|Лекция 4 (39 K)|
Лекция 5 (43 K)|Лекция 6 (48 K)|Лекция 7 (32 K)|
Лекция 8 (54 K)|Лекция 9 (41 K)|Лекция 10 (45 K)|
Лекция 11 (38 K)|Лекция 12 (45 K)|Лекция 13 (43 K)]

Задачи по классическим вычислениям (Exercises on classical computations)

[Postscript-файл (36 K)|Запакованный zip-ом postscript-файл (12 K)]

Задачи по квантовым вычислениям (Exercises on quantum computations)

[Postscript-файл (42 K)|Запакованный zip-ом postscript-файл (17 K)]

Программа курса

Часть 1: Основные понятия теории сложности (А.Шень)

1. Алгоритмическая сложность и класс P. Примеры алгоритмов и трудных задач.
2. Схемная сложность; однородные семейства булевых схем.
3. Класс NP. Сводимость по Карпу. NP-полные задачи.
4. Полиномиальная иерархия и класс PSPACE. Сводимость по Тьюрингу, относительная сложность.
5. Вероятностное вычисление и класс BPP. Полиномиальный вероятностный алгоритм проверки простоты числа.

Часть 2: Квантовое вычисление (А.Китаев)

1. Идея квантового вычисления. Унитарные преобразования и квантовые схемы. Классическое обратимое вычисление.
2. Основные понятия квантовой механики. Матрица плотности. Измерения и измеряющие операторы.
3. Определение и простейшие свойства квантового вычисления. Класс BQP. Некоторые идеи, касающиеся физической реализации квантового компьютера.
4. Квантовый алгоритм для задачи о периоде. Задача о стабилизаторе, дискретный логарифм.
5. Коды, исправляющие ошибки.
6. Квантовые коды.
7. Вычисление, устойчивое к ошибкам (классическое и квантовое).