1. Машины Тьюринга.
2. Вычислимые функции и разрешимые предикаты.
3. Вычисления на машинах Тьюринга.
4. Сложностные классы.
5. Схемы.

1. NP - класс предикатов, вычислимых за полиномиальное время недетерминированными машинами Тьюринга.
2. Сводимость и NP-полнота.

1. Необходимые сведения из теории чисел.
2. Необходимые сведения из алгоритмической теории чисел.
3. Алгоритм проверки простоты.
4. Анализ алгоритма.
5. BPP и схемная сложность.

1. Игры, в которые играют машины.
2. Класс PSPACE.

Часть II. Квантовые вычисления

1. Квантовый поиск: алгоритм Гровера.
2. Универсальная квантовая схема.
3. Квантовые алгоритмы и класс BQP.

1. Подсчет вероятностей для квантового вычисления.
2. Потеря когерентности (decoherence).
3. Измерение.

1. Задача о скрытой подгруппе в $Z_2^k$.
2. Разложение на множители и нахождение периода относительно возведения в степень.
3. Сведение факторизации к вычислению периода.
4. Квантовый алгоритм нахождения периода: основная идея.
5. Построение измеряющего оператора.
   1. Как получать информацию о собственном числе.
   2. Оценка условных вероятностей.
   3. Экспоненциально точное определение собственных чисел.
6. Обсуждение алгоритма.
7. Задача о скрытой подгруппе в $Z^k$.

1. Модификация классических определений.
2. Квантовое определение по аналогии.
3. Полные задачи.
4. Место BQNP среди других сложностных классов.

1. Классические коды.
2. Примеры классических кодов.
3. Линейные коды.
4. Квантовые коды.
5. Модель независимых ошибок в квантовом случае.
6. Основные определения и простейшие следствия.
7. Код Шора.
8. Симплектические (стабилизирующие) коды
9. Торические коды.
10. Процедура исправления ошибок.
11. Анионы (иллюстративный пример на основе торического кода).

Часть III. Решения задач

Литература

Предметный указатель