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

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

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

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

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ 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} }[/math]

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

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

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

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

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

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

Для индекса [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ 2^n-1 }[/math]

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