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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Добавление категории.)
Строка 1: Строка 1:
 
Основные авторы описания: [[Участник:Chernyavskiy|А.Ю.Чернявский]]
 
Основные авторы описания: [[Участник:Chernyavskiy|А.Ю.Чернявский]]
  
== Описание свойств и структуры алгоритма ==
+
== Свойства и структура алгоритма ==
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
Строка 8: Строка 8:
  
  
 
+
=== Математическое описание алгоритма ===
=== Математическое описание ===
 
  
 
'''Исходные данные:'''  
 
'''Исходные данные:'''  
Строка 46: Строка 45:
 
Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют независимые вычсиления элементов выходного вектора.
 
Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют независимые вычсиления элементов выходного вектора.
  
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
 
Для индекса <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</math> двоичного представления индекса <math>i.</math>
 
#Вычислить элемент <math>i_k</math> двоичного представления индекса <math>i.</math>
Строка 65: Строка 64:
 
[[file:OneQubitVectorTransform.png|thumb|center|800px|Граф алгоритма для <math>n=3, k=2</math> без отображения матрицы преобразования <math>U.</math> ]]
 
[[file:OneQubitVectorTransform.png|thumb|center|800px|Граф алгоритма для <math>n=3, k=2</math> без отображения матрицы преобразования <math>U.</math> ]]
  
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
 
 
 
 
 
 
=== Описание входных и выходных данных ===
 
  
 +
=== Входные и выходные данные алгоритма ===
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
  
 
+
== Программная реализация алгоритма ==
== Программная реализация ==
 
 
 
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
 
+
=== Локальность данных и вычислений ===
 
+
==== Локальность реализации алгоритма ====
=== Описание локальности данных и вычислений ===
+
===== Структура обращений в память и качественная оценка локальности =====
 
+
===== Количественная оценка локальности =====
==== Описание локальности алгоритма ====
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
+
=== Масштабируемость алгоритма и его реализации ===
==== Описание локальности реализации алгоритма ====
+
==== Масштабируемость алгоритма ====
 
+
==== Масштабируемость реализации алгоритма ====
===== Описание структуры обращений в память и качественная оценка локальности =====
+
=== Динамические характеристики и эффективность реализации алгоритма ===
 
+
=== Выводы для классов архитектур ===
 
+
=== Существующие реализации алгоритма ===
  
 
== Литература ==
 
== Литература ==
 
+
<references />
  
 
[[Категория:Статьи в работе]]
 
[[Категория:Статьи в работе]]

Версия 17:47, 28 июля 2015

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

Содержание

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

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

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


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

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

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

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

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


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


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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

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

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

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

2.7 Существующие реализации алгоритма

3 Литература