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

5.8. Трех- и более кубитовые схемы

«…состояние составной системы, не представимое в виде произведения состояний входящих в эту систему компонент, является запутанным. По причинам, которые до конца не ясны, запутанные состояния играют ключевую роль в квантовых вычислениях и обработке квантовой информации.»

М. Нильсен, И. Чанг [1, с.133]

Многокубитовые (т.е. трех- и более кубитовые) схемы, которые будем далее рассматривать, содержат следующие компоненты:

•три или более кубита;

•набор одно- , двухкубитовых гейтов;

•набор трехкубитовых гейтов;

•квантовые провода;

•специальные графические символы на квантовых проводах;

•измеритель (иногда на квантовых схемах не показывают).

Втабл. 5.4 приведены условные обозначения наиболее распространенных квантовых элементов (трехкубитовых гейтов).

Черная точка (для гейтов из табл. 5.4) означает то же самое, что

идля двухкубитовых гейтов (эти точки обозначают управляющие кубиты). Управляемый кубит (в данном случае он изображен как самый нижний кубит) подвергается операции, когда управляющие кубиты (в данном случае они изображены как два самых верхних кубита и обозначены этими черными точками) находятся оба в состоянии 1 . В элементе Фредкина черная точка (на линии управ-

ляющего кубита) означает, что выполняется управляемый обмен между двумя самыми нижними кубитами, когда самый верхний кубит находится в состоянии 1 .

Аналогично, как и для двухкубитовых гейтов, можно ввести обозначение в виде светлого кружка (вместо черного), означающее, что управляемый кубит (т.е. самый нижний кубит) подвергается операции, например, НЕ (в элементе Тоффоли) или операции U (в элементе C2U), когда управляющие кубиты (т.е. два самых верхних кубита) находится в состоянии 0 ).

511

Таблица 5.4. Трехкубитовые гейты (см. [1, с.16-17] и др.)

Наиме-	Возможное условное	Унитарная матрица гейта
нование	обозначение
гейта

Элемент														1	0	0	0	0	0	0	0
Тоффоли															1
														0		0	0	0	0	0	0
															0	1	0	0	0	0
														0							0
														0	0	0	1	0	0	0	0
														0	0	0	0	1	0	0	0
															0	0	0	0	1	0
														0							0
														0	0	0	0	0	0	0	1
														0 0 0 0 0 0 1							0
Элемент														1	0	0	0	0	0	0	0
Фредкина															1	0	0	0	0	0
														0							0
															0	1	0	0	0	0
														0							0
														0	0	0	1	0	0	0	0
														0	0	0	0	1	0	0	0
																				1
														0	0	0	0	0	0		0
														0	0	0	0	0	1	0	0
														0 0 0 0 0 0 0 1
Элемент														1	0	0	0	0	0	0	0
Тожде-															1	0	0	0	0	0
ственно-														0							0
															0	1	0	0	0	0
го преоб-				I										0							0
														0	0	0	1	0	0	0	0
разова-
														0	0	0	0	1	0	0	0
ния															0	0	0	0	1	0
														0							0
														0	0	0	0	0	0	1	0
														0 0 0 0 0 0 0 1
Элемент														1	0	0	0	0	0	0	0
2
C U														0 1 0 0 0 0 0 0
															0	1	0	0	0	0	0
														0
														0	0	0	1	0	0	0	0		,
														0	0	0	0	1	0	0	0
					U
														0 0 0 0 0 1 0 0
														0	0	0	0	0	0	A	B
														0 0 0 0 0 0 C D
															U		A		B
																=
																	C		D

512

В главе 2 было рассмотрено очень важное теоретическое положение. Все двухкубитовые гейты (операции) могут быть представлены (построены) с помощью только однокубитовых гейтов (преобразований) и двухкубитовых гейтов CNOT. Было показано, что трехкубитовые гейты (и многокубитовые) могут быть также представлены (построены) с помощью только однокубитовых преобразований и фундаментального гейта CNOT. Опираясь на это, можно сформулировать следующее важное правило для многокубитовых квантовых схем.

Правило 5.9 Любую многокубитовую схему (т.е. в квантовую схему,

в которой число кубитов квантового регистра больше двух) можно синтезировать, используя только 2 типа гейтов — однокубитовые гейты и двухкубитовые гейты CNOT ▄

Для многокубитовых схем (т.е. квантовых схем с числом кубитов больше двух) сформулируем еще аналогично Правилу 5.8 следующее важное правило.

Правило 5.10 Если в многокубитовой схеме (т.е. в квантовой схеме, в

которой число кубитов квантового регистра больше двух) применяется n-й кубитовый гейт, где n >2 (с унитарной матрицей M) к состояниям n кубитов (предполагается,

что квантовый регистр имеет состояние | Rg ), то для

каждого базисного вектора следует применять преобразование этого гейта, изменяющее состояние только этих n кубитов согласно матрице M и не затрагивающее состояния других кубитов в этом базисном состоянии ▄

Данное правило позволяет относительно быстро вычислять новый вектор состояния квантового регистра.

Сокращенные примеры (рассмотренные ниже) кратко покажут, как можно применять некоторые введенные правила.

513

Воспользовавшись результатами глав 2, 3, можно выполнять прямой анализ, обратный анализ и синтез квантовых схем, содержащих многокубитовые гейты. Соответствующие некоторые примеры и необходимые приемы были разобраны ранее.

В случае трех- и более кубитовых схем следует поступать аналогично, как в случае меньшего числа кубитов.

Так, если требуется решить задачу прямого анализа для квантовой схемы с числом кубитов больше 2, можно поступить, например, следующим образом. Вычислить (опираясь на Правило 5.0в, Правила 5.4(1), 5.4(2)) матрицу результирующего преобразования (если она не известна из условия задачи) и затем, применяя необходимым образом Правила 5.0 а, б и с учетом Правила 5.7, 5.8, 5,10 уже вычислить выходной вектор квантового регистра (и если есть возможность, то вычислить векторы состояний отдельных кубитов). В отличие от квантовых схем с малым числом кубитов задача обратного анализа для квантовой многокубитовой схемы с числом кубитов больше 2 представляет уже некоторую трудность в ее решении, но при этом известно как надо ее решать.

Для решения обратной задачи можно поступать аналогично, как это было сделано при решении подобных задач с малым числом кубитов. Для этого надо знать унитарную матрицу результирующего преобразования для данной квантовой схемы. Зная эту матрицу и выходной вектор квантового регистра, необходимо составить соответствующую этим данным систему уравнений и затем попытаться решить ее. Если решение найдено, то входной вектор будет известен. Затем надо факторизовать его и попытаться найти векторы состояний отдельных кубитов. Если отдельные векторы кубитов существуют, то состояния этих кубитов есть чистое состояние, а если векторы отдельных кубитов не существуют, то это будет означать, что состояния этих кубитов есть смешанное состояние.

Для решения задачи синтеза можно поступать так же, как при решении задач с малым числом кубитов. Эта задача в общем виде пока далека от своего окончательного решения, так как представляет серьезную проблему в области квантовых вычислений.

Многокубитовая схема алгоритма Дойча была достаточно подробно рассмотрена в главе 3 и поэтому далее она не обсуждается. Далее остановимся на примерах, опирающихся на унитарные матрицы и матричное исчисление.

514

Пример 5.28 (построение конкретной унитарной матрицы) Известны требования к унитарной матрице M размером 8×8 в виде

	M| 000	=| 000	,	M| 001 =| 001 ,
	M| 010	=| 010	,	M| 011 =| 011 ,
M|100	= a|100	+ c|101 , M|101			= b|100	+ d |101 ,
M|110	= a|110	+ c|111 , M|111			= b|110	+ d |111 ,

где | 000 , | 001 , | 010 , | 011 , |100 , |101 , |110 , |111 —

это вычислительный базис 3-х кубитов (базисные векторы), а

| 0	1	,	|1	0	,	a	b	,	V †V = I .
	=			=		V =
	0			1		c	d

Требуется определить унитарную матрицу M.

Решение

1). Пусть E имеет представление

E = (eik),

где i =0, 2, …, 7; k =0, 2, …, 7.

2). Применим Правило 5.6 и будем искать решение, т.е. элементы некоторой матрицы E как решение следующей системы из 8 уравнений:

E | 000 =| 000 ,

E | 001 =| 001 ,

E | 010=| 010,

E | 011 =| 011 ,

E |100 = a|100 +c|101 ,E |101= b|100+ d |101,E |110= a|110+c|111,

E |111 = b|110 + d |111 .

515

Если решение этой системы уравнений не существует (eik, — комплексные числа и элементы матрицы E), то не существует и самой матрицы M. Отметим, что если подматрица V унитарна, то решение существует (см. ранее сделанный комментарий к задачам синтеза унитарного преобразования).

	3). Так как				1					0
		| 0 =						|1
					,					= ,
					0					1
	то, опираясь на Пример 5.15а, по аналогии следует, что базис-
	ные векторы
	| 000	, | 001 , | 010			, | 011 ,				|100 , |101				, |110 , |111
	могут быть представлены в виде
				1						0				0				0
				0						1				0				0
				0						0				1				0
	| 000 =| 0	| 0 | 0	=	0		,	| 001		=	0	,	| 010	=	0		, | 011	=	1	,
				0						0				0				0
				0						0				0				0
				0						0				0				0
				0						0				0				0
				0						0				0				0
				0						0				0				0
				0						0				0				0
		|100	=	0		,	|101		=	0	,	|110	=	0		, |111	=	0	,
				1						0				0				0
				0						1				0				0
				0						0				1				0
				0						0				0				1
							516

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

e00			1
e10			0
e				0
	20
e30			= 0			,
e			0
	40
e50			0
e			0
	60
			0
e70
e04			0
e14			0
e			0
	24
e34		= 0				,
e			a
	44
e54			c
e			0
	64
e			0
	74

e01e11

e21

e31 =e41

e51e61

e71

e05e15

e25

ee35 =45e55e65

e75

010

00 ,000

000

0b ,d00

e02		0
e12		0
e		1
22
e32	= 0		,
e		0
42
e52		0
e		0
62
e		0
72
e06		0
e16		0
e		0
26
e36		= 0			,
e		0
46
e56		0
e		a
66
e		c
76

e03				0
e13				0
e					0
	23
e33		= 1				,
e				0
	43
e53				0
e				0
	63
				0
e73
e07				0
e17				0
e				0
	27
e37				= 0			.
e				0
	47
e57				0
e				b
	67
e				d
	77

4). Таким образом, найдено следующее решение для матрицы Е:

	1	0	0	0	0	0	0	0
		1	0	0	0	0	0	0
	0
		0	1	0	0	0	0	0
	0
E =	0	0	0	1	0	0	0	0
	0 0 0 0 a b						0	0	.
		0	0	0	c	d	0	0
	0
	0	0	0	0	0	0	a	b
		0	0	0	0	0	c
	0							d
				517

5). Для найденной матрицы E проверим свойство унитарности,

т.е. EE† = E† E = I .

E† E =

1	0	0
	1	0
0
0	0	1
	0	0
0
=	0	0
0
	0	0
0
	0	0
0
	0	0
0
1		0
	1
0	1
=	0

0	0	0	0
0	0	0	0
0	0	0	0
1	0	0	0
0	a	b	0
0	c	d	0
0	0	0	a
0	0	0	c

0

1

a*	c*
b*	d*
0	a*
	b*

0

0

0

0

0

0 b d

0

	†			1	0	0	0
					1	0	0
				0
					0	1	0
				0
			×	0	0	0	1
				0	0	0	0
					0	0	0
				0
					0	0	0
				0
				0	0	0	0
				1		0
					1
				0		1
							1
			×
					0
c*
d	*

1			0		0
		1
	0	1
				1
=								≡ I,
		0		1	0	0
				0	1
				0	1		0
					0
							1

	0	0	0	0
	0	0	0	0
	0	0	0	0
	0	0	0	0		=
	a	b	0	0
	c	d	0	0
	0	0	a	b
	0	0	c	d
		0
						=
	a	b	0
	c	d
	0		a	b
			c
				d

т.е. свойство унитарности матрицы E выполняется. Так как E унитарна, то она есть искомая матрица, т.е. M=E.

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

518

Пример 5.29 (представление 3-кубитового гейта)

Вернемся к главе 2 и рассмотрим (табл. 5.4) 3-кубитовый элемент C2(U) с известной унитарной матрицей M0 размером 8×8 в виде

	1			0
			1
	0		1	1
M0=
			0
w	s	,		a
где V 2=U, U =			V =
z	t			c

	0
				,
1	0	0
0	1
0		w	s
		z
			t

, U и V — унитарные матри-

d

цы с комплексными элементами, где

w= a2+cb; s = ab+bd; z = ac+cd; t = cb+d2.

Требуется установить, что следующие две квантовые схемы эквивалентны:

		?
	U	≡
		V	V†	V

Решение

1). В условиях задачи не указан явно вычислительный базис. Будем далее предполагать, что входные векторы, выходные векторы, а также и все используемые матрицы преобразования соответствуют одному и тому же вычислительному базису.

519

2). Эквивалентность двух схем понимается в том смысле, что матрица M0 (гейта C2U) эквивалентна матрице Еc результирующего преобразования пяти гейтов (два гейта имеют матрицу V, один гейт матрицу V† и два гейт CNOT — матрицу Mb). Специально еще раз отметим, что результирующее преобразование с матрицей Еc зависит, вообще говоря, от порядка, в котором выполняются операции с матрицами (т.е. от порядка, в котором выполняются гейты).

3). Таким образом, применяя Правило 5.0в и учитывая Правило 5.4(2), необходимо сначала найти матрицы M1, M2, M3, M4 для системы из 3-х кубитов и вычислить матрицу Еc, где

Еc=M4 ×M2 ×M3 ×M2 ×M1,

и затем уже сравнить Еc с матрицей M0. Если Еc ≡ M0, то схемы эквивалентны.

4). Матрица (табл. 5.2) для гейта CNOT есть

1	0	0	0
Mb = 0	1	0	0	,
	0	0
0			1
0	0	1	0

матрица для гейта CNOT, с учетом третьего кубита, есть

			1			0		0
					1
1	0			0	1
		=				1					,
M2= Mb I= Mb
0	1				0		0	1
										0
								0		1
							1	0	0
							0	1
	520