Разработка программной модели квантовых вычислений и моделирование работы квантовых алгоритмов на платформе «Эльбрус»

ВВЕДЕНИЕ

Квантовые вычисления начали развиваться более 40 лет назад [1][2] и до сегодняшнего дня остаются областью информационных технологий, привлекающей внимание ученых из разных стран [3][4]. Благодаря способности квантовых компьютеров решать определенные вычислительные задачи экспоненциально быстрее классических, они могут найти применение в самых различных областях, таких как криптография, машинное обучение, искусственный интеллект, биология и т.д. Квантовые вычисления также могут быть использованы для решения вычислительных задач ВКО, таких как нечеткий поиск, оптимальное распределение информационных ресурсов, распознавание целей. Несмотря на то что создание полноценного квантового компьютера является на данный момент нерешенной задачей, разработка программных моделей квантовых вычислений остается актуальным направлением развития области. Такие программы используются для моделирования работы квантовых схем, а также изучения и поиска путей решения проблем, возникающих при реализации квантовых вычислений [5].

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

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

Все разработанные и разрабатываемые программные модели квантовых вычислений оперируют такими базовыми понятиями, как кубит, квантовый регистр, гейт, квантовая схема. Одиночный кубит является суперпозицией двух квантовых состояний |0› и |1›, каждое из которых может рассматриваться как носитель одного бита классической информации. Кубит представляется вектором единичной длины в трехмерном пространстве. Такое геометрическое изображение кубита называется его представлением на сфере Блоха (рис. 1).

Квантовый регистр шириной N состоит из N упорядоченных кубитов. Он может находиться в одном из двух состояний: измеренном или неизмеренном. Если квантовый регистр измерен, каждый кубит становится обычным битом, а квантовый регистр, соответственно, обычным регистром из N битов. Если квантовый регистр не измерен, то имеет место квантовая суперпозиция и значением квантового регистра является информация о вероятностях «выпадения» при измерении каждого из 2^N возможных N-разрядных двоичных чисел, то есть квантовый регистр из N кубитов – это вектор длиной 2^N. Состояние квантового регистра из N кубитов представляет собой тензорное произведение вектор-столбцов состояний соответствующих кубитов.

Квантовый гейт – это матрица размером 2^m × 2^m, где m – количество кубитов, на которые воздействует гейт. Воздействие гейта на кубит выражается скалярным произведением. В теории квантовых вычислений доказывается утверждение о том, что однокубитные гейты и гейт CNOT являются универсальными.

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

ПРОГРАММНАЯ МОДЕЛЬ КВАНТОВЫХ ВЫЧИСЛЕНИЙ

В качестве платформы для разработки программной модели была выбрана отечественная аппаратно-программная платформа «Эльбрус». Общее программное обеспечение (ОПО) «Эльбрус» содержит оптимизирующий компилятор lcc, позволяющий распараллеливать вычисления на уровне операций, тем самым повышая производительность программы [6]. ОПО «Эльбрус» также содержит библиотеку Elbrus Media Library – высокопроизводительную математическую и мультимедийную библиотеку, представляющую из себя набор разнообразных функций для обработки сигналов, изображений, видео и математических вычислений [7]. Библиотека EML содержит такие функции, как eml_Vector_Mul_64F и eml_ Algebra_GEMM_64F, которые могут позволить значительно ускорить вычисление некоторых операций, необходимых для моделирования квантовых вычислений, таких как умножение векторов и умножение матриц.

В рамках данной работы была разработана программная модель квантовых вычислений. После изучения различных вариантов реализации вычислительной части программы было принято решение использовать язык программирования Python и библиотеку математических вычислений NumPy для ее разработки. Интерфейс разработанной модели с открытой в нем квантовой схемой алгоритма квантового преобразования Фурье для 4 кубитов представлен на рисунке 2.

Программная модель состоит из двух частей: вычислительной части, написанной на языке программирования Python, и интерфейсной части, для разработки которой были использованы языки HTML и JavaScript. Пользовательский интерфейс позволяет редактировать, сохранять и загружать квантовые схемы, а также выставлять количество запусков квантовых схем. Для моделирования вычислительной части программы была использована библиотека NumPy, опирающаяся на нативную библиотеку Elbrus Media Library и использующая ее функции при работе.

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

Как было сказано выше, значением неизмеренного квантового регистра является информация о вероятностях «выпадения» определенного значения при измерении каждого из 2N возможных чисел, то есть для получения достоверного результата необходимо произвести многократное измерение квантового регистра. Результатом работы разработанной программной модели является диаграмма распределения состояний кубитов после серии измерений (рис. 3).

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

КВАНТОВЫЕ АЛГОРИТМЫ

В квантовых вычислениях квантовый алгоритм – это алгоритм, который работает на реалистичной модели квантовых вычислений. Представляет собой последовательность унитарных операций (гейтов) с указанием, над какими именно кубитами их надо совершать. В рамках данной работы была смоделирована работа набора квантовых алгоритмов, описание некоторых из них приведено ниже.

АЛГОРИТМ ДОЙЧА – ЙОЖИ

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

Алгоритм представляет собой применение к нулевому вектору |0›^⊗n оператора H^⊗nU_f H^⊗n, где H – это гейт Адамара, U_f – квантовый оракул, а ⊗n – возведение в степень n через тензорное произведение. Если после измерения регистра все биты равны 0, значит значение функции f(x) не зависит от x, в противном случае функция является сбалансированной. Для данного алгоритма можно создать квантовый оракул путем применения гейтов CNOT с каждым входным кубитом в качестве элемента управления и выходным битом в качестве цели. Изначальные состояния, которые дают 0 или 1, можно варьировать путем применения гейта X к некоторым элементам управления. Затем необходимо перевести входные кубиты в состояние |+›, а выходной кубит в состояние |−›. В симуляторе это можно сделать при помощи гейтов (гейтов Адамара и гейта NOT), а можно при помощи изменения базисного состояния кубита. После применения оракула необходимо использовать гейты Адамара на входных кубитах, а затем измерить их. Результат работы алгоритма приведен на рисунке 5.

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

АЛГОРИТМ БЕРНШТЕЙНА – ВАЗИРАНИ

Алгоритм Бернштейна – Вазирани является расширенной версией алгоритма Дойча – Йожи. Известно, что существует скрытая булева функция, которая принимает в качестве входных данных строку битов и возвращает либо 0, либо 1, причем f(x) = a • x, где • – скалярное произведение. Требуется найти a. Квантовая схема алгоритма с a = 011 представлена на рисунке 6. Алгоритм Бернштейна – Вазирани демонстрирует преимущество квантовых алгоритмов по наименьшему требуемому количеству запросов к оракулу. Классическое решение задачи в лучшем случае потребует O(n) обращений к оракулу, в то время как квантовый алгоритм решает задачу за O(1) [8].

Основные кубиты инициализируются состоянием |0›^⊗n, а вспомогательный состоянием |1›. Затем ко всем кубитам применяется гейт Адамара. К результатам предыдущего шага применяется оракул U_f, после чего к основным кубитам снова применяется гейт Адамара. В результате измерение входного регистра даст искомый «скрытый» вектор. Результат работы алгоритма приведен на рисунке 7.

Результатом измерения является искомый «скрытый» вектор – 011.

КВАНТОВОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ

В классических вычислениях преобразование Фурье – это математическая операция, которая является фундаментальной для таких областей, как обработка сигналов. Квантовое преобразование Фурье (QFT) выполняет преобразование между двумя базисами, вычислительным (Z) базисом и базисом Фурье, и является частью некоторых важных алгоритмов, таких как алгоритм Шора [9]. Гейт Адамара – это однокубитное QFT, так как он выполняет преобразование из базиса Z |0› и |1› в базис X |+› и |−›. Точно так же все многокубитные состояния в вычислительном базисе имеют соответствующие состояния в базисе Фурье, то есть QFT – это просто функция, которая переводит состояние из одного базиса в другой.

Схема квантового преобразования Фурье для двух кубитов приведена на рисунке 8.

В многокубитных (2 и больше) квантовых схемах, реализующих QFT, используются два гейта: гейт Адамара и контролируемый фазовый поворот. Для 2-кубитного QFT к первому кубиту сначала применяется гейт Адамара, который переводит кубит в суперпозицию. Затем к кубиту применяется контролируемый гейт S (являющийся частным случаем гейта U1 с λ = π/2). После этого ко второму кубиту применяется гейт Адамара. Результат работы квантовой схемы приведен на рисунке 9.

Схема квантового преобразования Фурье для трех кубитов приведена на рисунке 10.

С увеличением количества кубитов алгоритм усложняется. QFT для 3 кубитов требует выполнения следующих шагов:

1) Применить гейт Адамара к первому кубиту |x₁›;

2) К первому кубиту применить гейт S, контролируемый вторым кубитом;

3) Применить к первому кубиту гейт T (являющийся частным случаем гейта U1 с λ = π/4), контролируемый вторым кубитом;

4) Применить гейт Адамара ко второму кубиту;

5) Применить гейт S, контролируемый третьим кубитом, ко второму кубиту;

6) Применить гейт Адамара к третьему кубиту.

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

Схема квантового преобразования Фурье для четырех кубитов приведена на рисунке 2.

4-кубитная схема, реализующая QFT, построена по тому же принципу, что и схема для 3 кубитов, но в ней используется гейт поворота U1 с λ = π/8. Соответственно в 5-кубитной схеме используется U1 с λ = π/16, в 6-кубитной U1 с λ = π/32 и т.д. Результат работы квантовой схемы приведен на рисунке 3.

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

С использованием разработанной модели был проведен эксперимент на вычислительном комплексе «Эльбрус-801», в ходе которого была смоделирована работа ряда различных квантовых схем, содержащих от 1 до 15 кубитов. В процессе эксперимента использовались следующие программные пакеты:

• Эльбрус ОС с ядром версии 5.4.0, дистрибутив версии 6.0;
• Python версии 3.7.4;
• NumPy версии 1.17.2.

Как и ожидалось, с увеличением количества кубитов наблюдалось значительное увеличение в затраченной памяти и времени выполнения (рис. 12). При попытке смоделировать вычислительную схему, содержащую 16 кубитов, возникла ошибка из-за превышения максимально возможного количества памяти, выделяемого для работы виртуальной машины Python. Также в ходе исследования была смоделирована работа ряда квантовых алгоритмов, в том числе алгоритма Дойча – Йожи, алгоритма Бернштейна – Вазирани, алгоритма Гровера.

Возможности аппаратно-программной платформы «Эльбрус» позволяют оптимизировать процесс моделирования квантовых вычислений. В дальнейшем планируется перенос вычислительной части модели с интерпретируемого языка Python на компилируемый язык C++, что позволит в полной мере воспользоваться всеми возможностями оптимизации, предоставляемыми программным обеспечением и архитектурой «Эльбрус». Также планируется использование специальных методов хранения разреженных матриц, что может позволить значительно снизить объем памяти, используемый при моделировании.

ЗАКЛЮЧЕНИЕ

В рамках данной работы была разработана программная модель квантовых вычислений и проведен вычислительный эксперимент, в ходе которого была смоделирована работа квантовых схем и алгоритмов. В ходе эксперимента с увеличением количества кубитов наблюдалось значительное увеличение в затраченной памяти и времени выполнения. Использование возможностей оптимизации, предоставляемых ОПО и архитектурой «Эльбрус», а также эффективное использование структур данных позволит не только увеличить количество моделируемых кубитов, но и повысить скорость получения результата при моделировании. Усовершенствование разработанной модели может позволить расширить спектр квантовых алгоритмов, доступных для моделирования. Разработанная модель может быть использована для разработки и отладки вычислительно сложных алгоритмов, которые могут быть применены в том числе для решения вычислительных задач ВКО, таких как нечеткий поиск, оптимальное распределение информационных ресурсов, распознавание целей.