Уровень алгоритма

Двухкубитное преобразование вектора-состояния: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
 
(не показано 13 промежуточных версий 3 участников)
Строка 1: Строка 1:
−
Основные авторы описания: [[Участник:Chernyavskiy|А.Ю.Чернявский]]
+
{{algorithm
 +
| name              = Двухкубитное преобразование <br /> вектора-состояния
 +
| serial_complexity = <math>5 \cdot 2^n</math>
 +
| pf_height        = <math>2</math>
 +
| pf_width          = <math>2^{n+2}</math>
 +
| input_data        = <math>2^n+16</math>
 +
| output_data      = <math>2^n</math>
 +
}}
 +
Основные авторы описания: [[Участник:Chernyavskiy|А.Ю.Чернявский]].
  
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
Строка 5: Строка 13:
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
−
Алгоритм производит моделирование действия двухкубитного квантового вентиля на вектор-состояние.  
+
''Алгоритм производит моделирования действия двухкубитного квантового вентиля на вектор-состояние.''
−
 
+
<ref>[[http://sqi.cs.msu.su/store/storage/jpvtv20_algebraic_tools.pdf|Кронберг Д. А., Ожигов Ю. И., Чернявский А. Ю. Алгебраический аппарат квантовой информатики.]]</ref>
 +
<ref>[[http://sqi.cs.msu.su/files/book_v01.pdf|Корж О. В., Чернявский А. Ю. Практикум по суперкомпьютерным технологиям и квантовым вычислениям 3 курс.]] </ref>
 +
<ref>Preskill J. Lecture notes for physics 229: Quantum information and computation //California Institute of Technology. – 1998.</ref>
 +
<ref>Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. – М : Мир, 2006.</ref>
 +
Данный алгоритм обычно является подпрограммой и многократно применяется к различным кубитам одного состояния (например при моделировании квантовых алгоритмов или анализе квантовой запутанности). Особенностью алгоритма, как и большинства алгоритмов квантовой инфоорматики, является экспоненциальный рост объема данных в зависимости от основного параметра - числа кубитов, что приводит к необходимости суперкомпьютерной реализации для решения важных практических задач.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Строка 55: Строка 67:
 
Алгоритм требует:
 
Алгоритм требует:
 
# <math>2^{n+2}</math> операций умножения комплексных чисел;
 
# <math>2^{n+2}</math> операций умножения комплексных чисел;
−
# <math>3\dot 2^n</math> операций сложения комплексных чисел;
+
# <math>3\cdot 2^n</math> операций сложения комплексных чисел;
 
# <math>2^{n+1}</math> операций получения значения <math>k</math>-го бита числа;
 
# <math>2^{n+1}</math> операций получения значения <math>k</math>-го бита числа;
 
# <math>2^{n+3}</math> операций изменения значения <math>k</math>-го бита числа.
 
# <math>2^{n+3}</math> операций изменения значения <math>k</math>-го бита числа.
Строка 61: Строка 73:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
−
Представим граф алгоритма для случаев <math>n=3, k=1, l=2</math>(рис.1) и <math>n=3, k=1, l=3</math>(рис.2). На графах не представлены матрицы преобразования <math>U,</math> в связи с тем, что их размер при больших <math>n</math> много меньше, нежели размеры входного и выходного векторов. Отметим, что структура графа (а именно обращение к входным данным) сильно зависит от параметров <math>k,l.</math>
+
Представим граф алгоритма для случаев <math>n=3, k=1, l=2</math> (рис.1) и <math>n=3, k=1, l=3</math> (рис.2). На графах не представлены матрицы преобразования <math>U,</math> в связи с тем, что их размер при больших <math>n</math> много меньше, нежели размеры входного и выходного векторов.  
 +
 
 +
Отображение графа со входными и выходными данных, а также "свёрнутой" основной операцией удобно для понимания локальности обращений к памяти.
 +
Отметим, что структура графа (а именно обращение к входным данным) сильно зависит от параметров <math>k,l.</math>
 
[[file:TwoQubitVectorTransform_23.png|thumb|center|800px|Рисунок 1. Граф алгоритма для <math>n=3, k=2, l=3</math> без отображения матрицы преобразования <math>U.</math> ]]
 
[[file:TwoQubitVectorTransform_23.png|thumb|center|800px|Рисунок 1. Граф алгоритма для <math>n=3, k=2, l=3</math> без отображения матрицы преобразования <math>U.</math> ]]
 
[[file:TwoQubitVectorTransform_13.png|thumb|center|800px|Рисунок 2. Граф алгоритма для <math>n=3, k=1, l=3</math> без отображения матрицы преобразования <math>U.</math> ]]
 
[[file:TwoQubitVectorTransform_13.png|thumb|center|800px|Рисунок 2. Граф алгоритма для <math>n=3, k=1, l=3</math> без отображения матрицы преобразования <math>U.</math> ]]
 +
[[file:q_operation2.png|thumb|center|400px|Рисунок 3. Граф основной операции.]]
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
 +
Как видно из информационного графа, прямой алгоритм моделирования однокубитного преобразования обладает высочайшей степенью параллелизма. Все операции вычисления элементов нового вектора-состояния могут быть произведены параллельно. Для вычисления одного элемента необходимо выполнить две операции умножения и одну операцию сложения, операции умножения, в свою очередь, также могут быть выполнены параллельно.
 +
Таким образом, необходимо выполнение двух ярусов: одного, состоящего из <math>2^{n+2}</math> умножений и другого, состоящего из <math>3 \cdot 2^n</math> сложений.
 +
 +
=== Входные и выходные данные алгоритма ===
 +
'''Входные данные:'''
  
 +
* Комплексный вектор состояния <math>u</math> длины <math>2^n.</math> Обычно нормирован на единицу.
 +
* Унитарная матрица <math>U</math> порядка <math>4</math>.
 +
* Номера кубитов <math>k,l</math>.
  
−
=== Входные и выходные данные алгоритма ===
+
'''Выходные данные:'''
 +
* Комплексный вектор состояния <math>w</math> длины <math>2^n</math>.
 +
 
 +
'''Объем входных данных:''' <math>2^n+16</math> комплексных чисел и <math>2</math> целочисленых параметра.
  
 +
'''Объем выходных данных:''' <math>2^n</math> комплексных чисел.
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
 +
Соотношение последовательной и параллельной сложности является ''экспоненциальным'' (эксмпонента переходит в константу).
  
 +
Вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''константа''.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
  
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
 +
На языке C функцию двухкубитного преобразования можно записать следующим образом:
 +
 +
<source lang="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];
 +
}
 +
}
 +
</source>
 +
 
 +
Особенности последовательной реализации аналогичны [[Однокубитное преобразование вектора-состояния#Особенности реализации последовательного алгоритма|Особенности реализации последовательного алгоритма однокубитного преобразования]].
  
−
===== Структура обращений в память и качественная оценка локальности =====
 
−
===== Количественная оценка локальности =====
 
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
−
=== Масштабируемость алгоритма и его реализации ===
+
=== Результаты прогонов ===
−
==== Масштабируемость алгоритма ====
 
−
==== Масштабируемость реализации алгоритма ====
 
−
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
−
=== Существующие реализации алгоритма ===
 
  
 +
== Литература ==
  
−
== Литература ==
 
 
<references />
 
<references />
  
 
[[Категория:Статьи в работе]]
 
[[Категория:Статьи в работе]]
 +
[[Категория:Алгоритмы моделирования квантовых систем]]
 +
 +
[[en:Two-qubit transform of a state vector]]

Текущая версия на 15:58, 19 июля 2022


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

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

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

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

Алгоритм производит моделирования действия двухкубитного квантового вентиля на вектор-состояние. [1] [2] [3] [4] Данный алгоритм обычно является подпрограммой и многократно применяется к различным кубитам одного состояния (например при моделировании квантовых алгоритмов или анализе квантовой запутанности). Особенностью алгоритма, как и большинства алгоритмов квантовой инфоорматики, является экспоненциальный рост объема данных в зависимости от основного параметра - числа кубитов, что приводит к необходимости суперкомпьютерной реализации для решения важных практических задач.

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

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

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

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

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


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


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

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

[math] 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]i_1i_2\ldots i_n[/math] представляет собой двоичную запись индекса элемента в массиве.


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Объем входных данных: [math]2^n+16[/math] комплексных чисел и [math]2[/math] целочисленых параметра.

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

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

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

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

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

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

На языке 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];
	}
}

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

2.2 Возможные способы и особенности параллельной реализации алгоритма

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

3 Литература

  1. ↑ [Д. А., Ожигов Ю. И., Чернявский А. Ю. Алгебраический аппарат квантовой информатики.]
  2. ↑ [О. В., Чернявский А. Ю. Практикум по суперкомпьютерным технологиям и квантовым вычислениям 3 курс.]
  3. ↑ Preskill J. Lecture notes for physics 229: Quantum information and computation //California Institute of Technology. – 1998.
  4. ↑ Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. – М : Мир, 2006.
Источник — https://algowiki-project.org/w/ru/index.php?title=Двухкубитное_преобразование_вектора-состояния&oldid=29174