Двухкубитное преобразование вектора-состояния: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
(Добавление категории.) |
ASA (обсуждение | вклад) |
||
| (не показано 15 промежуточных версий 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|А.Ю.Чернявский]]. | ||
| − | == | + | == Свойства и структура алгоритма == |
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | Алгоритм производит | + | ''Алгоритм производит моделирования действия двухкубитного квантового вентиля на вектор-состояние.'' |
| + | <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> | ||
| + | Данный алгоритм обычно является подпрограммой и многократно применяется к различным кубитам одного состояния (например при моделировании квантовых алгоритмов или анализе квантовой запутанности). Особенностью алгоритма, как и большинства алгоритмов квантовой инфоорматики, является экспоненциальный рост объема данных в зависимости от основного параметра - числа кубитов, что приводит к необходимости суперкомпьютерной реализации для решения важных практических задач. | ||
| − | + | === Математическое описание алгоритма === | |
| − | |||
| − | === Математическое описание === | ||
'''Исходные данные:''' | '''Исходные данные:''' | ||
| Строка 47: | Строка 58: | ||
Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют независимые вычсиления элементов выходного вектора. | Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют независимые вычсиления элементов выходного вектора. | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
Для каждого индекса <math>i</math> от <math>0</math> до <math>2^n-1</math> | Для каждого индекса <math>i</math> от <math>0</math> до <math>2^n-1</math> | ||
#Вычислить элементы <math>i_k, i_l</math> двоичного представления индекса <math>i.</math> | #Вычислить элементы <math>i_k, i_l</math> двоичного представления индекса <math>i.</math> | ||
| Строка 56: | Строка 67: | ||
Алгоритм требует: | Алгоритм требует: | ||
# <math>2^{n+2}</math> операций умножения комплексных чисел; | # <math>2^{n+2}</math> операций умножения комплексных чисел; | ||
| − | # <math>3\ | + | # <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>-го бита числа. | ||
| Строка 62: | Строка 73: | ||
=== Информационный граф === | === Информационный граф === | ||
| − | Представим граф алгоритма для случаев <math>n=3, k=1, l=2</math> и <math>n=3, k=1, l=3</math>. На графах не представлены матрицы преобразования <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> много меньше, нежели размеры входного и выходного векторов. |
| − | [[file:TwoQubitVectorTransform_23.png|thumb|center|800px|Граф алгоритма для <math>n=3, k=2, l=3</math> без отображения матрицы преобразования <math>U.</math> ]] | + | |
| − | [[file:TwoQubitVectorTransform_13.png|thumb|center|800px|Граф алгоритма для <math>n=3, k=1, l=3</math> без отображения матрицы преобразования <math>U.</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_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 /> | ||
[[Категория:Статьи в работе]] | [[Категория:Статьи в работе]] | ||
| + | [[Категория:Алгоритмы моделирования квантовых систем]] | ||
| + | |||
| + | [[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 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
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]
- Вычислить элементы [math]i_k, i_l[/math] двоичного представления индекса [math]i.[/math]
- Для всех четырех бинарных значений [math]j_k, j_l[/math] вычислить индексы [math]i_1i_2\ldots j_k \ldots j_l \ldots i_n[/math]
- Просуммировать [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 Последовательная сложность алгоритма
Алгоритм требует:
- [math]2^{n+2}[/math] операций умножения комплексных чисел;
- [math]3\cdot 2^n[/math] операций сложения комплексных чисел;
- [math]2^{n+1}[/math] операций получения значения [math]k[/math]-го бита числа;
- [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.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 Литература
- ↑ [Д. А., Ожигов Ю. И., Чернявский А. Ю. Алгебраический аппарат квантовой информатики.]
- ↑ [О. В., Чернявский А. Ю. Практикум по суперкомпьютерным технологиям и квантовым вычислениям 3 курс.]
- ↑ Preskill J. Lecture notes for physics 229: Quantum information and computation //California Institute of Technology. – 1998.
- ↑ Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. – М : Мир, 2006.
