Содержание к диссертации
Введение
Глава 1. Квантовые вычисления 12
1.1. Квантовые вычисления 12
1.1.1. Краткая история теории квантовых вычислений 12
1.1.2. Общая информация о квантовых вычислениях 13
1.2. Квантовые алгоритмы 18
1.2.1. Общие сведения 18
1.2.2. Алгоритм поиска Гровера 18
1.2.3. Квантовое преобразование Фурье 20
1.2.4. Квантовый алгоритм нахождения периода функции 21
1.2.5. Алгоритм разложения числа на простые множители (Алгоритм Шора) 22
1.2.6. Квантовый алгоритм вычисления дискретного логарифма 23
1.2.7. Другие квантовые алгоритмы 24
1.3. Способы описания квантовых алгоритмов 25
1.3.1. Квантовые схемы 25
1.3.2. Квантовая машина Тьюринга 28
1.3.3. Сложность квантовых вычислений 29
1.3.4. Языки квантового программирования 30
1.4. Организация квантового компьютера 31
1.5. Реализация квантовых компьютеров 31
1.6. Квантовые компьютеры и информационная безопасность 32
1.7. Моделирование квантовых компьютеров 37
1.8. Выводы 38
Глава 2. Алгоритмы для имитации квантового компьютера 40
2.1. Квантовые регистры 40
2.2. Использование линейного массива для хранения вектора состояния квантового регистра 40
2.3. Использование связного списка для хранения вектора состояния квантового регистра 42
2.4. Использование структуры данных, основанной на графах для хранения вектора состояния квантового регистра 42
2.4.1. Алгебраические решающие диаграммы 42
2.4.2. Алгоритм построения алгебраических решающих диаграмм 45
2.4.3. Кодирование матриц и векторов 53
2.4.4. Квантовые преобразования 60
2.5. Алгоритмы для имитации квантового компьютера 74 t
2.5.1. Способ имитации квантового компьютера 74
2.5.2. Имитация квантовых преобразований 74
2.5.3. Имитация измерений квантовых регистров 75
2.6. Выводы 76
Глава 3. Реализация библиотеки функций 77
3.1. Выбор языка программирования 77
3.2. Реализация библиотеки функций для работы с алгебраическими решающими диаграммами 79
3.3. Реализация библиотеки функций для работы с векторами 86
3.4. Примеры эффективного применения алгебраических решающих диаграмм 88
3.5. Реализация библиотеки функций для моделирования квантового компьютера 91
3.6. Выводы 95
Глава 4. Язык для представления квантовых алгоритмов 97
4.1. Постановка задачи 97
4.2. Требования к языку 97
4.3. Описание языка 98
4.3.1. Структура языка 98
4.3.2. Стандартные преобразования 101
4.4. Примеры программ 103
4.4.1. Программа факторизации натурального числа с помощью квантового алгоритма Шора 103
4.5. Программа, реализующая алгоритм гровера 103
4.6. Интерпретатор 104
4.6.1. Общие сведения 104
4.6.2. Использование интерпретатора 105
4.7. Тестирование производительности 106
4.8. Выводы 113
Заключение и общие выводы 115
Литература 116
Приложение... 125
- Алгоритм разложения числа на простые множители (Алгоритм Шора)
- Квантовые компьютеры и информационная безопасность
- Использование структуры данных, основанной на графах для хранения вектора состояния квантового регистра
- Примеры эффективного применения алгебраических решающих диаграмм
Введение к работе
В настоящее время активно развивается теория квантовых вычислений. Несмотря на то, что идея квантового компьютера была высказана еще Р. Фейнманом в 1982 г. и с тех пор проводятся научные исследования по этой тематике, квантовые компьютеры еще не созданы. Однако, уже сейчас ясно, что теоретических ограничений для этого нет. Кроме того, имеются определенные достижения в области теории квантовых вычислений.
Несмотря на то, что квантовому компьютеру присущи некоторые особенности (например, вычисления на квантовом компьютере могут быть только обратимыми), любой алгоритм, предназначенный для классического компьютера, можно реализовать и для квантового. Кроме того, квантовый компьютер обладает серьезными преимуществами, по сравнению с классическим компьютером - квантовым параллелизмом, который позволяет одновременно производить вычисления с различными исходными данными. Существуют так называемые квантовые алгоритмы, то есть алгоритмы, использующие преимущества квантового компьютера. Квантовые алгоритмы позволяют решать некоторые задачи значительно более эффективно по сравнению с классическими алгоритмами.
Квантовых алгоритмов на настоящий момент известно мало. Наиболее важные - это квантовый алгоритм факторизации натуральных чисел и квантовой алгоритм дискретного логарифмирования, разработанные П. Шором (1994 г.), а также алгоритм поиска, разработанный Л. Гровером (1996 г.). Кроме того, существуют квантовые алгоритмы для решения некоторых математических задач, практическая ценность которых пока не ясна. Такое положение вещей, по-видимому, обусловлено в частности отсутствием возможности запуска и отладки сколь-нибудь сложных квантовых алгоритмов.
Существующие квантовые алгоритмы имеют значительно меньшую вычислительную сложность, по сравнению классическими аналогами. Так,
квантовые алгоритмы факторизации натуральных чисел и дискретного логарифмирования имеет полиномиальную сложность, в то время как классические аналоги имеют надполиномиальную сложность. Это позволяет надеяться на то, что возможно построение эффективных квантовых алгоритмов для решения каких-либо других задач.
В связи с наличием эффективных квантовых алгоритмов факторизации целых чисел и вычисления дискретного логарифма, можно утверждать, что разработка практических образцов квантовых компьютеров приведет к тому, что основные ассиметричные криптографические алгоритмы окажутся нестойкими. Такие криптоалгоритмы используются для шифрования данных, для электронных цифровых подписей, а также для распределения криптографических ключей. Нестойкость этих криптоалгоритмов повлечет за собой, нарушение секретности больших объемов информации во всем мире, что приведет к серьезным и труднопредсказуемым последствиям для информационной безопасности государств, различных предприятий, в том числе банков, а также физических лиц.
В условиях отсутствия практических квантовых компьютеров, встает задача разработки комплекса программ для моделирования квантового компьютера. Следует заметить, что такой комплекс программ ни коем образом не может заменить квантового компьютера. Его возможности сильно ограничены, однако он позволит запускать и отлаживать квантовые программы, что очень ценно как для разработки новых квантовых алгоритмов, так и для целей обучения студентов основам квантовых вычислений. Курсы, посвященные квантовым вычислениям, в настоящее время читаются во многих высших учебных заведениях России, Европы и США. В ряде ВУЗов, например в Калифорнийском Техническом Университете и в МГУ им. Ломоносова, открыты кафедры квантовых вычислений.
Вместе с тем, возникает задача разработки языка для описания алгоритмов для квантового компьютера. Несмотря на то, что в настоящее время
разработано уже несколько таких языков, только для одного из них создан интерпретатор, позволяющий выполнять программы, написанные на этом языке. Эти языки имеют ряд недостатков, которые затрудняют их практическое использование, а интерпретатор имеет ряд ограничений, также затрудняющих его практическое использование.
Целью диссертационной работы является разработка алгоритмов для имитации квантового компьютера, разработка программного обеспечения на основе этих алгоритмов и создание языка описания квантовых алгоритмов.
Для достижения этой цели в диссертации необходимо решить следующие задачи:
Разработать метод представления состояний квантовых регист-^ ров.
Разработать алгоритм обработки информации о состоянии кван-тового регистра.
Разработать способ моделирования квантовых вычислений.
Разработать библиотеку функций, реализующих операции над' квантовыми регистрами.
Разработать язык описания квантовых алгоритмов.
6. Разработать интерпретатор языка описания квантовых алгорит
мов.
Объектом исследования является математическая модель квантового компьютера.
Предметом исследования выступают методы моделирования работы квантового компьютера.
Методы исследования. Для решения поставленных задач в работе использовались методы дискретной математики, теории сложности алгоритмов, функционального программирования.
Научная новизна.
Разработан новый способ представления матриц и векторов. Особенностью способа является то, что матрицы и вектора представляются в виде графов специального вида - алгебраических решающих диаграмм. Разработаны новые алгоритмы для действий над матрицами и векторами, представленными в виде алгебраических решающих диаграмм.
Разработан новый способ имитации квантовых вычислений. Особенностью этого способа является использование представления состояния кванто- ^ вого регистра в виде алгебраической решающей диаграммы. Этот способ позволяет получить большую производительность по сравнению с существую-щими способами в ряде задач.
Разработан новый язык для описания квантовых алгоритмов и интерпретатор для него.
На защиту выносится:
Алгоритмы для действий над матрицами и векторами, представленными в виде алгебраических решающих диаграмм.
Способ имитации квантовых вычислений, основанный на использовании алгебраических решающих диаграмм.
Язык для описания квантовых алгоритмов.
Программное обеспечение для имитации квантового компьютера.
Практическая значимость. Разработана библиотека функций для имитации квантового компьютера. На основе этой библиотеки разработан интерпрета-
тор языка описания квантовых алгоритмов. Разработанное программное обеспечение может быть использовано как в качестве инструмента для отладки квантовых алгоритмов, так и в качестве средства для обучения студентов основам квантовых вычислений.
Апробация и внедрение результатов работы. Результаты диссертационной работы внедрены в Ракетно-космической корпорации «Энергия» им. СП. Королева, а также в учебный процесс кафедры информационной безопасности МГТУ им. Н.Э. Баумана.
Основные результаты работы докладывались и обсуждались на ряде научных конференций, проводимых в МГТУ им. Н.Э. Баумана, а также на научных семинарах кафедры информационной безопасности МГТУ им. Н.Э. Баумана.
Публикации по теме диссертации. Основные результаты данной работы опубликованы в восьми печатных трудах. В том числе две статьи опубликованы в изданиях, рекомендованных ВАК.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка и приложения. Библиографический список состоит из 99 наименований.
В первой главе диссертации выполнен обзор литературы по теме диссертации. Рассмотрен математический аппарат теории квантовых вычислений. Рассмотрены способы представления квантовых алгоритмов, такие как схемы из обратимых элементов, квантовые машины Тьюринга, квантовые языки программирования. Рассмотрены существующие квантовые алгоритмы, такие как алгоритмы Шора и алгоритм Гровера. Рассмотрено применение
существующих квантовых алгоритмов в целях криптоанализа. Рассмотрены существующие способы и средства для моделирования квантовых вычислений.
Во второй главе рассматриваются различные способы представления квантовых алгоритмов. Разрабатывается способ кодирования матриц и векторов над полем комплексных чисел, основанный на графах специального вида - алгебраических решающих диаграмм (АРД). Разработаны алгоритмы для вычисления произведения матриц, заданных таким способом; произведения матрицы на вектор; кронекерова произведения матриц и векторов; а также другие алгоритмы для работы с предложенной структурой данных. Доказывается ряд теорем, связанных с предложенной структурой данных.
Разрабатывается способ выполнения имитации работы квантовых алгоритмов. Разрабатываются алгоритмы для имитации квантовых вычислений с применением алгебраических решающих диаграмм.
В третьей главе диссертации, на основе результатов второй главы, разрабатывается библиотека функций для моделирования квантового компьютера, включающая в себя тип данных для представления квантового регистр, функции для создания квантовых регистров, функции для выполнения квантовых преобразований и функции для выполнения измерений квантовых регистров. В основе этой библиотеки лежит библиотека функций для работы с алгебраическими решающими диаграммами, которая также разрабатывается в этой главе. Библиотеки функций разработаны на языке программирования Haskell.
Разработка библиотеки для работы с алгебраическими решающими диаграммами представляет научный интерес в связи с отсутствием подобных библиотек, разработанных для каких-либо языков программирования, а также с отсутствием библиотек для работы с другими видами решающих диаграмм, разработанных на языке Haskell. Такая библиотека является ценной не
только в контексте разработки эффективного программного обеспечения для программной имитации квантового компьютера, но и для большого числа других задач, в частности, задач верификации логических схем, задач исследования булевых функций и функций многозначной логики и т.п. Эта библиотека включает в себя типы данных и функции, предназначенные для работы с алгебраическими решающими диаграммами и работы с векторами и матрицами, представленными с помощью АР Д.
В четвертой главе диссертации, разрабатывается язык представления квантовых алгоритмов и интерпретатор этого языка.
Разрабатываемый язык не берет на себя функции классического языка программирования. Программы на этом языке создаются динамически, и вызываться из программ, написанных на традиционных языках программирования, и работающих на обычных компьютерах. Этот язык позволяет описывать произвольные квантовые преобразования. Он включает в себя операторы для создания квантовых регистров, для задания квантовых преобразований, для применения преобразований к квантовым регистрам, для проведения измерений квантовых регистров и ряд других операторов. Кроме того, он включает операторы для приема исходных данных и вывода результатов.
Интерпретатор разработанного языка реализован на языке Haskell с использованием ряда вспомогательных средств. Основой для интерпретатора служит библиотека функций, реализованная в третьей главе.
Производится тестирование производительности разработанного интерпретатора.
В заключении изложены основные теоретические и практические результаты диссертационной работы.
В приложении приведены наиболее важные исходные коды разработанного программного обеспечения.
Алгоритм разложения числа на простые множители (Алгоритм Шора)
Для современной криптографии важна задача вычисления дискретного логарифма. На том, что вычислительная сложность этой задачи существенно сверхполиномиальна, основана криптосистема Эль-Гамаля [22]. В общем случае, эта задача формулируется следующим образом. Пусть g - образующий элемент конечной группы G., дан элемент aeG . Требуется найти г є G такой, что a = gr. Различные варианты криптосистемы Эль-Гамаля используют разные группы. Наиболее часто эта схема применяется для группы Z , где р - простое, и для группы точек эллиптической кривой [6]. Существует квантовый алгоритм Шора для вычисления дискретного логарифма. Этот алгоритм был впервые предложен в работе [94]. Приведем здесь его оригинальную версию, которая предназначена для группы Zp (где р - простое). Сначала найдем q - степень двойки, чтобы р q 2р. Приведем квантовый регистр в состояние: Применим теперь преобразование Фурье к первой и второй частям регистра, в результате чего, регистр перейдет в состояние:
Измерим теперь состояние квантового регистра. В результате измере 1 ния с вероятностью не менее мы получим с и а такие, что: же время, лучший классический алгоритм для дискретного логарифма имеет сверхполиномиальную сложность. Существуют различные обобщения рассмотренного алгоритма. В частности, в работе [88] приводится вариант алгоритма Шора для группы точек эллиптической кривой над полем GF(p"), обладающий сложностью 0{пъ). Многие задачи, для которых существуют квантовые алгоритмы, являются частным случаем задачи о скрытой подгруппе. Эта задача формулируется следующим образом (приводится по книге [7]): Пусть G - конечная группа. Пусть имеется оракул, вычисляющий некоторую функцию f:G- B", для которой выполняется свойство: где D — ранее неизвестная группа, D с G . Задача состоит в том, чтобы найти группу D. Существует квантовый алгоритм, решающий эту задачу за полиномиальное по logGJ время, в случае, если группа G — абелева. В работе [58] доказано, что решение этой задачи на классическом компьютере требует экспоненциального времени. Как показано в работах [43, 64], задачи факторизации и дискретного логарифмирования, а также ряд других задач, сводятся к задаче о скрытой подгруппе. Пожалуй, самым распространенным на сегодня способом описания квантовых алгоритмов являются квантовые схемы, впервые предложенные еще Р. Фейнманом в работе [67]. Способ использует тот факт, что любые преобразования над квантовой системой являются унитарными, и, следовательно, обратимыми. Заметим, что множество подстановок G :Вк -» Вк инъективно отображается на множество унитарных операторов над Ar-мерным гильбертовым пространством. При этом оператор соответствующий подстановке действует по правилу: G\x) = \Gx). Определение 1.4. Базисом квантовой схемы называется некоторое множество А подстановок вида G : Вк - Вк. Определение 1.5. Квантовой схемой над базисом А называется последовательность подстановок ut,U2,... ,U„ Определение 1.6. Базис называется полным, если для любого булева оператора, найдется вычисляющая его схема над этим базисом. Квантовая схема, таким образом, реализует подстановку W = Т [ U,. С i=i помощью таких квантовых схем, как это показано в монографии [7], при надлежащем выборе базиса, можно вычислить любой булев оператор, в том числе и необратимый.
Квантовые компьютеры и информационная безопасность
В настоящее время большое значение для многих областей экономики и техники имеют вопросы, связанные с информационной безопасностью [9, 14, 15]. Важным вопросом является влияние, которое окажут квантовые компьютеры на информационную безопасность. Этот вопрос исследуется в работах [10, 11].
Отметим, что небольшая модификация алгоритма Гровера, описанная в работе [10], превращает его в алгоритм для восстановления ключа симметричного алгоритма шифрования по тексту сообщения и шифротексту. При использовании классического компьютера, для этого требуется полный перебор, имеющий сложность 0(2т), где т - длина ключа. Использование алгоритма Гровера позволяет достичь сложности о(2п12\. Таким образом, появление квантовых компьютеров приведет к снижению эффективной длины ключа в два раза. Это говорит о том, что уже сейчас в ряде задач следует использовать симметричные шифры с длиной ключа не менее 256 бит.
Кроме того, аналогичный алгоритм может быть использован для взлома хэш-функций, в связи с чем, следует использовать хэш-функции с длиной блока не менее 256 бит.
Стойкость системы асимметричного шифрования RSA основывается на сверхполиномиальной вычислительной сложности факторизации натуральных чисел. Однако алгоритм Шора имеет сложность, которая оценивается в 0(п3). В то же время, лучший классический алгоритм факторизации — алгоритм решета числового поля (см. работу [87]), имеет сложность
Криптосистема Эль-Гамаля основана на вычислительной сложности задачи дискретного логарифмирования. Наиболее часто эта система основывается на группе Zp и на группе точек эллиптической кривой. Существует квантовый алгоритм Шора для вычисления дискретного логарифма в группе Z В работе [94] сложность этого алгоритма оценивается как 0{пъ). В то же время, лучший классический алгоритм для дискретного логарифма имеет сверхполиномиальную сложность. В работе [88] приводится вариант алгоритма Шора для группы точек эллиптической кривой над полем Галуа GF(p), обладающий сложностью 0(п3).
Несмотря на большие успехи, которых достигла криптология, необходимо отметить, что появление действующих образцов квантовых компьютеров приведет к тому, что многие криптосистемы, прежде всего асимметричные, перестанут быть стойкими, что приведет к невозможности безопасного предоставления многих услуг, в том числе интернет-банкинга и электронной торговли. Перестанут быть безопасными электронные подписи и схемы распределения ключей. Из этого следует, что необходимы новые криптоалгоритмы и, прежде всего, асимметричные.
Кроме негативных последствий для компьютерной безопасности, развитие квантовых вычислений имеет и свои позитивные последствия. Один из позитивных моментов — так называемая квантовая криптография.
Обычные протоколы открытого распространения ключей, например, протокол Диффи-Хеллмана [63], основаны на предположении о том, что используемая в них функция (например, возведение в степень по простому модулю) является однонаправленной. Однако на настоящий момент не существует удовлетворительной теории однонаправленных функций. Более того, многие из функций, считающихся однонаправленным и применяющихся в протоколах открытого распространения ключей, не являются однонаправленными для квантового компьютера. Кроме того, протокол Диффи-Хеллмана уязвим перед атакой «человек посередине» (man-inhe-middle attack) [22].
С помощью квантово-механических методов можно реализовать такое устройство для распределения ключей, что злоумышленник физически не сможет перехватить информацию. В литературе методы передачи ключей по квантовому каналу, называют квантово-криптографическими.
Квантовой криптографии посвящен ряд работ, в частности, [35, 45, 51, 65, 93] и др. В настоящее время существует сеть квантовой передачи ключей, соединяющая не менее 10 точек на территории США и действующая в интересах американских вооруженных сил [65, 66]. Кроме того, ряд компаний уже продает коммерческие образцы оборудования для квантового распространения ключей. В качестве примера можно привести швейыарскую компанию IdQuantique.
Существуют различные протоколы квантового распространения ключей. Подробное их рассмотрение выходит далеко за рамки настоящей диссертации. Для полноты обзора приведем лишь один протокол квантового распространения ключей, рассмотренный в книге [1].
Итак, пусть у нас есть канал связи, по которому можно передавать квантовые биты. Два пользователя, А и В, хотят договориться об общем ключе для шифрования информации, передаваемой по открытому каналу.
Использование структуры данных, основанной на графах для хранения вектора состояния квантового регистра
Во многих случаях вектор состояния квантового регистра имеет большое число повторяющихся компонентов. Определение 2.12. Алгебраической решающей диаграммой (АРД), представляющей функцию f:B" S, где S — некоторое множество, называется направленный ациклический корневой граф D = (V,T,E0,Ex,X,root) , где V— множество нетерминальных вершин, Г- множество терминальных вершин, Т П V = 0; Е0 и Ег - два множества дуг. Х- множество переменных функции/ X = {х1,х2,...,хп). root - корневая вершина. Причем выполняются следующие свойства: Потомка и вершины v будем называть младшим потомком, тогда и только тогда, когда (v,u)e Е0 и называть старшим потомком и обозначать high(v), тогда и только тогда, когда (v,u) є Ех. Младшего потомка вершины и будем обозначать low(v). Старшего потомка вершины и будем обозначать high(v). Переменную, которой помечена вершина v є V будем обозначать var(y). Если v є Т, то элемент множества S, которым эта вершина помечена, будем обозначать val(v). Корневую вершину алгебраической решающей диаграммы D будем обозначать root(D). Рассмотрим функцию if(t,x,y) = , где t є В. Эту функцию можно записать также как if(t,x,y) = xt+ v(l -1). Заметим, что АРД с корневой вершиной v реализует функцию, рекур-рентно определяемую как: Определение 2.13. Алгебраическая решающая диаграмма называ ется упорядоченной, если на любом пути через граф, соблюдается порядок переменных х1,х2,...,хп, которыми помечены вершины. Определение 2.14. Алгебраическая решающая диаграмма называ ется сокращенной (САРД), если выполняются два условия: Уникальность.
Не существует двух различных вершин с одинаковыми характеристиками. Другими словами $u,v є V : var(w) = var(v), low(u) = low(v),high(u) - high(v) и Несокращаемость. He существует вершины и, для который бы выполнялось: low(n) = high(u). Как доказано в статье [31], упорядоченная САРД является канонической для данного порядка переменных, т.е. при выбранном порядке переменных каждой функции соответствует ровно одна САРД. W - таблица, реализующая функцию, отображающую вершины и в тройки (i,l,h), для нетерминальной вершины, и в значения х, для терминальной вершины. Здесь / = var(w), / = low (и), h = high(u), x=vctl(u). H - таблица, реализующая функцию, отображающую тройки (/,/,/ ), для нетерминальных вершин и д; - для терминальных вершин, в и. и = add{W,i,l,h) — создать в таблице Wновый элемент: вершину и с атрибутами (/,/,/ ) и = add{W,х) — создать в таблице W новый элемент: вершину и с атрибутом X. var(w), low(u), high(u) — номер переменной, младшего и старшего потомков нетерминальной вершины и (в таблице W). val(u) — найти в таблице W значение, ассоциированное с терминальной вершиной и. term(u) - если вершина и является терминальной, то возвращает 1 иначе - 0. Ъ = member(H,i,l,h) - проверить, имеется ли нетерминальная вершина с атрибутами (i,l,h) в таблице Н.
Возвращает 1, если имеется, иначе 0. Ъ = member(H,x) — проверить, имеется ли терминальная вершина с параметром атрибутом х в таблице Н. Возвращает 1, если имеется, иначе 0. u = lookup{H,i,l,h) — найти нетерминальную вершину, с атрибутами (/,/,/г) в таблице Н. и = 1оокир{Н,х) - найти терминальную вершину, с атрибутом д: в таблице Н. insert(H,i,l,h,u) - добавить в таблицу Нвершину и с атрибутами (i,l,h) insert(H,x,u) — добавить в таблицу Нтерминальную вершину и с атрибутом х. Для того чтобы эти функции эффективно работали, таблицы Т и Н должны хранится с помощью структуры данных, в которой поиск имеет логарифмическую относительно количества элементов сложность. Сначала опишем функцию Mk(z,/,/z), которая возвращает вершину и, соответствующую тройке (/, /, h), если эта вершина есть в таблице Н. В случае, если такой вершины в таблице нет, она создает такую вершину и возвращает ее идентификатор. Блок-схема функции Мк показана на рис. 2.1.
Примеры эффективного применения алгебраических решающих диаграмм
В этом разделе приведем некоторые примеры, показывающие эффективность применения алгебраических решающих диаграмм.
Как уже упоминалось, применение решающих диаграмм дает большой выигрыш в расходе памяти при кодировании повторяющихся данных. На Вышеприведенные примеры демонстрируют эффективность применения алгебраических решающих диаграмм для кодирования данных с повторениями. При этом имеется возможность эффективно выполнять преобразования над АРД без дополнительных операций декодирования, в отличие от классических методов сжатия информации (таких алгоритмах, как например, Лемпеля-Зива или Хаффмана).
Для решения задачи моделирования квантового компьютера, достаточно важным является выбор способа представления амплитуды вероятности квантового состояния. Амплитуда является комплексным числом, а в стандартной библиотеке языка Haskell имеется тип данных для представления комплексных чисел Complex. Этот тип представляет собой пару чисел: действительную и мнимую часть числа. В то же время, учитывая тот факт, что в данном случае важными являются выполнение таких операций, как нахождение вероятности, соответствующей амплитуде и равной квадрату модуля амплитуды, а также операций умножения комплексных чисел и фазового сдвига, оптимальным является хранение комплексных чисел в виде пары амплитуда и фаза. Таким образом, для представления амплитуд вероятности, был введен следующий тип: data Qubit = Float :@ Float
Этот тип реализует класс Eq (т.е. величины этого типа можно сравнивать). Также он реализует класс Num, т.е. операции сложения, вычитания, умножения, функции вычисления абсолютной величины и знака.
Для него естественным образом вводятся функции усиления и фазового Кроме того, тип Qubit реализует класс NormSpace. Для того, чтобы иметь возможность хранить данные типа Qubit, этот тип должен реализовывать класс Ord, т.е. множество значений этого типа должно быть линейно упорядоченным. Это можно сделать путем сравнения сначала амплитуды, а в случае равенства - фазы. Другими словами
