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

Размещено на http://www.allbest.ru/

1

Научный журнал КубГАУ, №134(10), 2017 года

http://ej.kubagro.ru/2017/10/pdf/78.pdf

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

Потапов Виктор Сергеевич

аспирант 3 года обучения

Гушанский Сергей Михайлович

к.т.н., доцент

Южный федеральный университет, Таганрог, Россия

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

Ключевые слова: квантовый регистр, симулятор квантового вычислителя, комплексная плоскость, кубит

Development of computational structure of the simulator of a quantum calculator and determining its performance. Potapov Viktor Sergeevich, Gushanskiy Sergei Mikhailovich

This article describes the basics of performance, as well as the structural and functional component of the development and implementation of SQC. In accordance with this, a computational structure of the simulator of a quantum calculator has been derived, taking into account all the available features of constructing a simulator of a quantum computing device. Also, a software implementation of the derived universal computational structure of SQC that satisfies and operates according to the principles of this scheme is implemented

Keywords: quantum register, simulator of quantum calculator, complex plane, qubit

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

На данный момент существует большое количество различных сред моделирования (как консольных, так и графических), библиотек API, а также моделей отдельных алгоритмов. Некоторые модели строятся на базе существующих математических сред моделирования, например модель алгоритма Гровера, разработанная в Санкт-Петербургском Государственном Университете. Различаются модели и по подходам к моделированию: QuIDDPro [1] имеет математическое ядро построено на графовом подходе, который в отличии от обычного матричного подхода позволяет значительно экономить память при моделировании. Отдельного упоминания стоят библиотеки APIlibquantum [2], Cove [3] для построения программ моделирования квантовых вычислений, которые предоставляют готовый функционал для построения собственной модели.

Вычислительная структура симулятора квантового вычислителя

Вычислительная структура симулятора квантового вычислительного устройства [4], показанная на рис. 1, позволяется разработать симулятор квантового вычислителя, соблюдая требования, отображенные в схеме. Данная структурная и функциональная иллюстрация вычислительной модели симулятора квантового вычислителя является универсальной для его построения. обозначает первый кубит регистра (КР) QR1; - второй КР QR1; - текущий кубит КР QR1; - последний кубит.

Вычислительная структура СКВ условно содержит два КР QR1 и QR2. Единственный реальный регистр можно условно разделить и на большее число вспомогательных частей. Такое разделение может быть сделано в целях, например, удаления квантового мусора при подготовке к процессу измерения. Каждый квантовый разряд регистра QR1 и каждый квантовый разряд регистра QR2 является кубитом. Размерность каждого кубита одинакова: .

Рисунок 1. Схема вычислительной структуры СКВ

вычислительный симулятор квантовый вычислитель

Это означает, что в одном кубите может быть записано и хранится различных чисел. Число кубитов в регистре QR1 и QR2 одинаково и равно . Таким образом, регистры QR1 и QR2 могут быть частями одного реально существующего КР QR. Например, все нечетные квантовые разряды относятся к регистру QR1, а все четные кубиты - к КР QR2. Каждый кубит регистра QR1 соединен с квантовым блоком пересечений - блоком (т.е. является входом блока ). То же относится и кубитам регистра QR2. Выход каждого блока передается на схемы фильтрации и измерения. Сам блок реализует интегральную операцию пересечения в форме блочно-диагональной матрицы Рота [5].

Программная симуляция квантовых алгоритмов и процессов. В соответствии с вышеописанной и разработанной схемой вычислительной модели СКВ, была построена программная симуляция. Данная модель может принимать унитарную функцию f и эффективно определять ее след (вектор направления) в соответствии с использованием векторной, матричной алгебры. Этот след функции f на n кубитов можно найти вдоль одной из осей X или Y.

Рисунок 2. Главная форма/форма вывода результата работы модели

Результат работы модели представляется в виде раскрашенного набора пикселей. На рисунке 3 разобрана карта цветов в комплексной плоскости. Оттенок однозначно зависит от фазы ?. Например, положительное число отображается красным пикселем, отрицательное - светло-голубым. Регистр кубит размера n определяется как 2 в степени n базисных состояний. Каждое базисное состояние представлено как единый квадрат (пиксель) амплитуда Ж которого определяется его цвет в соответствии с цветовой картой. Если кубит |j> имеет реальную амплитуду a ? (0, 1], то j-ый квадрат в регистре красного цвета. Все кубиты, которые имеют амплитуды Z = 0 окрашены в чёрный цвет.

Рисунок 3. Карта цветов квантового регистра в комплексной плоскости

Данная модель может принимать унитарную функцию f и эффективно определять ее след (вектор направления) в соответствии с использованием векторной, матричной алгебры. Этот след функции f на n кубитов можно найти вдоль одной из осей X или Y.

Определение производительности СКВ

Что влияет на производительность симуляторов квантовых вычислительных устройств?

Квантовая схема, ее размер и глубина. Рассуждая о данном важнейшем компоненте симулятора, возможно выделить: число элементов (квантовый логические гейты) и ветвей квантовой схемы, число взаимосвязанных между собой ветвей (глубина; некоторые гейты функционируют с привязкой нескольких ветвей, например CCNOT). Квантовой схемой над базисом B называется последовательность унитарных операторов , где , , n - число кубитов. Более формально, матричные элементы оператора U[S] имеют следующий вид. Пусть

(1)

Обозначим x[S] как под-последовательность битов, стоящих на местах из множества S. Тогда оператор U[S] записывается как

, (2)

. (3)

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

Начальное базисное состояние СКВ (НБС СКВ). Квантовое состояние - это любое возможное состояние, в котором может находиться квантовая система. Пусть состояние квантовой системы задано вектором . При разложении в соответствии с полными наборами векторов системы и ее окружения : , где - амплитуда вероятности нахождения системы в j-м состоянии. Очевидно, что производительность СКВ с точки зрения НБС зависит от числа ветвей квантовой схемы и вида базисного состояния (БС). Стоит отметить, что само по себе НБС СКВ не влияет на его производительность. Однако при рассмотрении НБС в рамках жизненного цикла квантовой схемы нельзя не учесть величину манипуляций пользователя при работе с СКВ в рамках ее начального приготовления и настройки (СКВ относится к типу автоматизированных систем).

Получаем уравнение, отражающее величину производительности в рамках начального базисного состояния СКВ:

, (4)

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

Запуск различных алгоритмов в рамках разработанного СКВ

Разработанный СКВ также предполагает реализацию набора квантовых алгоритмов, что в свою очередь влияет на производительность всего СКВ. Затраты на производительность в данном случае прямопропорциональны классу сложности конкретного квантового алгоритма, что подробно реализовано в работе [6]:

, (5)

где - временная сложность квантового алгоритма, или, если проще, время работы конкретного алгоритма, - количество выполняемых в алгоритме операций, - количество запросов к квантовому оракулу в процессе работы квантового алгоритма, - классы сложности квантовых алгоритмов ( | - операция логическое ИЛИ).

В системе ниже представлены математические формализации некоторых классов сложности.

Алгоритм при полиномиальном времени (Р) эквивалентен детерминированной машиной Тьюринга (МТ), вычисляющей ответ по данному на входную ленту слову из входного алфавита. Сложностью функции f называется функция C, зависящая от длины входного слова и равная максимуму времени работы машины по всем входным словам фиксированной длины (1). Если для функции f существует МТ M такая, что (6) для некоторого числа C, то говорят, что она принадлежит классу P.

NP - класс задач, ответ на которые можно получить за время P, а классом NTIME(f) называется класс задач, для которых существует недетерминированная МТ, работа которой останавливается при превышении длины входа (8). Формальное определение класса NP через класс NTIME выглядит так (7). Суммируя все вышеизложенное, получим:

(9)

Построенный на основе предложенной вычислительной структуры СКВ позволяет:

1) оптимизировать вычислительный процесс симулятора в соответствии с набором компонентов: сдвоенный квантовый регистр (QR1 и QR2), схема фильтрации и измерения, квантовые блоки пересечений и число кубитов .

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

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

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

Работа выполнена в рамках проектной части госзадания Минобрнауки России № 2.3928.2017/4.6 в Южном федеральном университете.

Литература

1. QuIDDPro: High-Performance Quantum Circuit Simulation // URL: http://vlsicad.eecs.umich.edu/Quantum/qp/ (Дата обращения: 11.06.2017);

2. libquantum 1.1.1 // URL: http://www.libquantum.de/api/1.1/index.html (Дата обращения: 11.06.2017);

3. Cove: A Practical Quantum Computer Programming Framework // URL: http://cove.purkeypile.com/ (Дата обращения: 11.06.2017);

4. Guzik V., Gushanskiy S., Polenov M., Potapov V. Models of a quantum computer, their characteristics and analysis // 9th International Conference on Application of Information and Communication Technologies (AICT). - Institute of Electrical and Electronics Engineers, 2015. - P. 583-587;

5. Правильщиков П.А. Квантовый параллелизм и новая модель вычислений // Труды XII Всероссийского совещания по проблемам управления ВСПУ-2014.

6. Потапов В.С., Гузик В.Ф., Гушанский С.М. О производительности и вычислительной сложности квантовых алгоритмов // Информатизация и связь. - 2017, № 3. - С.24-29.

References

1. QuIDDPro: High-Performance Quantum Circuit Simulation // URL: http://vlsicad.eecs.umich.edu/Quantum/qp/ (Data obrashcheniya: 11.06.2017);

2. libquantum 1.1.1 // URL: http://www.libquantum.de/api/1.1/index.html (Data obrashcheniya: 11.06.2017);

3. Cove: A Practical Quantum Computer Programming Framework // URL: http://cove.purkeypile.com/ (Data obrashcheniya: 11.06.2017);

4. Guzik V., Gushanskiy S., Polenov M., Potapov V. Models of a quantum computer, their characteristics and analysis // 9th International Conference on Application of Information and Communication Technologies (AICT). - Institute of Electrical and Electronics Engineers, 2015. - P. 583-587;

5. Pravil'shchikov P.A. Kvantovyj parallelizm i novaya model' vychislenij // Trudy XII Vserossijskogo soveshchaniya po problemam upravleniya VSPU-2014.

6. Potapov V.S., Guzik V.F., Gushanskij S.M. O proizvoditel'nosti i vychislitel'noj slozhnosti kvantovyh algoritmov // Informatizaciya i svyaz'. - 2017, № 3

Размещено на Allbest.ru