Двухкубитное преобразование вектора-состояния - История изменений

ASA в 12:58, 19 июля 2022

2022-07-19T12:58:19Z

← Предыдущая версия		Версия от 12:58, 19 июля 2022
Строка 7:		Строка 7:
	\| output_data = <math>2^n</math>		\| output_data = <math>2^n</math>
	}}		}}
	Основные авторы описания: [[Участник:Chernyavskiy\|А.Ю.Чернявский]]		Основные авторы описания: [[Участник:Chernyavskiy\|А.Ю.Чернявский]].

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
Строка 146:		Строка 146:

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

	~~=== Локальность данных и вычислений ===~~
	Особенности локальности алгоритма двухкубитного преобразования аналогичны [[Однокубитное преобразование вектора-состояния#Локальность данных и вычислений\|таковым для однокубитного преобразования]]
	~~==== Локальность реализации алгоритм ====~~

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

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

			== Литература ==

	~~== Литература ==~~
	<references />		<references />

ASA в 14:13, 14 марта 2018

2018-03-14T14:13:10Z

← Предыдущая версия		Версия от 14:13, 14 марта 2018
Строка 168:		Строка 168:
	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]
	[[Категория:Алгоритмы моделирования квантовых систем]]		[[Категория:Алгоритмы моделирования квантовых систем]]

			[[en:Two-qubit transform of a state vector]]

AntonChupin в 13:13, 8 июля 2016

2016-07-08T13:13:32Z

← Предыдущая версия		Версия от 13:13, 8 июля 2016
Строка 167:		Строка 167:

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]
			[[Категория:Алгоритмы моделирования квантовых систем]]

Chernyavskiy: /* Общее описание алгоритма */

2015-08-26T16:51:01Z

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

← Предыдущая версия		Версия от 16:51, 26 августа 2015
Строка 13:		Строка 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>
			Данный алгоритм обычно является подпрограммой и многократно применяется к различным кубитам одного состояния (например при моделировании квантовых алгоритмов или анализе квантовой запутанности). Особенностью алгоритма, как и большинства алгоритмов квантовой инфоорматики, является экспоненциальный рост объема данных в зависимости от основного параметра - числа кубитов, что приводит к необходимости суперкомпьютерной реализации для решения важных практических задач.

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

Chernyavskiy: /* Локальность данных и вычислений */

2015-08-26T16:49:39Z

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

← Предыдущая версия		Версия от 16:49, 26 августа 2015
Строка 144:		Строка 144:

	=== Локальность данных и вычислений ===		=== Локальность данных и вычислений ===
			Особенности локальности алгоритма двухкубитного преобразования аналогичны [[Однокубитное преобразование вектора-состояния#Локальность данных и вычислений\|таковым для однокубитного преобразования]]
	==== Локальность реализации алгоритм ====		==== Локальность реализации алгоритм ====

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

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

Chernyavskiy: /* Особенности реализации последовательного алгоритма */

2015-08-26T16:48:00Z

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

← Предыдущая версия		Версия от 16:48, 26 августа 2015
Строка 103:		Строка 103:

	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
			На языке 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>

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

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

Chernyavskiy: /* Свойства алгоритма */

2015-08-26T16:41:53Z

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

← Предыдущая версия		Версия от 16:41, 26 августа 2015
Строка 96:		Строка 96:

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

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

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

Chernyavskiy: /* Входные и выходные данные алгоритма */

2015-08-26T16:41:33Z

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

← Предыдущая версия		Версия от 16:41, 26 августа 2015
Строка 91:		Строка 91:
	* Комплексный вектор состояния <math>w</math> длины <math>2^n</math>.		* Комплексный вектор состояния <math>w</math> длины <math>2^n</math>.

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

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

Chernyavskiy: /* Входные и выходные данные алгоритма */

2015-08-26T16:40:48Z

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

← Предыдущая версия		Версия от 16:40, 26 августа 2015
Строка 82:		Строка 82:

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===
			'''Входные данные:'''

			* Комплексный вектор состояния <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> комплексных чисел.

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

Chernyavskiy: /* Ресурс параллелизма алгоритма */

2015-08-26T16:39:38Z

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

← Предыдущая версия		Версия от 16:39, 26 августа 2015
Строка 78:		Строка 78:

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

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