Читать онлайн «Классические и квантовые вышисления»

КЛАССИЧЕСКИЕ и КВАНТОВЫЕ ВЫЧИСЛЕНИЯ А. Китаев, А. Шень, М. Вялый мцнмо ЧеРо 1осква 1999 ББК 22. 12 22. 134 К53 А. Китаев, А. Шень, М. Вялый К53 Классические и квантовые вычисления. — М. : МЦНМО, ЧеРо, 1999. — 192 с. ISBN 5-900916-35-9 Эта книга предназначена для первоначального знакомства с новой быстро развивающейся и популярной областью исследований — теорией квантовых вычислений. Вначале приводится краткое введение в классическую теорию сложности вычислений. Затем подробно излагаются основы теории квантовых вычислений, включая онисание основных известных к настоящему времени эффективных квантовых алгоритмов. Для студентов физико-математических специальностей (начиная со второго года обучения), аспирантов, научных работников: математиков и физиков. ББК 22. 12 22. 134 # Издание осуществлено при финансовой поддержке РФФИ (издательский проект 1(^99-01-14054) ©А. Китаев, А. Шень, М. Вялый, 1999 ISBN 5-900916-35-9 w , , , ©МЦНМО, 1999 Редактор В. В. Ященко Технический редактор М. Н. Вялый Лицензия ЛР №071150 от 11. 04. 95 г. Подписано в печать 16. 09. 99 г. Формат 60 X 90/16. Бумага офсетная №1. Печать офсетная. Печ. л. 12,0. Тираж 1500. Издательство Московского Центра непрерывного математического образования. 121002, Москва, Большой Власьевский пер. , д. 11. Издательство «ЧеРо». Редакционно-издательский отдел: 121002, Москва, Б. Власьевский пер. , д. 11, комн. 208. Тел. 24133 90, 2411869. Отдел реализации. 118899, Москва, ул. Акад. Хохлова, д. 11. Тел. 939 47 09, 939 34 93. Оглавление Предисловие 4 Обозначения 6 Введение 9 Часть I. Классические вычисления 17 1. Что такое алгоритм? 17 2. Класс NP: сводимость и полнота 29 3. Вероятностные алгоритмы и класс ВРР. Проверка простоты числа 37 4. Иерархия сложностных классов 43 Часть II. Квантовые вычисления 50 5. Онределения и обозначения 52 6. Соотношение между классическим и квантовым вычислением . . 56 7. Базисы для квантовых схем 60 8. Определение квантового вычисления. Примеры 68 9. Квантовые вероятности 75 10. Физически реализуемые преобразования матриц плотности ... . 81 11. Измеряющие операторы 86 12. Быстрые квантовые алгоритмы 90 13. Квантовый аналог NP: класс BQNP 105 14. Классические и квантовые коды 119 Часть III. Решения задач 142 Из раздела 1 142 Из раздела 2 156 Из раздела 4 164 Из раздела 6 166 Из раздела 7 166 Из раздела 8 174 Из раздела 9 178 Из раздела 10 179 Из раздела 11 184 Из раздела 12 184 Из раздела 14 185 Литература 188 Предметный указатель 191 Предисловие в последние годы интерес к тому, что называется «квантовые компьютеры», необычайно возрос. Идея использования возможностей квантовой механики при организации вычислений выглядит всё более привлекательной, начаты экспериментальные работы в этой области. Однако перспективы физической реализации квантовых компьютеров пока совергпепно неясны. Скорее всего, это дело нескольких десятилетий. Основные достижения в этой области носят пока чисто математический характер. Эта книга предназначена для первоначального знакомства с математической теорией квантовых вычислений.