Однокубитное преобразование вектора-состояния: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
м |
|||
| Строка 51: | Строка 51: | ||
#Вычислить индексы <math>j</math> имеющие двоичные представления <math>i_1i_2\ldots \overline{i_k} \ldots i_n,</math> где крышка означает обращение бита. | #Вычислить индексы <math>j</math> имеющие двоичные представления <math>i_1i_2\ldots \overline{i_k} \ldots i_n,</math> где крышка означает обращение бита. | ||
#Вычислить <math>w_i = u_{i_k i_k}\cdot v_{i} + u_{i_k \overline{i_k}}\cdot v_j.</math> | #Вычислить <math>w_i = u_{i_k i_k}\cdot v_{i} + u_{i_k \overline{i_k}}\cdot v_j.</math> | ||
| + | |||
| + | === Последовательная сложность алгоритма === | ||
| + | Алгоритм требует: | ||
| + | # <math>2^{n+1}</math> операций умножения комплексных чисел; | ||
| + | # <math>2^n</math> операций сложения комплексных чисел; | ||
| + | # <math>2^n</math> операций получения значения <math>k</math>-го бита числа; | ||
| + | # <math>2^n</math> операций изменения значения <math>k</math>-го бита числа. | ||
| + | Отметим, что данный алгоритм обычно применяется много раз подряд, в связи с чем вычисления, связанные с побитовыми операциями (3-4), могут единожды вычисляться в начале алгоритма. Кроме того, от них можно избавиться пользуясь сложением и побитовым умножением с числом <math>2^k,</math> которое сохраняется для всего алгоритма. | ||
=== Информационный граф === | === Информационный граф === | ||
Версия 22:03, 3 декабря 2014
Содержание
- 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 Математическое описание
Исходные данные:
Целочисленные параметры n - число кубитов (необязательно) и k - номер кубита, над которым производится преобразование.
Комплексная матрица U = \begin{pmatrix} u_{00} & u_{01}\\ u_{10} & u_{11} \end{pmatrix} однокубитного преобразования размера 2 \times 2.
Комплексный вектор v размерности 2^n, задающей начальное состояние многокубитной системы.
Вычисляемые данные: комплексный вектор w размерности 2^n, соответствующий состоянию после преобразования.
Формулы метода:
Состояние после действия преобразования U на k-й кубит имеет вид v_{out} = I_{2^{k-1}}\otimes U \otimes I_{2^{n-k}}, где I_{j} - единичная матрица размерности j, а \otimes - тензорное произведение (произведение Кронекера).
Однако, элементы итогового вектора можно записать и в прямом виде, что более удобно для вычислений:
- 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}
Индекс-кортеж i_1i_2\ldots i_n представляет собой двоичную запись индекса элемента в массиве.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро алгоритма представляет собой независимое вычисление всех 2^n элементов вектора w. Вычисление каждого элемента требует две операции умножения и одну операцию сложения. Кроме того необходимо вычислять индексы типа i_1i_2\ldots 0_k \ldots i_n, а также значение бита i_k, что требует побитовых операций.
1.4 Макроструктура алгоритма
Как записано и в описании ядра алгоритма, основную часть метода составляют независимые вычсиления элементов выходного вектора.
1.5 Описание схемы реализации последовательного алгоритма
Для индекса i от 0 до 2^n-1
- Вычислить элемент i_k двоичного представления индекса i.
- Вычислить индексы j имеющие двоичные представления i_1i_2\ldots \overline{i_k} \ldots i_n, где крышка означает обращение бита.
- Вычислить w_i = u_{i_k i_k}\cdot v_{i} + u_{i_k \overline{i_k}}\cdot v_j.
1.6 Последовательная сложность алгоритма
Алгоритм требует:
- 2^{n+1} операций умножения комплексных чисел;
- 2^n операций сложения комплексных чисел;
- 2^n операций получения значения k-го бита числа;
- 2^n операций изменения значения k-го бита числа.
Отметим, что данный алгоритм обычно применяется много раз подряд, в связи с чем вычисления, связанные с побитовыми операциями (3-4), могут единожды вычисляться в начале алгоритма. Кроме того, от них можно избавиться пользуясь сложением и побитовым умножением с числом 2^k, которое сохраняется для всего алгоритма.
