Классические и квантовые вычисления

Классические и квантовые вычисления

2-е издание, исправленное

Шень А.Х.
Вялый М.Н.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Классические и квантовые вычисления/ А.Х. Шень, М.Н. Вялый - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Шень А.Х., Вялый М.Н., 2007-2016

3

Предисловие

Материалы данного учебного курса подготовлены с использованием файлов книги
“Языки и исчисления”, являющейся свободно распространяемой и доступной по адресу
ссылка: http://www.mccme.ru/free-books/. Авторы книги не принимали участия в
подготовке этих материалов для курса.

В последние годы интерес к тому, что называется “квантовые компьютеры”,
необычайно возрос. Идея использования возможностей квантовой механики при
организации вычислений выглядит все более привлекательной, начаты
экспериментальные работы в этой области.

Однако перспективы физической реализации квантовых компьютеров пока
совершенно неясны. Скорее всего, это дело нескольких десятилетий. Основные
достижения в этой области носят пока чисто математический характер.

Эта книга предназначена для первоначального знакомства с математической теорией
квантовых вычислений. Для удобства читателя вначале дается краткое введение в
классическую теорию сложности вычислений. Затем подробно излагаются основы
теории квантовых вычислений, включая описание основных известных к настоящему
времени эффективных квантовых алгоритмов.

Основу книги составили материалы курса “Классическое и квантовое вычисление”,
прочитанного А. Шенем (классические вычисления) и А. Китаевым (квантовые
вычисления) в Высшем колледже математики Независимого Московского
университета в весеннем семестре 1998 г. При подготовке книги также использовались
материалы курса Physics 229 - Advanced Mathematical Methods of Physics (Quantum
computation), который вели Дж. Прескилл (John Preskill) и А. Китаев (при участии А.
Ландала (Andrew Landahl)) в Калифорнийском технологическом институте в 1998-1999
уч. г.

Необходимые для чтения этой книги знания невелики. В сущности, достаточно знания
линейной алгебры в объеме стандартного университетского курса, элементарной
теории вероятностей, элементарной теории чисел и минимальных представлений о
теории алгоритмов (например, иметь навыки практического программирования
нетривиальных алгоритмов).

Обозначения

4