Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/ium/s98/quantcomp.html
Дата изменения: Fri Dec 9 17:01:07 2005
Дата индексирования: Tue Oct 2 06:28:52 2012
Кодировка: koi8-r
Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п
|
На главную страницу НМУ
Классическое и квантовые вычисление (весна 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: Основные понятия теории сложности (А.Шень)
- Алгоритмическая сложность и класс P. Примеры алгоритмов и
трудных задач.
- Схемная сложность; однородные семейства булевых схем.
- Класс NP. Сводимость по Карпу. NP-полные задачи.
- Полиномиальная иерархия и класс PSPACE. Сводимость по Тьюрингу,
относительная сложность.
- Вероятностное вычисление и класс BPP. Полиномиальный
вероятностный алгоритм проверки простоты числа.
Часть 2: Квантовое вычисление (А.Китаев)
- Идея квантового вычисления. Унитарные преобразования и квантовые схемы.
Классическое обратимое вычисление.
- Основные понятия квантовой механики. Матрица плотности. Измерения и
измеряющие операторы.
- Определение и простейшие свойства квантового
вычисления. Класс BQP.
Некоторые идеи, касающиеся физической реализации квантового компьютера.
- Квантовый алгоритм для задачи о периоде. Задача о стабилизаторе,
дискретный логарифм.
- Коды, исправляющие ошибки.
- Квантовые коды.
- Вычисление, устойчивое к ошибкам (классическое и квантовое).