автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритмическое и программное обеспечение для моделирования квантового компьютера

Московский государственный технический университет имени Н.Э. Баумана

На правах рукописи

00346Эьиь

Ключарёв Пётр Георгиевич

АЛГОРИТМИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ МОДЕЛИРОВАНИЯ КВАНТОВОГО КОМПЬЮТЕРА

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

Автореферат диссертации

на соискание ученой степени кандидата технических наук

1 А а

Москва 2009

003469605

Работа выполнена в те им. Н.Э. Баумана

Московском государственном техническом университе-

Научный руководитель:

кандидат технических наук, доцент Медведев Николай Викторович

Официальные оппоненты:

доктор технических наук, профессор Шеремет Игорь Анатольевич

кандидат технических наук, доцент Рудаков Игорь Владимирович

Ведущая организация:

Учреждение Российской академии наук Вычислительный центр им. А. А. Дородницына РАН.

Защита состоится 4 июня 2009 г. в 14 часов 30 минут на заседании диссертационного совета Д 212.141.10 в Московском государственном техническом университете им. Н.Э. Баумана по адресу: 105005, Москва, 2-ая Бауманская, д.5.

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета им. Н.Э. Баумана.

Автореферат разослан ¿Цу^ЛтД. 2009 г.

Ученый секретарь диссертационного совета

к.т.н., доцент Иванов С.Р.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

жет заменить квантового компьютера. Его возможности сильно ограничены, однако он позволит запускать и отлаживать квантовые программы, что очень ценно как для разработки новых квантовых алгоритмов, так и для целей обучения студентов основам квантовых вычислений. Курсы, посвященные квантовым вычислениям, в настоящее время читаются во многих высших учебных заведениях России, Европы и США. В ряде ВУЗов, например в Калифорнийском Техническом Университете и в МГУ им. Ломоносова, открыты кафедры квантовых вычислений.

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

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

Все это позволяет утверждать, что тема настоящей диссертации является актуальной.

Объектом исследования является математическая модель квантового компьютера.

Предметом исследования выступают методы моделирования работы квантового компьютера.

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

1. Разработать методы представления состояний квантовых регистров.

2. Разработать алгоритмы обработки информации о состоянии квантового регистра.

3. Разработать способ моделирования квантовых вычислений.

4. Разработать библиотеку функций, для моделирования операций над квантовыми регистрами.

5. Разработать язык описания квантовых алгоритмов.

6. Разработать интерпретатор языка описания квантовых алгоритмов. Методы исследования. Для решения поставленных задач в работе использовались методы дискретной математики, теории алгоритмов, функционального программирования.

Научная новизна.

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

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

• Разработан новый способ имитации квантовых вычислений. Особенностью этого способа является использование представления состояния квантового регистра в виде алгебраической решающей диаграммы. Этот способ позволяет получить большую производительность по сравнению с существующими способами в ряде задач.

• Разработан новый язык для описания квантовых алгоритмов и интерпретатор для него.

На защиту выносится:

• Алгоритмы для действий над матрицами и векторами, представленными в виде алгебраических решающих диаграмм.

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

• Язык для описания квантовых алгоритмов.

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

Апробация и внедрение результатов работы. Результаты диссертационной работы внедрены в Ракетно-космической корпорации «Энергия» им. С.П. Королева, а также в учебный процесс кафедры информационной безопасности МГТУ им. Н.Э. Баумана.

Основные результаты работы докладывались и обсуждались на ряде научных конференций, проводимых в МГТУ им. Н.Э. Баумана, а также на научных семинарах кафедры информационной безопасности МГТУ им. Н.Э. Баумана.

Публикации по теме диссертации. Основные результаты данной работы опубликованы в восьми научных трудах. В том числе две статьи опубликованы в изданиях, рекомендованных ВАК.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка и приложения. Основная часть диссертации изложена на 124 страницах текста. Библиографический список состоит из 98 наименований (из них 76 - на иностранных языках).

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе диссертации выполнен обзор литературы по теме диссертации. Рассмотрен математический аппарат теории квантовых вычислений. Рассмотрены основные понятия теории квантовых вычислений, такие, как квантовый бит (кубит) и квантовый регистр. В частности, состояние квантового регистра длины п представляет собой вектор в 2"-мерном унитарном пространстве и записывается в виде линейной комбинации базисных состояний:

2"-1 2"-1 |у/) = где ах е С. При этом, выполняется условие: = 1.

х=0 ЫО

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

вероятностью |а1|2 и после измерения регистр перейдет (часто используется термин сколлапсирует) в состояние соответствующее результату измерения. В случае измерения /-го разряда, результат и будет выбираться из множества {0;1} с вероятностью ри = ^ . После измерения, регистр перейдет в

хх1 =и

состояние , * а^х). Здесь запись х, означает ¡-ый разряд квантового

.ЕКГ

регистра. Измерение набора из п разрядов соответствует последовательному измерению разрядов из этого набора, при этом результат вычисления является

элементом множества {0;1}".

Квантовый компьютер может осуществлять преобразования над квантовым регистром: = (/|(//,). При этом оператор и является унитарным. С квантовыми системами можно производить только линейные унитарные преобразования, причем любое линейное унитарное преобразование допустимо. В силу линейности, квантовые преобразования полностью определяются их действием на базисные векторы. Существуют различные базисы квантовых преобразований, с помощью которых можно представить любое квантовое преобразование. Квантовый алгоритм представляет собой конечную последовательность квантовых преобразований над квантовым регистром и измерений квантового регистра.

Рассмотрен ряд квантовых алгоритмов. Так, рассмотрен алгоритм Грове-ра, который позволяет найти число, для которого выполняется заданный предикат. Кроме того, рассмотрены алгоритмы Шора для факторизации натуральных

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

Рассматриваются способы описания квантовых алгоритмов, такие как: квантовые схемы, квантовые машины Тьюринга, языки квантового программирования. Приводятся некоторые факты из теории сложности квантовых алгоритмов.

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

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

Рассмотрено существующее программное обеспечение для моделирования квантовых вычислений. Такое ПО можно классифицировать следующим образом:

По объекту моделирования:

1. Программное обеспечение, моделирующее поведение квантовой системы, путем решения уравнения Шредингера. Такие программы называют эмуляторами.

2. Программное обеспечение, моделирующее абстрактную математическую модель квантового компьютера. Такие программы называют имитаторами (simulators).

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

Наиболее популярны три способа описания квантового алгоритма:

1. Описание в виде квантовой схемы.

2. Описание в виде квантовой машины Тьюринга.

3. Описание в виде программы на некотором, специализированном языке программирования.

Делается вывод о том, что наиболее перспективным способом описания квантовых алгоритмов является использование языка квантового программирования.

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

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

Для успешной имитации квантовых алгоритмов, следует располагать способом описания таких алгоритмов. Таким образом, встает вопрос о разработке языка квантового программирования.

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

Предложен способ машинного представления квантовых регистров, основанный на алгебраических решающих диаграммах (АРД). Алгебраическая решающая диаграммы (Algebraic Decision Diagram) представляет собой обобщение двоичной решающей диаграммы (Binary Decision Diagram) на случай произвольного множества значений терминальных вершин. Способ основан на использовании алгебраических решающих диаграмм для хранения векторов состояний квантовых регистров, а также для хранения матриц квантовых преобразований. Использование АРД позволяет значительно уменьшить затраты памяти в случае кодирования матриц и векторов с повторяющимися значениями, за счет использования свойства сокращенности. И в то же время для производства операций над закодированными таким образом матрицами и векторами не требуется декодирование.

АРД предназначены для представления функций вида /: {0;1}" S, где

5 - произвольное множество (рассматривается случай линейно упорядоченного множества S). Векторы можно рассматривать в качестве таких функций и, сле-

довательно, представлять их в виде АРД. Матрицы также можно рассматривать в качестве таких функций. При этом на любой цепи дерева несокращенной АРД, представляющей матрицу, вершины, соответствующие номерам строк и номерам столбцов матрицы чередуются.

Для умножения матриц, представленных в виде АРД, разработан алгоритм, основанный на следующем. Если у - вершина, имеющаяся либо в АРД матрицы А, либо, матрицы В, то в случае, если переменная вершины V входит в состав номера столбца матрицы А (и, следовательно, номера строки матрицы В), выполняется:

где запись Д означает матрицу, задаваемую АРД с корневой вершиной V в АРД матрицы А.

В обратном случае (т.е. в случае если V входит в состав номера строки матрицы А или номера столбца матрицы В), выполняется:

ДД +1оф)ЛкжМВ1тМ

В случае если Д и д, - константы, произведение ДД может быть вычислено непосредственно.

С помощью изложенного способа становится возможным осуществлять умножение матриц, представленных с помощью алгебраических решающих диаграмм, без декодирования. На основе этого алгоритма умножения матриц, разработан алгоритм для умножения матрицы, представленной в виде АРД на вектор, представленный в виде АРД. На входе этот алгоритм получает вершину АРД матрицы (обозначим ее А), вершину АРД вектора (обозначим его х) и номер переменной этой вершины - к. Будем обозначать младшего потомка вершины х как 1о\у(дг), старшего — как Ы2Ь(.г), номер переменной, соответствующей вершине х - как уаг(х).

Если А и х - терминалы, то результат - терминал, равный Ах. Если \'аг(х) = к, то *о=1о\у(х) *1=Ы§Ь(х) Рх=0-Иначе рх= 1 Если уаг(А)=2х, то А0=1о\у (А) А,=ЫёЬ(А) ра=0

Если уаг(Ао)=2£-1, то А00=1о\у(А0) А0]=Ы§Ь (А0)

А/г 0

иначе

РоО-1

Если уаг(А])=2А:-1, то Аю^ЬшСАО Ац=1%11 (А])

Ра1=0 иначе ра]=1

Иначе

Ра= 1

Результат выбирается из табл. 1 (если выходом является АРД с двумя потомками, они приводится через точку с запятой; иначе - приводится одно значение). Умножения матрицы на вектор, приведенные в этой таблице вычисляются по тому же алгоритму, при этом на его вход подается в качестве номера переменной (¿-1).

Результатом является АРД, представляющая вектор, равный искомому произведению.

Предложен способ для вычисления кронекеровых произведений матриц, представленных в виде АРД. Пусть надо вычислить кронекерово произведение А ® В. Способ состоит в замене каждой терминальной вершины АРД матрицы А, на АРД матрицы Б • ?, где / - значение, сохраненное в заменяемой терминальной вершине.

Таблица 1.

К алгоритму умножения матрицы на вектор_

Ра РаО Ра\ Рх

0 1

0 0 0 Ао(рсо+Ао\Х1', (Аоо+Ао\)х;

А\срсо+АиХ1 А]оХо~*~АцХ1

0 0 1 А00х0+А01х1; (Аоо+Ао{)х-,

А](хо+Х]); 2А&

0 1 0 А0(хо+хО; 2Аох;

А\оХо+А\\Х\ АюХд+АцХ1

0 1 1 Ао(хо+х,); 2Аох;

А,(хо+х,); 2А \х

1 Ао(хп+х,); 2Ах;

Исследуется вопрос о строении матрицы преобразования, переставляющего разряды с номерами / и^' у квантового регистра длины и. Это преобразование можно записать следующим образом:

Р = /,10 <

)Р ®1

где 12 = 8

1 0Л О 1

- кронекерово произведение матриц, А = А<8) А® ...<8> А.

п раз

Рис. 1. Алгебраическая решающая диаграмма для матрицы Рюйэ (размера

1024x1024)

Пунктирными линиями обозначены ребра, помеченные 0, сплошными линиями - 1. Кругами (в кругах - номера переменных) обозначены нетерминальные вершины, квадратами (в квадратах - значения) -терминальные.

Сформулированы и доказаны теорема о структуре матриц P(;W+1)0(;W) и теорема о структуре АРД, с помощью которой можно представить матрицу P(j-M) о (/-о- В качестве примера приведем АРД для матрицы /}0 09 (размера

1024x1024) (рис.1). Эти теоремы позволили разработать алгоритм для построения АРД, соответствующей таким матрицам.

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

Разрабатывается способ имитации квантовых вычислений. Выполнение квантового алгоритма состоит из следующих этапов: инициализация квантовых регистров; квантовые преобразования и измерения; последнее измерение; получение и обработка результатов управляющим классическим компьютером. В случае необходимости - квантовые вычисления повторяются.

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

Квантовые преобразования выполняются в соответствии с формулой

\y) = p-\F®C)P\x),

где х - текущее состояние квантового регистра, длины п; у - новое значение регистра; F - матрица 2к х 2к преобразования, действующего на к кубитах; Р -матрица подстановки.

Рассмотрим теперь проведение измерений состояния квантовых регистров. Для проведения измерения одного разряда с номером к, требуется получить вероятности того, что значение этого разряда равно нулю р{хк = 0}= рп и

единице р{хк = 1} = /г, = 1 - р0. При этом р{хк = 0} = ^ |ах|2. После случайного

выбора результата измерения и, требуется перевести регистр в состояние \у)= ^ йг , что достигается использованием алгоритма Restrict с парамет-

г.хк =11

рами {v,к,и), где v - корневая вершина АРД, с последующей нормировкой. Алгоритм Restrict - известный из теории решающих диаграмм алгоритм, который преобразует решающую диаграмму с корневой вершиной v, путем приравнивания переменной и к значению к. После выполнения алгоритма Restrict выполняется нормировка вектора состояния, путем вычисления нормы вектора |t//) и

деления значений всех терминальных вершин АРД на ■ Измерение набора

кубитов сводится к последовательному измерению каждого кубита из набора.

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

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

В библиотеке функций для работы с алгебраическими решающими диаграммами для описания типа вершин используется тип, сочетающий в себе два типа вершин:

1. Нетерминальная вершина. Такую вершину можно представить в виде тройки (v,/,/>), где v,l,h е Ъ": v - номер переменной, соответствующей вершине, / - номер дочерней вершины, соответствующей нулевому значению переменной, h - номер вершины, соответствующей единичному значению переменной

2. Терминальная вершина. В такой вершине хранится значение.

Алгебраическая решающая диаграмма хранится в структуре данных, состоящей из двух таблиц:

W - таблица, реализующая функцию, отображающую вершины и в тройки (i,l,h), для нетерминальных вершин; и в значения х, для терминальных вершин.

Н - таблица, реализующая функцию, отображающую тройки (i,l,h), для нетерминальных вершин и значения х - для терминальных вершин, в и.

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

Таким образом, алгебраическая решающая диаграмма хранится в виде структуры данных, содержащей три элемента: таблицу W (представленную с помощью типа Sequence), таблицу Н (представленную с помощью типа Map) и номера корневой вершины, заключенного в монаду Maybe. Типы Map и Sequence входят в стандартную библиотеку языка Haskell и реализованы в ней с помощью сбалансированных бинарных деревьев.

Реализующий АРД тип ADD является параметризованным. При этом тип хранимых значений может быть любым типом, являющемся линейно упорядоченным (т.е. реализующим класс Ord), для значений которого реализуется операция сравнения (т.е. тип реализует класс Eq).

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

Разработана библиотека функций для имитации квантового компьютера. Это библиотека функций основана на представлении вектора состояния квантовых регистров и матриц квантовых преобразований в виде АРД. Элементами этих векторов и матриц являются комплексные числа, представленные в экспоненциальном виде, причем в качестве отношения порядка используется лексикографическое отношение пар (амплитуда, фаза).

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

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

Основными объектами, с которыми оперирует разработанный язык, являются: классическая переменная, представляющая целое неотрицательное число, квантовый регистр, преобразование.

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

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

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

Разработанный язык имеет операторы для: • определения входной переменной;

• определения квантового преобразования;

• определения квантового регистра;

• вычисления тензорного произведения квантовых регистров;

• применения квантового преобразования к квантовому регистру;

• последовательного применения одного и того же квантового преобразования к различным разрядам квантового регистра;

• измерения состояния набора разрядов квантового регистра;

• вычисления классической функции от квантового регистра;

• передачи результатов вычислений в управляющую программу.

В языке реализованы стандартные квантовые преобразования: отрицание, фазовый сдвиг, фазовый сдвиг с отрицанием, Controlled-NOT, вентиль Тофол-ли, преобразование Адамара. Кроме того, для увеличения производительности на уровне языка реализованы такие преобразования, как преобразование Фурье и инверсия относительно среднего. Имеется возможность задавать любые другие квантовые преобразования.

Интерпретатор реализован на языке Haskell с помощью генератора парсе-ров Happy и лексического анализатора Alex.

Число кубитов

-Разработанный имитатор--QCSim

Рис. 2. Время выполнения имитации одной итерации алгоритма Гровера

Кроме того, в этой главе приводятся замеры производительности разработанного интерпретатора, при моделировании алгоритма Гровера и квантового преобразования Фурье. Его производительность для случая алгоритма

Гровера сравнивается с производительностью имитатор рСБт, разработанного в МБТ (Национальный институт стандартов, США). В соответствии с этими замерами, производительность разработанного интерпретатора (рис. 2) существенно выше, чем производительность имитатора квантовых вычислений (ЗСБпп, который использует массивы для хранения информации о квантовых состояниях. Требования к памяти разработанного имитатора - существенно ниже, чем для (^СБии (рис. 3) и являются линейными относительно длины моделируемого квантового регистра.

Квантовое преобразование Фурье, при достаточно большой длине квантового регистра, также имитируется с более высокой скоростью, чем с помощью (2СБ1т (рис. 4) и при этом, требует меньше памяти (рис. 5).

Разработанный интерпретатор и является имитатором квантового компьютера.

1000

100

ю

г

0.01

10

35

40

45

15 20 25 30 Число кубитов — Разработанный имитатор — -С1С51т

Рис. 3. Требования к памяти, при имитации одной итерации алгоритма

Гровера

-Разработанный имитатор — — ЦС51т

Рис. 4. Время выполнения имитации квантового преобразования Фурье

1000

100

ю

г

Число кубитов

-Разработанный имитатор — — ЦС51т

Рис. 5. Требования к памяти для имитации квантового преобразования Фурье

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработаны алгоритмы для хранения векторов и матриц в виде алгебраических решающих диаграмм и алгоритмы для действий над ними.

2. Разработаны алгоритмы для имитации квантового компьютера.

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

4. Разработана библиотека функций для имитации квантовых вычислений.

5. Разработан язык для представления квантовых алгоритмов и интерпретатор этого языка.

Результаты настоящей работы будут способствовать разработке новых

квантовых алгоритмов.

РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ключарев П.Г. Алгебраический подход к диагностике отказов вычислительной системы специального назначения // Компьюлог. - 2002. - №2. -С. 41-43.

2. Ключарев П.Г. Информационные и телекоммуникационные системы, их воздействие на общественное и индивидуальное сознание // Студенческая научная весна - 2000: Тез. докл. научно-технической конференции. - М.: МГТУ им. Н.Э. Баумана, 2001. - С. 57-58.

3. Ключарев П.Г. Квантовый компьютер и криптографическая стойкость современных систем шифрования // Вестник МГТУ им. Н.Э. Баумана. Серия Естественные науки. - 2007. - №2. - С. 113-120.

4. Ключарев П.Г. Криптоаналитические возможности квантового компьютера // Прикаспийский журнал: управление и высокие технологии. - 2008. -№2.-С. 7-13.

5. Ключарев П.Г. Основы квантовых вычислений и квантовой криптографии // Вестник МГТУ им. Н.Э. Баумана. Серия Приборостроение. - 2006. -№2. - С. 36-46.

6. Ключарев П.Г. Программная реализация двоичных регистров сдвига с обратной связью // Студенческая научная весна: Тез. докл. научно-технической конференции. - М.: МГТУ им. Н.Э. Баумана, 2002 -С. 125126.

7. Ключарев П.Г. Свобода и безопасность личности в условиях информационного общества // Тезисы Второго Международного конгресса Молодежь и наука-третье тысячелетие, 2001. - С. 125-126.

8. Ключарев П.Г. Социокультурная компетентность как одно из условий обеспечения информационной безопасности в Российской Федерации // Реформы в России и мире: компаративный анализ: Тез. докл. научно-технической конференции. - М.: МГТУ им Н.Э. Баумана, 2000. - С. 63-65.

Подписано к печати 22.04.09. Заказ № 297 Объем 1,0 печ.л. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 263-62-01

ВВЕДЕНИЕ.

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ.

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

1.1.1. Краткая история теории квантовых вычислений.

1.1.2. Общая информация о квантовых вычислениях.

1.2. Квантовые алгоритмы.

1.2.1. Общие сведения.

1.2.2. Алгоритм поиска Гровера.

1.2.3. Квантовое преобразование Фурье.

1.2.4. Квантовый алгоритм нахождения периода функции

1.2.5. Алгоритм разложения числа на простые множители (Алгоритм Шора).

1.2.6. Квантовый алгоритм вычисления дискретного логарифма

1.2.7. Другие квантовые алгоритмы.

1.3. Способы описания квантовых алгоритмов.

1.3.1. Квантовые схемы.

1.3.2. Квантовая машина Тьюринга.

1.3.3. Сложность квантовых вычислений.

1.3.4. Языки квантового программирования.

1.4. Организация квантового компьютера.

1.5. Реализация квантовых компьютеров.

1.6. Квантовые компьютеры и информационная безопасность

1.7. Моделирование квантовых компьютеров.

1.8. Выводы.

ГЛАВА 2. АЛГОРИТМЫ ДЛЯ ИМИТАЦИИ КВАНТОВОГО КОМПЬЮТЕРА

2.1. Квантовые регистры.

2.2. Использование линейного массива для хранения вектора состояния квантового регистра.

2.3. Использование связного списка для хранения вектора состояния квантового регистра.

2.4. Использование структуры данных, основанной на графах для хранения вектора состояния квантового регистра.

2.4.1. Алгебраические решающие диаграммы.

2.4.2. Алгоритм построения алгебраических решающих диаграмм

2.4.3. Кодирование матриц и векторов.

2.4.4. Квантовые преобразования.

2.5. Алгоритмы для имитации квантового компьютера.74 г

2.5.1. Способ имитации квантового компьютера.

2.5.2. Имитация квантовых преобразований.

2.5.3. Имитация измерений квантовых регистров.

2.6. Выводы.

ГЛАВА 3. РЕАЛИЗАЦИЯ БИБЛИОТЕКИ ФУНКЦИЙ.

3.1. Выбор языка программирования.

3.2. Реализация библиотеки функций для работы с алгебраическими решающими диаграммами.

3.3. Реализация библиотеки функций для работы с векторами

3.4. Примеры эффективного применения алгебраических решающих диаграмм.

3.5. Реализация библиотеки функций для моделирования квантового компьютера.

3.6. выводы.

ГЛАВА 4. ЯЗЫК ДЛЯ ПРЕДСТАВЛЕНИЯ КВАНТОВЫХ АЛГОРИТМОВ

4.1. постановка задачи.

4.2. Требования к языку.

4.3. Описание языка.

4.3.1. Структура языка.

4.3.2. Стандартные преобразования.

4.4. Примеры программ.

4.4.1. Программа факторизации натурального числа с помощью квантового алгоритма Шора.

4.5. Программа, реализующая алгоритм Гровера.103г.

4.6. Интерпретатор.

4.6.1. Общие сведения.

4.6.2. Использование интерпретатора.

4.7. Тестирование производительности.

4.8. Выводы.

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

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

Квантовых алгоритмов на настоящий момент известно мало. Наиболее важные - это квантовый алгоритм факторизации натуральных чисел и квантовой алгоритм дискретного логарифмирования, разработанные П. Шором (1994 г.), а также алгоритм поиска, разработанный Л. Гровером (1996 г.). Кроме того, существуют квантовые алгоритмы для решения некоторых математических задач, практическая ценность которых пока не ясна. Такое положение вещей, по-видимому, обусловлено в частности отсутствием возможности запуска и отладки сколь-нибудь сложных квантовых алгоритмов.

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

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

В условиях отсутствия практических квантовых компьютеров, встает задача разработки комплекса программ для моделирования квантового компьютера. Следует заметить, что такой комплекс программ ни коем образом не может заменить квантового компьютера. Его возможности сильно ограничены, однако он позволит запускать и отлаживать квантовые программы, что очень ценно как для разработки новых квантовых алгоритмов, так и для целей обучения студентов основам квантовых вычислений. Курсы, посвященные квантовым вычислениям, в настоящее время читаются во многих высших учебных заведениях России, Европы и США. В ряде ВУЗов, например в Калифорнийском Техническом Университете и в МГУ им. Ломоносова, открыты кафедры квантовых вычислений.

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

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

Для достижения этой цели в диссертации необходимо решить следующие задачи:

1. Разработать метод представления состояний квантовых регист-, V ров.

2. Разработать алгоритм обработки информации о состоянии квантового регистра.

3. Разработать способ моделирования квантовых вычислений.

4. Разработать библиотеку функций, реализующих операции над' квантовыми регистрами.

5. Разработать язык описания квантовых алгоритмов.

6. Разработать интерпретатор языка описания квантовых алгоритмов.

Объектом исследования является математическая модель квантового компьютера.

Предметом исследования выступают методы моделирования работы квантового компьютера.

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

Научная новизна.

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

• Разработан новый способ имитации квантовых вычислений. Особенностью этого способа является использование представления состояния кванто- ^ вого регистра в виде алгебраической решающей диаграммы. Этот способ позволяет получить большую производительность по сравнению с существующими способами в ряде задач.

• Разработан новый язык для описания квантовых алгоритмов и интерпретатор для него.

На защиту выносится:

• Алгоритмы для действий над матрицами и векторами, представленными в виде алгебраических решающих диаграмм.

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

• Язык для описания квантовых алгоритмов.

• Программное обеспечение для имитации квантового компьютера.

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

Апробация и внедрение результатов работы. Результаты диссертационной работы внедрены в Ракетно-космической корпорации «Энергия» им. С.П. Королева, а также в учебный процесс кафедры информационной безопасности МГТУ им. Н.Э. Баумана.

Основные результаты работы докладывались и обсуждались на ряде научных конференций, проводимых в МГТУ им. Н.Э. Баумана, а также на научных семинарах кафедры информационной безопасности МГТУ им. Н.Э. Баумана.

Публикации по теме диссертации. Основные результаты данной работы опубликованы в восьми печатных трудах. В том числе две статьи опубликованы в изданиях, рекомендованных ВАК.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка и приложения. Библиографический список состоит из 99 наименований.

4.8. Выводы

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

Основными объектами, с которыми оперирует разработанный язык, являются: классическая переменная, представляющая целое неотрицательное число, квантовый регистр, преобразование.

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

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

Разработан интерпретатор этого языка. Этот интерпретатор является имитатором квантового компьютера. Интерпретатор разработан на языке функционального программирования Haskell.

Произведено тестирование производительности интерпретатора, которое показала его превосходство по быстродействию и требованиям к памяти, над имитатором С2С8нп, разработанным в М8Т, на ряде квантовых алгоритмов.

Заключение и общие выводы

В диссертации получен ряд важных результатов, таких как:

• Разработаны алгоритмы для хранения векторов и матриц над произвольными линейно упорядоченными полями в виде алгебраических решающих диаграмм и алгоритмы для действий над ними.

• Разработаны алгоритмы для имитации квантового компьютера.

• Разработана библиотека функций, на языке функционального программирования Haskell, для работы с алгебраическими решающими диаграммами, а также с векторами и матрицами, хранимыми в виде алгебраических решающих диаграмм

• Разработана библиотека функций для имитации квантовых вычислений.

• Разработан язык для представления квантовых алгоритмов и интерпретатор этого языка.

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

Результаты настоящей работы будут способствовать разработке новых квантовых алгоритмов.

1. Алферов А.П. Основы криптографии. — М.: Гелиос АРВ, 2002. - 480 с.

2. Валиев К.А., Кокин К.А. Квантовые компьютеры: надежды и реальность. — М.: Регулярная и хаотическая динамика, 2001. 352 с.

3. Вирт Н. Библиотека программиста. Алгоритмы и структуры данных. — СПб.: Нев. диалект, 2001. 351 с.

4. Душкин Р.В. Справочник по языку Haskell. М.: ДМК, 2008. - 544 с.

5. Душкин Р.В. Функциональное программирование на языке Haskell. -М.: ДВК, 2006.-608 с.

6. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. М.: Кудиц-образ, 2001. - 363 с.

7. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО, 1999. - 192 с.

8. Ключарев П.Г. Алгебраический подход к диагностике отказов вычислительной системы специального назначения // Компыолог. 2002. -№2. - С. 25-28.

9. Ключарев П.Г. Информационные и телекоммуникационные системы, их воздействие на общественное и индивидуальное сознание // Студенческая научная весна 2000: Тез. докл. научно-технической конференции. - М.: МГТУ им. Н.Э. Баумана, 2001. - С. 57-58.

10. Ключарев П.Г. Квантовый компьютер и криптографическая стойкость современных систем шифрования // Вестник МГТУ им. Н.Э. Баумана. Серия Естественные науки. 2007. — №2. — С. 113-120.

11. Ключарев П.Г. Криптоаналитические возможности квантового компьютера // Прикаспийский журнал: управление и высокие технологии. — 2008.- №2.-С. 7-13.

12. Ключарев П.Г. Основы квантовых вычислений и квантовой криптографии // Вестник МГТУ им. Н.Э. Баумана. Серия Приборостроение. -2006. №2. - С. 36-46.

13. Ключарев П.Г. Программная реализация двоичных регистров сдвига с обратной связью // Студенческая научная весна: Тез. докл. научно-технической конференции. М.: МГТУ им. Н.Э. Баумана, 2002 -С. 125126.

14. Ключарев П.Г. Свобода и безопасность личности в условиях информационного общества // Тезисы Второго Международного конгресса Молодежь и наука третье тысячелетие, 2001. - С. 125-126.

15. Ландау Л.Д., Лифшиц Е.М. Квантовая механика. М.: Мир, 1982. - 342 с.

16. Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. — М.: Мир, 2006.-824 с.

17. Ожигов Ю.И. Квантовые вычисления. М.: Фак. Вычисл. математики и кибернетики МГУ им. М.В. Ломоносова, 2003. - 151 с.

18. Савельев И.В. Квантовая механика. М.: Наука, 1996. - 430 с.

19. Стин Э. Квантовые вычисления. Ижевск: Регулярная и хаотическая динамика, 2000. - 111 с.

20. Фомичев В.М. Дискретная математика и криптология. М.: Диалог-МИФИ, 2003.-400 с.

21. Шнайер Б. Прикладная криптография. М.: Триумф, 2002. - 815 с.

22. Abrams D.S., Lloyd S. Simulation of Many-Body Fermi Systems on a Universal Quantum Computer // Physical Review Letters. 1997. - Vol. 79, №13.-P. 2586-2589.

23. ACM Special Interest Group on Programming Languages., Association for Computing Machinery. Haskell '04: proceedings of the ACM SIGPLAN 2004 Haskell Workshop. New York: ACM Press, 2004. - 117 p.

24. ACM Spécial Interest Group on Programming Languages. Haskell '05: proceedings of the ACM SIGPLAN 2005 Haskell Workshop. New York: ACM Press, 2005.- 117 p.

25. ACM Special Interest Group on Programming Languages. Haskell '06: proceedings of the ACM SIGPLAN 2006 Haskell workshop. New York: Association for Computing Machinery, 2006. - 123 p.

26. Adleman L.M., DeMarrais J., Huang M.D.A. Quantum Computability // SIAM Journal on Computing. 1997. - Vol. 26, №5. - P. 1524-1540.

27. Andersen H.R., Hulgaard H. Boolean Expression Diagrams // Information and Computation. 2002. - Vol. 179, №2. - P. 194-212.

28. Association for Computing Machinery., ACM Special Interest Group on Programming Languages. Proceedings of the ACM SIGPLAN 2003 Haskell Workshop. New York, N.Y.: ACM Press, 2003. - 108 p.

29. Bahar R.I., Frohm E.A., Gaona C.M. Algebric Decision Diagrams and Their Applications // Formal Methods in System Design. 1997. - Vol. 10, №2. — P. 171-206.

30. Barenko A. Elementary gates for quantum computation // Physical Review.- 1995. Vol. A52, №5. - P. 3457-3467.

31. Beatty D.L., Bryant R.E. Formally verifying a microprocessor using a simulation methodology // Proceedings of the 31 st annual conference on Design automation. 1994. - P. 596-602.

32. Benioff P. Models of Quantum Turing machines // Fortschritte der Physik. — 1998. Vol. 46, №4-5. - P. 135-149.

33. Bennett C.H., Bessette F., Brassard G. Experimental quantum cryptography // Journal of Crypto logy. 1992. - Vol. 5, №1. - p. 3-28.

34. Bernstein E., Vazirani U. Quantum complexity theory // Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. 1993. - P. 11-20.

35. Bernstein E., Vazirani U. Quantum Complexity Theory // SIAM J. Comput. 1997. - Vol. 26, №5. - P. 1411-1473.

36. Betelli S., Calarco T., Serafini L. Toward an architecture for quantum programming // The European Physical Journal D. 2003. - Vol. 25, P. 181200.

37. Bird R. Introduction to functional programming, Haskell 1.3. — London: Prentice Hall Europe, 1998. 433 p.

38. Black P.E., Lane A.W. Modeling Quantum Information Systems // Proc. of The Interational Society for Optical Engineering. 2004. - №5436. - P. 340-347.

39. Blaha S. Quantum Computers and Quantum Computer Languages // Cosmos and consciousness. Bloomington: 1st Books Library, 2000. - P. 57-93.

40. Boghosian B.M., Taylor W. Simulating quantum mechanics on a quantum computer // Physica D: Nonlinear Phenomena. 1998. - Vol. 120, №1-2. -P. 30-42.

41. Boneh D., Lipton R.J. Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract) // Proceedings of the 15th Annual International Cryp-tology Conference on Advances in Cryptology. 1995. - P. 424-437.

42. Brace K.S., Rudell R.L., Bryant R.E. Efficient implementation of a BDD package // Design Automation Conference, 1990. Proceedings. 27th ACM/IEEE. 1990. - P. 40-45.

43. Brassard G., Salvail L. Secret-key reconciliation by public discussion // Advances in Cryptology: EUROCRYPT 93. - 1993. - P. 410-423.

44. Bryant R.E. Binary decision diagrams and beyond: Enabling technologies for formal verification // Proceedings of the International Conference on Computer-Aided Design. 1995. - P. 236-243.

45. Bryant R.E. Graph-based algorithms for Boolean function manipulation // IEEE Transactions on Computers. 1986. - Vol. 35, №8. - P. 677-691.

46. Bryant R.E. Symbolic Boolean manipulation with ordered binary-decision diagrams // ACM Computing Surveys (CSUR). 1992. - Vol. 24, №3. - P. 293-318.

47. Brylinski R.K., Chen G. Mathematics of quantum computation. Boca Raton: CRC Press, 2002. - 429 p.

48. Burch J.R., h jvp. Sequential circuit verification using symbolic model checking // Design Automation Conference, 1990. Proceedings. 27th ACM/IEEE. 1990. - P. 46-51.

49. Chau H.F. Practical scheme to share a secret key through a quantum channel with a 27.6% bit error rate // Physical Review A. 2002. - Vol. 66, №6. - P. 603-622.

50. Chen G., Kauffman L.H., Lomonaco S.J. Mathematics of quantum computation and quantum technology. Boca Raton: Chapman & Hall/CRC, 2008. -605 p.

51. Cirac J., Zoller P. Quantum Computation with Cold Trapped Ions // Physycal Review Letters. 1995. - Vol. 74, №20. - P. 4091-4094.

52. Clarke E., Fujita M., McGeer P. Multi-terminal binary decision diagrams: An efficient data structure for matrix representation // Formal Methods in System Design. 1997. - Vol. 10, №2-3. - P. 149-169.

53. Clarke E.M., Fujita M., Zhao X. Hybrid decision diagrams // Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design. — 1995.- P. 159-163.

54. Clarke E.M., Grumberg O., Peled D.A. Model Checking. Cambridge, MA: MIT Press, 2000.-330 p.

55. Cleve R. An introduction to quantum complexity theory // Collected Papers on Quantum Computation and Quantum Information Theory, World Scientific. 2000. - P. 103-127.

56. Cleve R. The query complexity of order-finding // Proceedings of 15th IEEE Conference on Computational Complexity. 2000. — P. 54-59.

57. Cousineau G., Mauny M. The functional approach to programming. Cambridge, U.K. ; New York, NY, USA: Cambridge University Press, 1998. -445 p.

58. Crandall R.E., Pomerance C. Prime Numbers a Computational Perspective. Springer, 2005. 597 p.

59. Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer // Proceedings of the Royal Society of London. 1985. -Vol. A400,№1818.-P. 97-117.

60. Diffie W., Hellman M. New directions in cryptography // Information Theory, IEEE Transactions on. 1976. - Vol. 22, №6. - P. 644-654.

61. Ekert A. Quantum algorithms: entanglement-enhanced information processing // Philosophical Transactions: Mathematical, Physical and Engineering Sciences. 1998. - Vol. 356, №1743. -P. 1769-1782.

62. Elliott C., Colvin A., Pearson D. Current status of the DARPA quantum network // Enabling Photonics Technologies for Defense, Security, and Aerospace Applications. Proceedings of the SPIE. 2005. - №5815. - P. 138149.

63. Elliott C., Pearson D., Troxel G. Quantum cryptography in practice // Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications. 2003. - P. 227-238.

64. Feynman R. Quantum Mechanical Computers // Foundations of Phisycs. — 1986.-Vol. 16, №6.-P. 507-531.

65. Feynman R. Simulating Physics with Computers // International Journal of Theoretical Physics. 1982. - Vol. 21, №6. - P. 467-488.

66. Fortnow L. One complexity theorist's view of quantum computing // Theoretical Computer Science. 2003. - Vol. 292, P. 597-610.

67. Glendinning I., Omer B. Parallelization of the QC-lib Quantum Computer Simulator Library // Parallel processing and applied mathematics: 5th International Conference, PPAM 2003, LNCS -2003. Vol. 3019, P. 461-468.

68. Grover L.K. A fast quantum mechanical algorithm for database search // Proceedings, 28th Annual ACM Symposium on the Theory of Computing.- 1996.- P. 212-232.

69. Grover L.K. Quantum Mechanics Help in Searching for a Needle in a Haystack // Phys. Rev. Lett. 1997. - Vol. 78, №2. - P. 325-328.

70. Hankerson D.R., Vanstone S.A., Menezes A.J. Guide to elliptic curve cryptography. New York: Springer, 2003. - 311 p.

71. Hopcroft J.E., Motwani R., Ullman J.D. Introduction to automata theory, languages, and computation. Boston: Addison-Wesley, 2001. - 521 p.

72. Hudak P. The Haskell school of expression : learning functional programming through multimedia. New York: Cambridge University Press, 2000.363 p.

73. Hutton G. Programming in Haskell. Cambridge, UK ; New York: Cambridge University Press, 2007. - 171 p.

74. Massar S., h Classical simulation of quantum entanglement without local hidden variables // Physical Review. 2001. - Vol. 63, №5. - P. 78-86.

75. Michielsen K., Raedt H. QCE: A Simulator for Quantum Computer Hardware // Turkish Journal of Physics. 2003. - Vol. 27, №5. - P. 343-370.

76. Michielsen K., Raedt K., Raedt H. Simulation of Quantum Computation: A Deterministic Event-Based Approach // Journal of Computational and Theoretical Nanoscience. 2005. - Vol. 2, №2. - P. 227-239.

77. Michielsen K., Raedt H., Raedt K. A simulator for quantuim computer hardware // Nanotechnology. 2002. - Vol. 13, №1. - P. 23-28.

78. Niwa J., Matsumoto K., Imai H. General-purpose parallel simulator for quantum computing // Physical Review A. 2002. - Vol. 66, №6 -P. 64-72.

79. Obenland K., Despain A. A Parallel Quantum Computer Simulator // High Performance Computing. 1998. - P. 73-98.

80. Okasaki C. Purely functional data structures. Cambridge, U.K. ; New York: Cambridge University Press, 1998. - 220 p.

81. Omer B. Classical Concepts in Quantum Programming // International Journal of Theoretical Physics. 2005. - №44/7. - P. 943-955.

82. Omer B. Procedural Quantum Programming // CASYS 2001 5th International Conference, AIP Conference Proceedings. - 2001. - №627. - P. 276285.

83. Peyton Jones S.L. Haskell 98 language and libraries : the revised report. -Cambridge, U.K. ; New York: Cambridge University Press, 2003. 255 p.

84. Pomerance C. A Tale of Two Sieves // Not. Amer. Math. Soc. 1996. - Vol. 43, P. 1473-1485.

85. Proos J.A. Shor's discrete logarithm quantum algorithm for elliptic curves. -Waterloo, Ont.: Faculty of Mathematics University of Waterloo, 2003. 351. P

86. Rabhi F., Lapalme G. Algorithms: a functional programming approach. -Harlow, England: Addison-Wesley, 1999. 235 p.

87. Runciman C., Wakeling D. Applications of functional programming. — London: UCL Press, 1995. 240 p.

88. Sanders J.W., Zuliani P. Quantum Programming // Mathematics of Program Construction, Springer LNCS. 2000. - №1837. - P. 127-139.

89. Sasao T. Representations of Discrete Functions. Kluwer Academic Publishers, 1996.-353 p.

90. Schmitt-Manderbach T., Weier H., Ursin R. Experimental Demonstration of Free-Space Decoy-State Quantum Key Distribution over 144 km // Physical Review Letters. 2007. - Vol. 98, №1. - P. 105-124.

91. Shor P. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // Proceedings of the 35th Annual Symposium on Foundations of Computer Science. 1994. — P. 11-20.

92. Sornborger A.T., Stewart E.D. Higher-order methods for simulations on quantum computers // Physical Review A. 1999. - Vol. 60, №3. - P. 19561965.

93. Thompson S. Haskell: the craft of functional programming. Harlow, Eng.: Addison Wesley, 1999. - 487 p.

94. Yao A. Quantum circuit complexity // Proceedings of the 34th Annual Symposium on Foundations of Computer Science. 1993. - P. 352-361.

95. Zalka C. Simulating quantum systems on a quantum computer // Royal Society of London Proceedings: Mathematical, Physical and Engineering Sciences. 1998. - Vol. 454, №1969. - P. 313-322.