Кулик Введение в теорию квантовых вычислений Книга 2 2008

т.е. кубиты и квантовый регистр находятся в чистом состоянии.

	В момент T2				1	1 1				1
	2			1					1
	| ψ1	=H | 0	=				×	=			,
				2					2
					1	−1	0			1

	2				1		1 1 0								1		1
| ψ2		= H	|1	=					×			=						,
					2										2
							1		−1 1							−1
																	1					1
				1		1			1				1		1					1
| Rg2 =| ψ 2	| ψ 2		=								1 =					−1			=		−1 ,
1		2
				2 1					2 −1				2			1				2
															1 −							−1
																	1

т.е. кубиты и квантовый регистр находятся в чистом состоянии.

5). Для того чтобы определить состояния кубитов	| ψ m	, | ψ m	и
	1	2

состояниесоставногоквантовогорегистра | Rgm , где m=3, 4, 5,

т.е. в различные моменты времени, отмеченные на квантовой схеме (рис. 5.24) как T3, T4, T5, получим конкретный вид 4-х унитарных матриц M1, M2, M3, M4 гейта Uf соответственно для каждой булевой функции f1(x), f2(x), f3(x), f4(x).

В Примере 5.22 (Примере 5.15в) с использованием Правила 5.6 найдена (для f3(0)=0, f3(1)=1) следующая матрица:

	1	0	0	0
M3 =	0	1	0	0	,
		0	0
	0			1
	0	0	1	0

которая в точности совпадает с матрицей для квантового элемента CNOT и является матрицей для гейта Uf с f3(x).

501

Поступая аналогичным образом и применяя Правило 5.6 с учетом f1(0)= f1(1)=0 и требований к матрице M1

M| 00 =| 00 , M| 01 =| 01 ,			M|10		=|10 , M|11 =|11 ,
может быть найдена следующая матрица:
	1	0	0	0
M1	= 0	1	0	0	,
		0	1
	0			0
	0	0	0	1

которая в точности совпадает с матрицей I для тождественного преобразования и является матрицей для гейта Uf с f1(x).

Поступая аналогичным образом и применяя Правило 5.6 с учетом f2(0)= f2(1)=1 и требований к матрице M2

M| 00 =| 01 ,	M| 01 =| 00 ,				M|10	=|11	, M|11	=|10	,
может быть найдена следующая матрица:
0	1	0	0
1 0		0	0	1 0 0 1
M2 =				=			=I X,
		0		0 1 1 0
0 0			1
0 0		1	0
которая является матрицей M2 для гейта Uf с f2(x).
Поступая аналогичным образом и применяя Правило 5.6 с уче-
том f4(0)=1, f4(1)=0 и требований к матрице M4
M| 00 =| 01 ,	M| 01 =| 00 ,				M|10	=|10	, M|11	=|11	,
				502

может быть найдена следующая матрица:

	0	1	0	0
M4	= 1 0 0 0				=M3 ×M2,
		0	1
	0			0
	0	0	0	1

которая является матрицей M4 для гейта Uf с f4(x).

6). Продолжим определять состояния кубитов | ψ1m , | ψ2m и со-

стояние самого составного регистра | Rgm , где m=3, 4, 5 в раз-

личные моменты времени, отмеченные на схеме (рис. 5.24) как T3, T4, T5. В моменты T0, T1, T2 эти состояния одинаковы и не зависят от различных унитарных матриц гейта Uf.

В момент T3 (матрица M1)

				| ψ 3				=?
						1
				| ψ2			3	=?
		| Rg3 = M1 ×| Rg2 =
	1 0 0 0				1					1+0				1
	0 1 0 0			1	−1				1		−1+0		1	−1
=			×					=				=				,
				2					2				2
	0 0 1 0					1					1+0				1
	0 0 0 1				−1						−1+0			−1

применим Правило 5.5, получим разложение вектора | Rg3

| Rg	3	=| ψ	3	| ψ	3	=	1	1		1		1	,
					2
		1					2			2
								1				−1
					503

			3	=		1			1
		| ψ1							,
						2
									1
		| ψ2	3	=		1				1
											.
						2
								−1
В момент T3 (матрица M2)
			| ψ 3			=?
				1
			| ψ2		3	=?
		| Rg3 = M2 ×| Rg2 =
	0 1 0 0			1						−1+0					−1
	1 0 0 0		1	−1					1		1+0			1		1
=													=
		×	2	=					2					2			,
	0 0 0 1			1							−1+0				−1
	0 0 1 0			−1							1+0					1

применим Правило 5.5, получим разложение вектора | Rg3

| Rg	3	=| ψ	3	| ψ			3		=			1			1		1		−1	,
							2
		1												2			2
															1				1
				| ψ1	3		=		1				1
													,
									2
													1
				3			=		1					−1
				| ψ2											.
									2
														1
В момент T3 (матрица M3)
						| ψ 3			=?
							1
						| ψ2		3	=?
							504

				| Rg3 = M3 ×| Rg2 =
	1 0		0 0				1				1+0				1
	0 1		0 0			1	−1			1		−1+0		1	−1
=					×				=				=				,
		0	0			2				2				2
	0			1				1				−1+0			−1
	0	0	1	0			−1					1+0				1

применим Правило 5.5, получим разложение вектора | Rg3

| Rg3 =| ψ 3		| ψ		3		=		1						1			1				1 ,
				2
	1										2						2
														−1						−1
		| ψ13		=		1							1
														,
						2
										−1
		| ψ2	3	=		1							1
														.
						2
										−1
В момент T3 (матрица M4)
			| ψ		3		=?
				1
			| ψ2			3	=?
	| Rg3 = M4 ×| Rg2 =
	0 1 0 0			1									−1+0							−1
	1 0 0 0		1	−1							1			1+0				1			1
=							=										=
		×	2								2			1+0				2				,
	0 0 1 0				1																1
	0 0 0 1			−1										−1+0						−1
				505

применим Правило 5.5, получим разложение вектора | Rg3

		| Rg	3		=| ψ		3	| ψ		3			=				1						1							1 −1						,
										2
						1
																			2					−1						2			1
								| ψ13		=			1										1
																								,
														2
																		−1
									3	=				1				−1
								| ψ2																.
														2
																							1
В момент T4 (матрица M1)																												1+1 1
	4	=H | ψ1		3		1		1 1						1							1						1
| ψ1					=				−		×										=						2						=				=| 0 ,
							2										2
								1		1											1							1−1 0
						| ψ24 = | ψ23 =															1					1		,
																					2
																									−1
																																				1
											1										1				1						1
		| Rg4 = | ψ 4						| ψ 4		=																				=				−1 .
					1				2															2								2				0
											0															−1
В момент T4 (матрица M2)																																				0
																												1+1 1
	4	=H | ψ1		3		1		1 1						1							1						1
| ψ1					=				−		×										=						2						=				=| 0 ,
							2										2
								1		1											1							1−1 0
						| ψ2		4	= | ψ2		3			=							1				−1			,
																					2
																										1
																																			−1
											1										1				−1						1
		| Rg4 = | ψ 4						| ψ 4		=																				=						1 .
					1				2															2								2				0
											0																1
																																				0
										506

В момент T4 (матрица M3)																			1−1 0
4	3			1	1 1			1					1					1
| ψ1	=H | ψ1	=					×									=		2				=			=|1 ,
				2					2
					1	−1					−1								1	+1 1
				| ψ24 = | ψ23 =							1						1
														,
											2
														−1
																							0
							0					1						1			1
	| Rg4 = | ψ 4			| ψ 4 =															=				0 .
		1				2							2							2			1
							1										−1
																							−1
В момент T4 (матрица M4)
																			1−1 0
4	3			1	1 1			1					1					1
| ψ1	=H | ψ1	=					×									=		2				=			=|1 ,
				2					2
					1	−1					−1								1	+1 1
					4		3	=			1			−1
				| ψ2		= | ψ2								,
											2
																	1
																							0
							0					1				−1					1
	| Rg4 =	| ψ 4		| ψ 4 =															=				0 .
		1				2							2							2			−1
							1											1
																							1

Вмомент T5 (матрица M1 или M2)

свероятностью 1 измерение покажет

для 1-го кубита состояние | 0 .

Вмомент T5 (матрица M3 или M4)

свероятностью 1 измерение покажет

для 1-го кубита состояние |1 .

Отметим, что само измерение, вообще говоря, влияет на состояние кубита.

507

6). Сведем полученные результаты в следующую табл. 5.3.

Таблица 5.3. Состояния кубитов в алгоритме Д. Дойча

Функция

Момент времени

T4

T5

1-й кубит

2-й кубит

1-й кубит

f1

| 0

1

| 0

−

1

|1

С

вероятно-

+

2

2

стью

1

(после

f2

| 0

измерения)

1

1

кубит

будет

−

2

| 0

−

2

|1

обнаружен

в

состоянии | 0

f3

|1

1

| 0

−

1

|1

С

вероятно-

+

2

2

стью

1

(после

f4

|1

измерения)

1

1

кубит

будет

−

2

| 0

−

2

|1

обнаружен

в

состоянии |1

Эта таблица позволяет уже получить окончательное решающее

правило.

7). Таким образом, для определения свойства функции можно

предложить следующее решающее правило:

•если измерение состояния 1-го (верхнего) кубита (т.е. ре-

гистра данных) показало, что состояние этого кубита | 0 , то функция f(x) является постоянной;

•если измерение состояния 1-го (верхнего) кубита (т.е. ре-

гистра данных) показало, что состояние этого кубита |1 , то функция f(x) является сбалансированной.

8). И тем самым задача решена ▄

508

Краткие методические замечания для квантового алгоритма Д. Дойча на двух кубитах

Наиболее существенное замечание связано с гейтом Uf, реализующим вычисление одной из 4-х, но нам не известной функции f(x). Обычно предполагают (см. [1, с.55-57; 14, с.146]), что Uf —

некоторый «черный ящик», или другое его название оракул, содержимое которого нам по какой-то причине недоступно. Оракул может выдавать значение функции для любого допустимого значения на его входе. В каком-то смысле оракул может быть представлен как некоторая программа для ЭВМ. Эту программу можно запускать на ЭВМ и вычислять значения функции (но какая из 4-х функций f1(x), f2(x), f3(x) или f4(x) реализована в этой программе, нам не известно). Исходный текст этой программы или то, как она работает, нам также не известны (не доступны). Причины этого могут быть разные, например юридические (существующие нормативные документы не всегда разрешают восстанавливать исходный текст программы путем дизассемблирования исполняемого кода) или технические (исходный текст сложен и очень запутан, и нет механического способа [14, с.150] узнать, какая в ней реализована функция быстрее, чем запустить эту программу на ЭВМ достаточное число раз и по результатам работы этой программы сделать вывод о реализованной в ней функции).

Действительно, ниже представлен следующий исходный текст программы fun1 на языке Си:

Int fun1(x) int x;

{

double otvet;
x=0;	/вычисление функции/
otvet=x
return(otvet);
}

509

Программисту достаточно одного беглого взгляда на этот текст программы, чтобы сразу понять, что эта программа при любых исходных значениях выдает на выход только 0, т.е. в программе реализована именно функция f1(x). Однако следующий исходный текст не столь очевиден:

Даже очень опытный программист будет испытывать затруднение в интерпретации этого вырожденного исходного текста, представленного пустым множеством символов (чистый, белый лист бумаги). Этот исходный текст есть модифицированная программа VACUUM [15] на специальном языке программирования. Знание о том, что делает эта программа, доступна создателю [15] программы, а не нам (поэтому для нас она представляется как

«черный ящик»).

Можно отметить, что эта программа на специальном языке программирования, реализует именно функцию f2(x). Для того чтобы на практике определить, какую функцию реализует программа, необходимо достаточное число раз (т.е. 2 раза) запустить ее на ЭВМ, зафиксировать выдаваемые ею результаты и по ним уже сделать вывод о реализованной в программе функции.

В заключение необходимо отметить, что рассматриваемый алгоритм Д. Дойча был успешно реализован (см. работу [13]) на практике экспериментальным путем на молекуле хлороформа при использовании ЯМР.

510