Двухкубитное преобразование вектора-состояния
| Двухкубитное преобразование вектора-состояния | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ 5 \cdot 2^n }[/math] |
| Объём входных данных | [math]\displaystyle{ 2^n+16 }[/math] |
| Объём выходных данных | [math]\displaystyle{ 2^n }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ 2 }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ 2^{n+2} }[/math] |
Основные авторы описания: А.Ю.Чернявский.
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм производит моделирования действия двухкубитного квантового вентиля на вектор-состояние. [1] [2] [3] [4] Данный алгоритм обычно является подпрограммой и многократно применяется к различным кубитам одного состояния (например при моделировании квантовых алгоритмов или анализе квантовой запутанности). Особенностью алгоритма, как и большинства алгоритмов квантовой инфоорматики, является экспоненциальный рост объема данных в зависимости от основного параметра - числа кубитов, что приводит к необходимости суперкомпьютерной реализации для решения важных практических задач.
Математическое описание алгоритма
Исходные данные:
-Целочисленные параметры [math]\displaystyle{ n - }[/math] число кубитов (необязательно) и [math]\displaystyle{ k,l - }[/math] номера кубитов, над которым производится преобразование.
-Комплексная матрица [math]\displaystyle{ 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]\displaystyle{ 4 \times 4. }[/math] Верхние и нижние двойные индексы обозначают бинарную запись индексов [math]\displaystyle{ i }[/math] и [math]\displaystyle{ j }[/math] (такие обозначения сильно упрощают дальнейшее описание).
-Комплексный вектор [math]\displaystyle{ v }[/math] размерности [math]\displaystyle{ 2^n, }[/math] задающей начальное состояние многокубитной системы.
Вычисляемые данные: комплексный вектор [math]\displaystyle{ w }[/math] размерности [math]\displaystyle{ 2^n, }[/math] соответствующий состоянию после преобразования.
Формулы метода:
Элементы итогового вектора записываются в следующем виде:
- [math]\displaystyle{ 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]\displaystyle{ i_1i_2\ldots i_n }[/math] представляет собой двоичную запись индекса элемента в массиве.
Вычислительное ядро алгоритма
Вычислительное ядро алгоритма представляет собой независимое вычисление всех [math]\displaystyle{ 2^n }[/math] элементов вектора [math]\displaystyle{ w. }[/math] Вычисление каждого элемента требует четыре операции умножения и три операцию сложения. Кроме того необходимо вычислять индексы типа [math]\displaystyle{ i_1i_2\ldots j_k \ldots j_l \ldots i_n, }[/math] а также значение битов [math]\displaystyle{ j_k,j_l }[/math] что требует побитовых операций.
Макроструктура алгоритма
Как записано и в описании ядра алгоритма, основную часть метода составляют независимые вычсиления элементов выходного вектора.
Схема реализации последовательного алгоритма
Для каждого индекса [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ 2^n-1 }[/math]
- Вычислить элементы [math]\displaystyle{ i_k, i_l }[/math] двоичного представления индекса [math]\displaystyle{ i. }[/math]
- Для всех четырех бинарных значений [math]\displaystyle{ j_k, j_l }[/math] вычислить индексы [math]\displaystyle{ i_1i_2\ldots j_k \ldots j_l \ldots i_n }[/math]
- Просуммировать [math]\displaystyle{ u^{j_k j_l}_{i_k i_l} v_{i_1i_2\ldots j_k \ldots j_l \ldots i_n}. }[/math]
Последовательная сложность алгоритма
Алгоритм требует:
- [math]\displaystyle{ 2^{n+2} }[/math] операций умножения комплексных чисел;
- [math]\displaystyle{ 3\cdot 2^n }[/math] операций сложения комплексных чисел;
- [math]\displaystyle{ 2^{n+1} }[/math] операций получения значения [math]\displaystyle{ k }[/math]-го бита числа;
- [math]\displaystyle{ 2^{n+3} }[/math] операций изменения значения [math]\displaystyle{ k }[/math]-го бита числа.
Отметим, что данный алгоритм обычно применяется много раз подряд, в связи с чем вычисления, связанные с побитовыми операциями (3-4), могут единожды проводиться в начале алгоритма. Кроме того, от них можно избавиться, пользуясь сложением и логическим умножением с числами [math]\displaystyle{ 2^l, }[/math] и [math]\displaystyle{ 2^k, }[/math] которые сохраняется для всего алгоритма.
Информационный граф
Представим граф алгоритма для случаев [math]\displaystyle{ n=3, k=1, l=2 }[/math] (рис.1) и [math]\displaystyle{ n=3, k=1, l=3 }[/math] (рис.2). На графах не представлены матрицы преобразования [math]\displaystyle{ U, }[/math] в связи с тем, что их размер при больших [math]\displaystyle{ n }[/math] много меньше, нежели размеры входного и выходного векторов.
Отображение графа со входными и выходными данных, а также "свёрнутой" основной операцией удобно для понимания локальности обращений к памяти. Отметим, что структура графа (а именно обращение к входным данным) сильно зависит от параметров [math]\displaystyle{ k,l. }[/math]
Ресурс параллелизма алгоритма
Как видно из информационного графа, прямой алгоритм моделирования однокубитного преобразования обладает высочайшей степенью параллелизма. Все операции вычисления элементов нового вектора-состояния могут быть произведены параллельно. Для вычисления одного элемента необходимо выполнить две операции умножения и одну операцию сложения, операции умножения, в свою очередь, также могут быть выполнены параллельно. Таким образом, необходимо выполнение двух ярусов: одного, состоящего из [math]\displaystyle{ 2^{n+2} }[/math] умножений и другого, состоящего из [math]\displaystyle{ 3 \cdot 2^n }[/math] сложений.
Входные и выходные данные алгоритма
Входные данные:
- Комплексный вектор состояния [math]\displaystyle{ u }[/math] длины [math]\displaystyle{ 2^n. }[/math] Обычно нормирован на единицу.
- Унитарная матрица [math]\displaystyle{ U }[/math] порядка [math]\displaystyle{ 4 }[/math].
- Номера кубитов [math]\displaystyle{ k,l }[/math].
Выходные данные:
- Комплексный вектор состояния [math]\displaystyle{ w }[/math] длины [math]\displaystyle{ 2^n }[/math].
Объем входных данных: [math]\displaystyle{ 2^n+16 }[/math] комплексных чисел и [math]\displaystyle{ 2 }[/math] целочисленых параметра.
Объем выходных данных: [math]\displaystyle{ 2^n }[/math] комплексных чисел.
Свойства алгоритма
Соотношение последовательной и параллельной сложности является экспоненциальным (эксмпонента переходит в константу).
Вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – константа.
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
На языке C функцию двухкубитного преобразования можно записать следующим образом:
void TwoQubitsEvolution(complexd *in, complexd *out, complexd U[4][4], int nqubits, int q1, int q2)
{
//n - число кубитов
//q1, q2 - номера кубитов, над которыми производится преобразование
int shift1=n-q1;
int shift2=n-q2;
//Все биты нулевые, за исключением соответсвующего номеру первого изменяемого кубита
int pow2q1=1<<(shift1);
//Все биты нулевые, за исключением соответсвующего номеру второгоизменяемого кубита
int pow2q2=1<<(shift2);
int N=1<<nqubits;
for (int i=0; i<N; i++)
{
//Установка изменяемых битов во все возможные позиции
int i00 = i & ~pow2q1 & ~pow2q2;
int i01 = i & ~pow2q1 | pow2q2;
int i10 = (i | pow2q1) & ~pow2q2;
int i11 = i | pow2q1 | pow2q2;
//Получение значений изменяемых битов
int iq1 = (i & pow2q1) >> shift1;
int iq2 = (i & pow2q2) >> shift2;
//Индекс в матрице
int iq=(iq1<<1)+iq2;
out[i] = U[iq][(0<<1)+0] * in[i00] + U[iq][(0<<1)+1] * in[i01] + U[iq][(1<<1)+0] * in[i10] + U[iq][(1<<1)+1] * in[i11];
}
}
Особенности последовательной реализации аналогичны Особенности реализации последовательного алгоритма однокубитного преобразования.
Возможные способы и особенности параллельной реализации алгоритма
Результаты прогонов
Выводы для классов архитектур
Литература
- ↑ [Д. А., Ожигов Ю. И., Чернявский А. Ю. Алгебраический аппарат квантовой информатики.]
- ↑ [О. В., Чернявский А. Ю. Практикум по суперкомпьютерным технологиям и квантовым вычислениям 3 курс.]
- ↑ Preskill J. Lecture notes for physics 229: Quantum information and computation //California Institute of Technology. – 1998.
- ↑ Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. – М : Мир, 2006.