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

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

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

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

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

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

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

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

Целочисленные параметры [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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Объем входных данных: [math]\displaystyle{ 2^n+4 }[/math] комплексных чисел и [math]\displaystyle{ 1 }[/math] одно целое.

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

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

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

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

Программная реализация алгоритма

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

На языке C функцию однокубитного преобразования можно записать следующим образом:

void OneQubitEvolution(complexd *in, complexd *out, complexd U[2][2], int nqubits, int q)
{
	//n - число кубитов
        //q - номер кубита для преобразования

	int shift = nqubits-q;
	//Все биты нулевые, кроме соответствующего позиции преобразуемого кубита  
	int pow2q=1<<(shift);

	int N=1<<nqubits;
	for	(int i=0; i<N; i++)
	{
		//Обнуления меняющегося бита
		int i0 = i & ~pow2q;
		
		//Установка меняющегося бита
		int i1 = i | pow2q;
		
		//Получение значения меняющегося бита
		int iq = (i & pow2q) >> shift;

		out[i] = U[iq][0] * in[i0] + U[iq][1] *in[i1];
	}
}

Отметим, что существенная часть вычислений и логики кода приходится на битовые операции, однако, этого можно избежать: однокубитное преобразование в большинстве случаев является лишь подпрограммой и применяется к разным кубитам большое число раз. В свою очередь, вычисляемые при помощи битовых операций индексы i0, i1 и iq зависят лишь от параметров количества кубитов n и номера кубита q. Число кубитов обычно фиксировано, соответственно, можно вычислить эти индексы заранее для всех q от 1 до n. Для хранения потребуется лишь массив целочисленных переменных линейного размера 3n в то время, как обрабатываемые данные имеют экспоненциальный размер. Очевидно, что такая оптимизация критически необходима при реализации алгоритма на вычислительных устройствах или языках программирования с отсутствием быстрых битовых операций (примером может служить среда Matlab).

Локальность данных и вычислений

К сожалению, в потивовес идельной возможности параллелизации алгоритма, он обладает очень плохой локальностью.

Из математического описания и информационных графов для разных параметров q можно заметить, что при однократном применении однокубитного преобразования легко получить идеальную локальность обращения к данным простой перестановкой кубитов. Так, переместив кубит q на последнее место, мы получим взаимодействие лишь соседних по памяти элемнтов, причем в идеальном последовательном доступе.

Однако, преобразование одного кубита в прикладных задачах является лишь подпрограммой и применяется многократно с различными параметрами q. Как видно из математического описания и Рис. 1-2, это полностью исключает возможность добиться локальности обращений к данным.