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

Однокубитное преобразование вектора-состояния
Последовательный алгоритм
Последовательная сложность	$3 \cdot 2^n$
Объём входных данных	$2^n$
Объём выходных данных	$2^n$
Параллельный алгоритм
Высота ярусно-параллельной формы	$2$
Ширина ярусно-параллельной формы	$2^n$

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

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

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

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

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

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

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

Комплексная матрица $U = \begin{pmatrix} u_{00} & u_{01}\\ u_{10} & u_{11} \end{pmatrix}$ однокубитного преобразования размера $2 \times 2.$

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

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

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

Состояние после действия преобразования $U$ на $k-$й кубит имеет вид $v_{out} = I_{2^{k-1}}\otimes U \otimes I_{2^{n-k}},$ где $I_{j} -$ единичная матрица размерности $j,$ а $\otimes -$ тензорное произведение (произведение Кронекера).

Однако, элементы итогового вектора можно записать и в прямом виде, что более удобно для вычислений:

$w_{i_1i_2\ldots i_k \ldots i_n} = \sum\limits_{j_k=0}^1 u_{i_k j} v_{i_1i_2\ldots j_k \ldots i_n} = u_{i_k 0} v_{i_1i_2\ldots 0_k \ldots i_n} + u_{i_k 1} v_{i_1i_2\ldots 1_k \ldots i_n}$

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

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

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

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

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

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

Для индекса $i$ от $0$ до $2^n-1$

1. Вычислить элемент $i_k$ двоичного представления индекса $i.$
2. Вычислить индексы $j$ имеющие двоичные представления $i_1i_2\ldots \overline{i_k} \ldots i_n,$ где крышка означает обращение бита.
3. Вычислить $w_i = u_{i_k i_k}\cdot v_{i} + u_{i_k \overline{i_k}}\cdot v_j.$

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

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

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

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

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

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

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

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