Двухкубитное преобразование вектора-состояния

Двухкубитное преобразование вектора-состояния
Последовательный алгоритм
Последовательная сложность	[math]5 \cdot 2^n[/math]
Объём входных данных	[math]2^n+16[/math]
Объём выходных данных	[math]2^n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]2[/math]
Ширина ярусно-параллельной формы	[math]2^{n+2}[/math]

Основные авторы описания: А.Ю.Чернявский

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм производит моделирование действия двухкубитного квантового вентиля на вектор-состояние.

1.2 Математическое описание алгоритма

Исходные данные:

-Целочисленные параметры [math]n - [/math] число кубитов (необязательно) и [math]k,l -[/math] номера кубитов, над которым производится преобразование.

-Комплексная матрица [math]U = {u_{ij}}= \begin{pmatrix} u_{00}^{00} & u_{01}^{00} & u_{10}^{00} & u_{11}^{00}\\ u_{00}^{01} & u_{01}^{01} & u_{10}^{01} & u_{11}^{01}\\ u_{00}^{10} & u_{01}^{10} & u_{10}^{10} & u_{11}^{10}\\ u_{00}^{11} & u_{01}^{11} & u_{10}^{11} & u_{11}^{11} \end{pmatrix}[/math] двухкубитного преобразования размера [math]4 \times 4.[/math] Верхние и нижние двойные индексы обозначают бинарную запись индексов [math]i[/math] и [math]j[/math] (такие обозначения сильно упрощают дальнейшее описание).

-Комплексный вектор [math]v[/math] размерности [math]2^n,[/math] задающей начальное состояние многокубитной системы.

Вычисляемые данные: комплексный вектор [math]w[/math] размерности [math]2^n,[/math] соответствующий состоянию после преобразования.

Формулы метода:

Элементы итогового вектора записываются в следующем виде:

[math] w_{i_1i_2\ldots i_k \ldots i_l \ldots i_n} = \sum\limits_{j_k=0, j_l=0}^1 u^{j_k j_l}_{i_k i_l} v_{i_1i_2\ldots j_k \ldots j_l \ldots i_n} [/math]

Индекс-кортеж [math]i_1i_2\ldots i_n[/math] представляет собой двоичную запись индекса элемента в массиве.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма представляет собой независимое вычисление всех [math]2^n[/math] элементов вектора [math]w.[/math] Вычисление каждого элемента требует четыре операции умножения и три операцию сложения. Кроме того необходимо вычислять индексы типа [math]i_1i_2\ldots j_k \ldots j_l \ldots i_n,[/math] а также значение битов [math]j_k,j_l[/math] что требует побитовых операций.

1.4 Макроструктура алгоритма

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

1.5 Схема реализации последовательного алгоритма

Для каждого индекса [math]i[/math] от [math]0[/math] до [math]2^n-1[/math]

1. Вычислить элементы [math]i_k, i_l[/math] двоичного представления индекса [math]i.[/math]
2. Для всех четырех бинарных значений [math]j_k, j_l[/math] вычислить индексы [math]i_1i_2\ldots j_k \ldots j_l \ldots i_n[/math]
3. Просуммировать [math]u^{j_k j_l}_{i_k i_l} v_{i_1i_2\ldots j_k \ldots j_l \ldots i_n}.[/math]

1.6 Последовательная сложность алгоритма

Алгоритм требует:

1. [math]2^{n+2}[/math] операций умножения комплексных чисел;
2. [math]3\cdot 2^n[/math] операций сложения комплексных чисел;
3. [math]2^{n+1}[/math] операций получения значения [math]k[/math]-го бита числа;
4. [math]2^{n+3}[/math] операций изменения значения [math]k[/math]-го бита числа.

Отметим, что данный алгоритм обычно применяется много раз подряд, в связи с чем вычисления, связанные с побитовыми операциями (3-4), могут единожды проводиться в начале алгоритма. Кроме того, от них можно избавиться, пользуясь сложением и логическим умножением с числами [math]2^l,[/math] и [math]2^k,[/math] которые сохраняется для всего алгоритма.

1.7 Информационный граф

Представим граф алгоритма для случаев [math]n=3, k=1, l=2[/math] (рис.1) и [math]n=3, k=1, l=3[/math] (рис.2). На графах не представлены матрицы преобразования [math]U,[/math] в связи с тем, что их размер при больших [math]n[/math] много меньше, нежели размеры входного и выходного векторов.

Отображение графа со входными и выходными данных, а также "свёрнутой" основной операцией удобно для понимания локальности обращений к памяти. Отметим, что структура графа (а именно обращение к входным данным) сильно зависит от параметров [math]k,l.[/math]

Рисунок 1. Граф алгоритма для [math]n=3, k=2, l=3[/math] без отображения матрицы преобразования [math]U.[/math]

Рисунок 2. Граф алгоритма для [math]n=3, k=1, l=3[/math] без отображения матрицы преобразования [math]U.[/math]

Рисунок 3. Граф основной операции.

1.8 Ресурс параллелизма алгоритма

Как видно из информационного графа, прямой алгоритм моделирования однокубитного преобразования обладает высочайшей степенью параллелизма. Все операции вычисления элементов нового вектора-состояния могут быть произведены параллельно. Для вычисления одного элемента необходимо выполнить две операции умножения и одну операцию сложения, операции умножения, в свою очередь, также могут быть выполнены параллельно. Таким образом, необходимо выполнение двух ярусов: одного, состоящего из [math]2^{n+2}[/math] умножений и другого, состоящего из [math]3 \cdot 2^n[/math] сложений.

1.9 Входные и выходные данные алгоритма

Входные данные:

• Комплексный вектор состояния [math]u[/math] длины [math]2^n.[/math] Обычно нормирован на единицу.
• Унитарная матрица [math]U[/math] порядка [math]4[/math].
• Номера кубитов [math]k,l[/math].

Выходные данные:

• Комплексный вектор состояния [math]w[/math] длины [math]2^n[/math].

Объем входных данных: [math]2^n+16[/math] комплексных чисел и [math]2[/math] целочисленых параметра.

Объем выходных данных: [math]2^n[/math] комплексных чисел.

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности является экспоненциальным (эксмпонента переходит в константу).

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