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

1 Описание свойств и структуры алгоритма

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

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

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

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

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

-Комплексная матрица $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}$ двухкубитного преобразования размера $4 \times 4.$ Верхние и нижние двойные индексы обозначают бинарную запись индексов $i$ и $j$ (такие обозначения сильно упрощают дальнейшее описание).

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

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

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

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

$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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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