Предисловие

    Обозначения

    Введение

    Часть I. Классические вычисления

  1. Что такое алгоритм?
    1. Машины Тьюринга.
    2. Вычислимые функции и разрешимые предикаты.
    3. Вычисления на машинах Тьюринга.
    4. Сложностные классы.
    5. Схемы.
  2. Класс NP: сводимость и полнота
    1. NP - класс предикатов, вычислимых за полиномиальное время недетерминированными машинами Тьюринга.
    2. Сводимость и NP-полнота.
  3. Вероятностные алгоритмы и класс BPP. Проверка простоты числа
    1. Необходимые сведения из теории чисел.
    2. Необходимые сведения из алгоритмической теории чисел.
    3. Алгоритм проверки простоты.
    4. Анализ алгоритма.
    5. BPP и схемная сложность.
  4. Иерархия сложностных классов
    1. Игры, в которые играют машины.
    2. Класс PSPACE.

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

  5. Определения и обозначения
  6. Соотношение между классическим и квантовым вычислением
  7. Базисы для квантовых схем
  8. Определение квантового вычисления. Примеры
    1. Квантовый поиск: алгоритм Гровера.
    2. Универсальная квантовая схема.
    3. Квантовые алгоритмы и класс BQP.
  9. Квантовые вероятности
  10. Физически реализуемые преобразования матриц плотности
    1. Подсчет вероятностей для квантового вычисления.
    2. Потеря когерентности (decoherence).
    3. Измерение.
  11. Измеряющие операторы
  12. Быстрые квантовые алгоритмы
    1. Задача о скрытой подгруппе в $Z_2^k$.
    2. Разложение на множители и нахождение периода относительно возведения в степень.
    3. Сведение факторизации к вычислению периода.
    4. Квантовый алгоритм нахождения периода: основная идея.
    5. Построение измеряющего оператора.
      1. Как получать информацию о собственном числе.
      2. Оценка условных вероятностей.
      3. Экспоненциально точное определение собственных чисел.
    6. Обсуждение алгоритма.
    7. Задача о скрытой подгруппе в $Z^k$.
  13. Квантовый аналог NP: класс BQNP
    1. Модификация классических определений.
    2. Квантовое определение по аналогии.
    3. Полные задачи.
    4. Место BQNP среди других сложностных классов.
  14. Классические и квантовые коды
    1. Классические коды.
    2. Примеры классических кодов.
    3. Линейные коды.
    4. Квантовые коды.
    5. Модель независимых ошибок в квантовом случае.
    6. Основные определения и простейшие следствия.
    7. Код Шора.
    8. Симплектические (стабилизирующие) коды
    9. Торические коды.
    10. Процедура исправления ошибок.
    11. Анионы (иллюстративный пример на основе торического кода).

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

    Литература

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