Квантовые вычисления и функциональное программирование

Квантовые вычисления 
и функциональное 
программирование

Москва, 2015

Р. В. Душкин

УДК  004.42
ББК 32.973
 
Д86

 
 
Душкин Р. В.

Д86 
Квантовые вычисления и функциональное программирование. – М.: ДМК Пресс, 2015. – 232 с.: ил. 

ISBN 978-5-97060-275-1

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

Книга будет интересна всякому, кто интересуется новыми веяниями в области 

теории вычислений и смежных наук.

 
УДК   004.42

 
ББК 32.973

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

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

 
© Душкин Р. В., 2015

ISBN 978-5-97060-275-1               © Оформление, издание, ДМК Пресс, 2015

Книга посвящается всем людям доброй воли с открытым разумом, 
естественно-научным мировоззрением и системным мышлением

Содержание

Введение ................................................................. 6

Глава 1. Наивное понимание модели квантовых 
вычислений ............................................................ 11
Квантовые состояния и кубиты ....................................................................................14
Несколько кубитов ............................................................................................................24
Гейты и квантовые схемы ................................................................................................29
Квантовая схемотехника .................................................................................................45
Принципы квантовых вычислений .............................................................................49
Общая архитектура квантового компьютера ...........................................................53
Краткие выводы ..................................................................................................................55

Глава 2. Фреймворк для квантовых вычислений .............56
Квантовые состояния .......................................................................................................56
Кубиты ...................................................................................................................................60
Гейты .......................................................................................................................................68
Квантовые вычислительные схемы .............................................................................73
Некоторые задачи и их решение ...................................................................................75
Краткие выводы ..................................................................................................................82

Глава 3. Язык программирования Quipper .....................83
Немного о языке QCL ......................................................................................................85
Введение в язык Quipper .................................................................................................88
Решение нескольких простых задач ............................................................................90
От простого к сложному ..................................................................................................97
Дополнительные возможности ...................................................................................106
Краткие выводы ................................................................................................................108

Глава 4. Детальное рассмотрение некоторых 
квантовых алгоритмов .............................................110
Алгоритм Гровера .............................................................................................................111
Алгоритмы Дойча и Дойча-Йожи ..............................................................................121
Алгоритм Саймона ..........................................................................................................127
Алгоритм Шора ................................................................................................................132
Краткие выводы ................................................................................................................147

Глава 5. Квантовый «зоопарк» ...................................149
Алгебраические и теоретико-числовые алгоритмы .............................................150
Алгоритмы со специальными оракулами ................................................................156
Алгоритмы аппроксимации и эмуляции .................................................................185
Краткие выводы ................................................................................................................195

Содержание  5

Обзор литературы о квантовых вычислениях ...............199

Обзор видеокурсов по квантовым вычислениям 
и смежным темам ...................................................223

Заключение ...........................................................229

Низкий поклон спонсорам ........................................231

Введение

Сегодня всё больше и больше теоретических работ и даже практических разработок появляется в области так называемых квантовых 
вычислений, то есть новой вычислительной модели, которая вместо 
давно известного понятия бита (который, в свою очередь, пришёл 
к нам из работ Алана Тьюринга и Джона фон Неймана) основана на 
понятии «кубита», то есть квантового бита.
Квантовый бит – это некая квантовая система, которая до измерения находится в произвольной линейной суперпозиции двух базисных квантовых состояний (то есть, по сути, может принимать бесконечно большое разнообразие возможных значений), а в результате 
измерения с той или иной вероятностью принимает одно из двух возможных значений. Поэтому он и называется битом, поскольку возможных значений два, но, с другой стороны, он квантовый, поскольку 
эти два значений находятся в суперпозиции друг с другом.
Эта вычислительная модель в последнее время привлекает к себе 
всё больше и больше внимания как учёных, так и инженеров, поскольку её реализация, что называется, в «железе» откроет широчайшие возможности для решения задач, для которых в традиционной 
вычислительной модели не было вполне эффективных алгоритмов 
решения. Например, к таким задачам относится задача факторизации заданного числа, то есть поиска списка простых делителей этого числа (на гипотезе о невозможности быстро и эффективно найти 
разложение числа на простые множители основаны практически все 
современные методы криптографии). Есть ещё ряд задач такого же 
плана, решение которых в модели квантовых вычислений является 
полиномиальным, а не экспоненциальным, как в традиционной модели.
Это делает модель квантовых вычислений крайне интересной областью исследования. Однако, как это обычно бывает, основная масса 
исследований проводится за рубежом в университетах и исследовательских центрах западных стран. В России если и находятся энтузиасты, то все их работы «плетутся» в хвосте передовых исследований 
в данном перспективнейшем направлении. Связано это отчасти с тем, 
что методическая база для обучения специалистов у нас настолько 
устарела, что говорить о подготовке высококлассных специалистов 
в этой области просто не приходится.
Энтузиасты пользуются англоязычной литературой, которая часто 
настолько сложна для понимания просто в силу того, что западная 

Введение  7

мысль уже далеко ушла вперёд, что нашему исследователю сложно 
найти и ухватить нить повествования. Небольшое количество переводной литературы не спасает дело. А вот наличие некоторого количества монографий и учебников по квантовым вычислениям на русском языке скорее удручает, чем восхищает. Дело всё в том, что для 
того, чтобы читать и понимать всю эту литературу на русском языке, 
необходимо полноценно владеть теорией модели квантовых вычислений. Получается замкнутый круг – научиться негде и не у кого, 
а для учёбы надо уже всё знать.
В какой-то мере разорвать этот порочный круг призвана данная небольшая книга, в которой даётся самое-самое введение в модель квантовых вычислений. Для её чтения необходимо лишь владеть острым 
умом, желанием научиться и идти дальше в самостоятельном поиске, 
иметь базовые знания в математике и понимание принципов функционального программирования. Желательно наличие знания языка 
Haskell, его синтаксиса и операционной семантики. Это поможет понимать примеры, которыми изобилует эта книга.
Я постарался как можно больше избегать формул, строгой математики и «жёсткого матана», насколько это вообще возможно при рассмотрении подобной темы. Все понятия объясняются на пальцах, как 
можно более наивно. Поэтому я сразу же прошу прощения у читателя, который знаком с моделью квантовых вычислений, – многие объяснения могут показаться настолько упрощёнными и наивными, что 
будут балансировать на грани «ликбеза». Но именно такова цель этой 
книги – дать объяснение новой вычислительной модели как можно 
более широкому кругу читателей.
Да, для чтения книги желательно, чтобы читатель был знаком 
с языком функционального программирования Haskell. Это связано 
с несколькими причинами. Во-первых, функциональное программирование в целом и язык Haskell в частности являются моей областью 
интереса и исследований. Пропаганда и распространение информации о языке Haskell – это то, чем я занимаюсь уже на протяжении 
многих лет. К тому же это единственный язык программирования, 
на котором я могу реализовывать программы, поэтому все примеры 
в этой книге волей-неволей пришлось писать именно на нём.
Во-вторых, функциональное программирование как парадигма 
разработки программного обеспечения самым гармоничным образом легла на модель квантовых вычислений, поскольку понятие 
«функция» включает в себя понятие «унитарное преобразование», 
используемое в модели квантовых вычислений. Так что в рамках 

 Введение

функ цио нального программирования квантовые алгоритмы выражаются самым естественным образом. Поэтому нет никакого удивления 
в том, что современное предложение по реализации нового языка программирования Quipper, который используется для выражения квантовых вычислительных схем, полностью основано на языке Haskell.
Ну а в-третьих, есть одна важная особенность у модели квантовых вычислений. Разработать квантовый алгоритм – это значит настолько переформатировать себе мозги и «сдвинуть парадигму», что 
дальше уже просто нельзя. Квантовая механика по своей сути абсолютно контринтуитивна, и у нас нет никаких эмпирических навыков работы с бесконечномерными гильбертовыми пространствами и 
траекториями в них. И я считаю, что именно функциональное программирование наиболее близко из других способов программирования к парадигме квантовых вычислений. Расстояние от функционального до квантового программирования несколько короче, чем от 
любого иного.
Данная книга разбита на пять глав. В первой главе заинтересованному читателю предлагается описание модели квантовых вычислений, выраженное самыми простыми словами, которые только нашлись у меня. Из этой главы можно будет узнать, что такое кубит, 
как кубиты можно связывать друг с другом для получения многокубитовых состояний, что такое квантовая вычислительная схема и т. д. 
Прочитав эту главу, читатель сможет уже обратиться к более сложным источникам информации по квантовым вычислениям.
Вторая глава посвящена разработке фреймворка для выполнения 
квантовых вычислений на языке Haskell. Этот фреймворк позволяет 
решать многочисленные задачи по квантовым вычислениям и квантовой механике в целом. Реализация такого фреймворка позволяет 
более глубоко проникнуть в понимание модели квантовых вычислений, вынести «на пальцах» основные объекты и операции модели 
квантовых вычислений. После чтения этой главы, а особенно после 
самостоятельной работы с реализованным фреймворком, читатель 
сможет легко оперировать понятиями квантовых вычислений на 
практическом уровне. Но сам фреймворк будет дополняться по мере 
продвижения по тексту книги, особенно в четвёртой главе.
В третьей главе описывается новый язык программирования 
Quipper, который был разработан на базе языка Haskell для реализации квантовых алгоритмов. Приводятся описание языка, его синтаксис и несколько примеров реализации квантовых схем. После 
озна комления с этой главой читатель будет знать об одной из самых 

Введение  9

современных задач в рамках дальнейшей разработки модели квантовых вычислений в практическом русле. Несмотря на то что этот 
новый язык ещё не реализован в виде квантового компилятора и до 
реализации в «железе» ещё довольно далеко, он может быть одной 
из перспективнейших идей, которая будет реализована в ближайшем 
будущем.
Далее четвёртая и пятая главы посвящены описанию разработанных к настоящему времени квантовых алгоритмов. Не секрет, 
что в имеющейся литературе по квантовым вычислениям зачастую 
приводят описания двух или максимум трёх алгоритмов, которые 
разработаны к этому времени (алгоритм Дойча для распознавания 
сбалансированной функции, алгоритм Шора для факторизации и 
алгоритм Гровера для поиска – это тот самый максимум, что можно 
найти в современной литературе). Однако на сегодняшний момент 
разработано уже несколько десятков квантовых алгоритмов, и число 
это с каждым месяцем и годом растёт. Наверняка к моменту выхода 
этой книги в свет число разработанных квантовых алгоритмов увеличится, и описание уже станет неполным. Однако, ознакомившись 
с приведёнными в книге описаниями, читателю станет намного проще ориентироваться в имеющемся разнообразии алгоритмов. Соответственно, в четвёртой главе кратко описываются алгоритмы Гровера, Дойча (и Дойча-Йожи), Саймона и два алгоритма Шора (включая 
алгоритм квантового преобразования Фурье) как наиболее простые 
алгоритмы квантовой модели вычислений. А в пятой главе приводятся краткие описания других алгоритмов.
Поскольку литература по рассматриваемому вопросу очень немногочисленна, то я считаю своим долгом произвести более или менее 
полноценный обзор всего, что имеется на текущий момент на русском 
языке. В разделе «Обзор литературы о квантовых вычислениях» приводятся ссылки на литературу и краткая аннотация к каждой книге 
или иному материалу. Этот раздел будет полезен тем из читателей, 
кто хочет углубить свои знания в этой важной теме.
Ну и немаловажным и небезынтересным будет смежный раздел 
«Обзор видеокурсов по квантовым вычислениям и смежным темам», 
поскольку сегодня со всё большим и большим внедрением в повседневную жизнь новых методов обучения (так называемые MOOC – 
Massive Open Online Courses, то есть «массовые открытые онлайнкур сы») любому человеку становятся доступны знания в виде 
ви деолекций и интерактивных обучающих программ по практически 
любому направлению знаний, в том числе и по квантовым вычисле

 Введение

ниям. Для того чтобы ориентироваться и иметь представление о правильном выборе, читатель может обратиться к этому разделу.
К книге прикладываются многочисленные файлы с исходными 
кодами на языке Haskell, которые описываются по тексту книги. Читателю будет интересно разобраться самостоятельно с теми примерами, которые приводятся, и приложенные файлы помогут ему в этом. 
В случае если вы получили эту книгу без приложенных к ней файлов 
с примерами, вы всегда можете обратиться ко мне по электронной 
поч те (roman.dushkin@gmail.com), чтобы получить их.
Структура и стиль этой книги устроены так, что описание многих 
понятий вводится постепенно, как бы исподволь. Понимание концепций модели квантовых вычислений будет накатываться на читателя 
«волнами». И если в начале чтения книги может показаться, что чтото из написанного весьма непонятно, то дальше при изложении тех 
же понятий (возможно, иными словами и выражениями) понимание 
будет углубляться, расширяться и разъясняться. Я заранее прошу 
прощения у тех из читателей, кто сложно воспринимает подобный 
стиль, однако, по моему сугубому мнению, в данном издании именно 
он будет наиболее применим.
Я искренне надеюсь, что этот мой скромный труд даст начало новому направлению работы в нашем научном сообществе. Я буду рад 
всем конструктивным отзывам, комментариям, замечаниям и особенно благодарностям моих читателей.
В добрый путь!
Душкин Р. В.
Москва, 2014

Глава 1

Наивное понимание 
модели квантовых 
вычислений

Если вы думаете, что понимаете квантовую 
механику, значит, вы её не понимаете.

Ричард Фейнман

Книгу, текст которой вы читаете или просматриваете в настоящий 
момент (вы же вряд ли держите в руках бумажный экземпляр, но наверняка читаете с экрана или компьютера, или электронной книгочиталки), уважаемый читатель, вряд ли можно назвать книгой по квантовой механике. Здесь нет практически ничего из того, что обычно 
изучают в университетах на строгих курсах по «квантам», – всех этих 
уравнений Шрёдингера, Гейзенберга, Паули и т. д., фотоэффектов, парадоксов типа ЭПР, элементарных частиц и так называемой стандартной модели, квантования энергии и т. д., и т. п. Эта книга рассказывает 
о модели квантовых вычислений – новом способе осуществления вычислительных процессов таким образом, чтобы переложить на «квантовую природу» нашего мира возможность эффективной параллелизации вычислений. Квантовые вычисления – это пока лишь модель, 
которая ещё не нашла своего воплощения в «железе». Примерно так 
же воспринимали наши деды и прадеды вычислительную модель 
Тьюринга и фон Неймана, когда она только была разработана, – до 
полноценной реализации в «железе» тогда было ещё очень далеко 
(впрочем, некоторые пытались её реализовать в «дереве»).
В рамках кибернетики давно известен принцип, гласящий, что 
лучшей моделью системы является сама система. Видимо, используя именно этот принцип, Ричард Фейнман как-то выразил мнение, 

 Наивное понимание модели квантовых вычислений

что раз природа вокруг нас имеет квантово-механическую природу, 
то лучше всего её помогут смоделировать квантово-механические системы. Развивая эту мысль, можно сказать, что любое моделирование 
какого-либо физического процесса, выполненное при помощи современных средств вычислительной техники, будет неточным и неполным, но только лишь приближённым до какой-то степени точности, 
и у нас есть очень ограниченные средства повышения оной точности. 
В итоге любая такая модель так и останется неточной.
Однако если для моделирования использовать именно квантовомеханические системы с внутренне присущей им неопределённостью 
и недетерминированностью, то такое моделирование позволит точно 
отразить те физические процессы, которые в своей основе являются 
абсолютно такими же – неопределёнными и недетерминированными. 
Это понимание и стало основой развития модели квантовых вычислений.
Другой момент, который необходимо отразить в преддверии описания модели квантовых вычислений, относится к пониманию математики как научного языка. В самом общем понимании математика 
оперирует символами, при этом интерпретация символов всецело 
зависит от решаемой задачи, но не от самих символов. Математика 
прос то описывает алфавит, из которого можно создавать символы, 
задаёт систему аксиом и правил преобразования, при помощи которых можно оперировать символами чисто синтаксическим порядком. 
Именно так работает классический компьютер – «он» нисколько не 
понимает смысла производимых с битами (0 и 1) операций, «он» 
прос то манипулирует символами. И даже наименования для битов 
«0» и «1» – это чистая условность, которая введена людьми для собственного удобства, поскольку компьютер манипулирует двумя различимыми состояниями.
Таким образом, математика – это система синтаксического манипулирования символами. Конечно, это несколько однобокое понимание, и в рамках математики есть системы, которые отрицают или 
расширяют такой подход. Но в целом именно этим и занимаются 
учёные-математики, и чем выше уровень абстракции символов, которыми они оперируют, тем меньше в них реального смысла и больше 
чистого синтаксиса.
Принимая во внимание оба описанных соображения, можно сказать, что квантовые вычисления – это некоторая математическая модель, формализм, помогающий в теории осуществить решение задач, 
которые сложно решить в традиционной модели вычислений за при