Кулик Введение в теорию квантовых вычислений Книга 2 2008

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

С.Д. Кулик, А.В. Берков, В.П. Яковлев

ВВЕДЕНИЕ В ТЕОРИЮ КВАНТОВЫХ ВЫЧИСЛЕНИЙ

(методы квантовой механики в кибернетике) Книга 2

Рекомендовано УМО “Ядерные физика и технологии” в качестве учебного пособия

для студентов высших учебных заведений

Москва 2008

УДК 530.145:007(075) ББК 22.31я7+32.81я7 К 90

Кулик С.Д., Берков А.В., Яковлев В.П. Введение в теорию квантовых вычислений (методы квантовой механики в кибернетике): учебное пособие.– В 2 кн.– Кн. 2.– М.: МИФИ, 2008.–532 с.

Изложены основные понятия и методы теории квантовых вычислений — новой дисциплины, сформировавшейся на стыке квантовой механики и кибернетики. Представлены начальные основы квантовой схемотехники. На многочисленных примерах детально рассмотрены основные идеи, а также даны решения задач прямого и обратного анализа квантовой схемы и задачи синтеза квантовой схемы, удовлетворяющей требуемым условиям.

Пособие в основном ориентировано на студентов МИФИ кафедр “Теоретическая ядерная физика” и “Управляющие интеллектуальные системы”, изучающих не только квантовую механику, но и теорию принятия решений, и схемотехнику вычислительных устройств.

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

Во второй книге представлены основы квантовых вычислений.

Пособие подготовлено в рамках Инновационной образовательной программы.

Рецензент д-р физ.-мат. наук, профессор С. Г. Рубин

ISBN 978-5-7262-0976-0

ISBN 978-5-7262-0997-5 (кн. 2)

©Московский инженерно-физический институт (государственный университет), 2008

2

ОГЛАВЛЕНИЕ

3

4

Во многих источниках есть ошибки, опечатки, упущения и т.п. дефекты. Конечно, и эта работа не исключение. В любом случае будем рады информации об обнаруженных опечатках и неточностях.

Авторы

sedmik@mail.ru

sedmik@hotmail.com

5

ВВЕДЕНИЕ

________________________________________________________

За последние два–три десятилетия сформировалась новая область знания о природе, объединившая в себе квантовую механику и теорию информации. К этой междисциплинарной науке относят-

ся такие понятия как «квантовая информация» и «квантовые вы-

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

В ближней ретроспективе отправным пунктом можно считать доклад Ричарда Фейнмана «Моделирование физики на компьютерах», который был сделан в 1981 г. в Массачусетском технологическом институте (MIT) и опубликован в 1982 г. вместе со статьей «Квантово-механические компьютеры» (Int. J. Theor. Phys., 1982, V.21, P.467-488), и работу Дэвида Дойча «Квантовая теория, принцип Чёрча – Тьюринга и универсальный квантовый компьютер»

(Proc. R.Soc. Lond., 1985, V. A400, P. 97-117). Эти работы положи-

ли начало пониманию того факта, что вычисления, основанные на законах квантовой механики, или, говоря более общим языком, процессы манипулирования квантовой информацией могут быть гораздо (например, даже экспоненциально) быстрее и эффективнее, чем для классической информации. Количественный аспект этого утверждения является следствием нового качества, связанного с понятием квантовой информации. В статье «Информация по сути физична» (Physics Today, May 1991, P.23-29) Рольф Ландауэр

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

6

ния двухуровневого атома. Такие состояния и, следовательно, представляемая ими информация подчиняются законам квантовой механики.

На сегодняшний день квантовая информатика синтезирует целый ряд актуальных областей современной фундаментальной и прикладной физики, дискретной математики и кибернетики, а также передовые достижения в области квантовых технологий. Усилия многих мировых научных групп, сконцентрированные в этих направлениях исследований, привели к целому ряду впечатляющих результатов, которые экспериментально подтверждают фундаментальные основы квантовой информатики и открывают реалистические перспективы ее дальнейшего развития. Поскольку границы этой области исследований оказываются чрезвычайно обширными и включают много взаимосвязанных дисциплин, то путешествие по ней удобно начать, взглянув на схематическую карту, представленную на рис.В1. По этой схеме, не претендующей на полноту, можно составить представление о том, какова роль и место вопросов, затронутых в данной книге.

Сейчас представляется совершенно ясным, что изучение основ квантовой информатики и квантовых вычислений должно войти как обязательный компонент в систему подготовки как физиков, так и специалистов по теории информации, которых готовит МИФИ и которым адресуется данная книга. Авторы ставили своей целью написать учебник, который, с одной стороны, адекватным образом представлял бы достаточно широкий круг вопросов, связанных с этой областью, а с другой стороны, был бы без ущерба для научной строгости доступным для понимания как студентам физических специальностей, так и студентам, обучающимся в области кибернетики и схемотехники вычислительных устройств. Определенная разнонаправленность этих «граничных условий» неизбежно диктовала и отбор материала, а также метод и стиль изложения. Поскольку основной задачей было дать введение в

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

7

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

Опыт создания информационных систем (ИС) показал, что современный специалист в области ИС и, в частности, автоматизи-

рованных систем обработки информации и управления (АСОИУ)

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

Современные исследования убедительно показывают, что элементная база вычислительных средств, построенная на квантовых объектах, обеспечит возможность реализовывать не просто эффективные, а очень эффективные алгоритмы для решения практических задач. Инструментарий квантовых вычислений предоставляет для квантовой схемотехники широкие возможности эффективного решения очень важных для практики задач, которые либо слишком трудны, либо просто «неподвластны» классическим алгоритмам. Квантовая механика открыла возможность разработки квантовых алгоритмов для выполнения квантовых вычислений. Именно основам квантовых вычислений и посвящено данное пособие.

Авторы благодарны студентам кафедры “Теоретическая ядерная физика” и кафедры “Управляющие интеллектуальные системы” МИФИ, которые были первыми слушателями, и на них апробировалась часть материалов, представленных в пособии. ВПЯ благодарит П.А. Жукова и К.Е. Городничева за техническую помощь в оформлении рукописи. СДК признателен А.В. Жижилеву, и П.В. Чамкину за дополнительную проверку примеров из главы 5.

В пособии в книге 2 главу 1 написал А.В. Берков, главы 2, 3, 4 — В.П. Яковлев, главу 5 (и главу 1 в книге 1) — С.Д. Кулик.

Авторы

8

9

Рис. В1

«…я смело могу сказать, что квантовой механики никто не понимает…»

Р. Фейнман

Основные понятия квантовой механики

10