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

4). Пусть

Ma =	a	a		,
	a00	a01
	10	11
	b	b		,
Mb = b00		b01
	10	11

тогда результирующая матрица Mc=Mb ×Ma (именно в таком порядке Mb на Ma, хотя сами гейты в квантовой схеме идут в обратном: порядке сначала преобразование с матрицей Ma, а затем преобразование с матрицей Mb) есть

b

b

a

a

b00

b01

× a00

a01

=

10

11

10

11

b00

a00

+b01 a10

b00

a01

+b01 a11

c00

c01

= b

a

+b

a

b

a

+b

a

=

c

c

=Mc,

10

00

11

10

10

01

11

11

10

11

т.е.

c00	= b00 a00 +b01	a10	,	c01 = b00 a01 +b01 a11 ,
c10	= b10 a00 +b11	a10	,	c11 = b10 a01 +b11 a11 .

V

5). Пусть входной вектор есть | ψ = . Тогда при подаче этого

W

вектора на вход первого гейта с матрицей Ma на его выходе будет следующий вектор | A′ :

a00	a01		V	a00	V + a01	W	′
			×	=			=| A .
a10	a11		W	a10	V +a11 W

411

6). Далее (для квантовой схемы из двух гейтов) при подаче уже этого вектора | A′ на вход второго гейта с матрицей Mb на его

выходе будет вектор | B′ , который определяется следующим образом:

b00 b01

′

b00

b01

a00 V +a01 W

b b

×| A

= b b

× a V + a W

=

10

11

10

11

10

11

b00 [a00 V + a01 W ]+b01

[a10 V +a11

W ]

=

=

[a00

V +a01 W ]+b11 [a10 V +a11

b10

W ]

V [b00a00 +b01 a10 ]+W [b00 a01 +b01

a11 ]

=| B

′

′

,

=

]+W [b10 a01 +b11

=| ψ

V [b10 a00 +b11 a10

a11 ]

1

который и есть результирующий выходной вектор | ψ1′

всей

квантовой схемы из двух последовательно соединенных гейтов,

т.е. | ψ1′ =| B′ .

7). Далее при подаче вектора | ψ

V

на вход другой квантовой

=

W

схемы из одного гейта с матрицей

Mc на его выходе будет сле-

дующий вектор | ψ′2 :

Mc × | ψ =

c c

V

c V +c W

00

01

×

=

00

01

=

c10

c11

W

c10 V +c11 W

V

[b00a00 +b01 a10 ]+W [b00

a01 +b01 a11 ]

′

.

=

[b10

a00

+b11 a10 ]+W [b10

=| ψ

V

a01 +b11 a11 ]

2

Сравнение векторов

| ψ1′

и | ψ′2

показывает, что они иден-

тичны, а значит и сами схемы эквивалентны.

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

412

Из Примера 5.13 и главы 2 следует, что результат произведения унитарных операторов есть унитарный оператор, а значит последовательное применение нескольких однокубитовых гейтов эквивалентно некоторому результирующему однокубитовому гейту (квантовому элементу).

Для рассмотрения далее очередных примеров сформулируем следующее важное правило.

Правило 5.4(1)

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

На практике важно уметь упрощать квантовые схемы. Один из возможных способов упрощения квантовой схемы — это замена одной ее части (или даже целиком ее) другой эквивалентной квантовой схемой. Для этого необходимо заменять группу гейтов в квантовой схеме на один или несколько других гейтов, которые реализуют то же самое унитарное преобразование. Следующий пример показывает, как это можно делать.

Пример 5.14а (тождества и эквивалентные схемы)

Пусть H, X, Y, Z, S, T, I — это обозначения матриц гейтов, представленных в табл. 5.1. Запись, например, вида HXS означает перемножение этих матриц, а сами три гейта последовательно один за другим соединены в обратном порядке, т.е. сначала S, а затем X и H. Проверить тождество HXS ≡Z означает, что необходимо выяснить эквивалентность следующих двух квантовых схем:

?

| ψ

S

X

H

| ψ1′

≡ | ψ

Z

| ψ′2

Знак минус перед обозначением матрицы гейта (например, –Y) означает, что все элементы этой матрицы умножаются на (–1).

413

Последовательность нескольких стоящих подряд одинаковых матриц (гейтов) будем обозначать с помощью показателя степени, например, HHXH как H2XH, или ZZ как Z2, или TTTT как T4

и т.п. (H 2 и H 2 — это разные обозначения, см. рис. 5.10, 5.11).

Отметим, что порядок в последовательности записи матриц (гейтов) очень существенен. Например, HXH и HHX приводят к разному конечному результату, т.е. к разным выходным векторам, поскольку эти последовательности гейтов имеют разные матрицы результирующих преобразований (это является следствием того, что рассматриваемые матрицы подчиняются некоммутативной алгебре).

Требуется выяснить справедливость следующих тождеств:

для 4-х гейтов

T 4 ≡Z,

для 3-х гейтов [1, с.228]

HXH ≡Z,

HYH ≡–Y,

HZH ≡X,

для 2-х гейтов [1, с.116,225]

H 2 ≡I,

I 2 ≡I,

S 2 ≡Z,

T 2 ≡S.

Решение

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

ры | ψ1′ , | ψ′2 и необходимые матрицы преобразования гейтов соответствуют одному и тому же вычислительному базису.

2). Применяя Правило 5.4(1) и учтя, что i = −1 ,

аi = exp(iπ4)= 1+2i ,

414

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

тождество H 2 ≡I
H	2			1				1 1								1		1 1												1	1 1									1 1
		=												×														=		2						×						=
					2												2
								1				−1						1				−1									1				−1					1 −1
					1				1+1 1−1														1					2 0 1 0												≡ I ,
		=								−1 1−(							−1)				=							0 2							=	0 1
					2																		2
								1
тождество I 2 ≡I
		1 0 1 0 1+0 0 +0 1 0																																						≡ I ,
I 2 =									×								=																		=
		0 1 0 1 0																			+0 0 +1 0 1
тождество S 2 ≡Z
		1 0 1 0 1+0 0 +0 1 0																																							≡ Z ,
S2 =										×							=															2 =
		0							i 0					i 0 +0 0 +i																				0				−1
тождество T2 ≡S
		1										0					1											0
T 2 =								1								×							1				(1+i)								=
		0						2				(1+i) 0											2
		1+0										0 +0								0								1							0					1 0			≡S ,
		=										1							2		=																2	=
		0		+0 0 + 2 (1+i)																0								2 (1+							2i +i			)		0 i

тождество T 4 ≡Z

поскольку справедливы T 2 ≡S и S 2 ≡Z, то

T 4 = T 2 T 2 = S T 2 = S S = S 2 ≡Z,

415

тождество HXH ≡Z
0		1				1		1	1
XH =			×								=
						2
1		0						1	−1
	1		0 +1 0 −1										1				1 −1
=				+0 1						=									= M,
		2													2
			1						+0								1 1
HXH = HM =						1		1 1			×				1			1 −1		=	1	1+1 −1+1			=
																					2		−1
						2									2
								1	−1									1 1				1		−1−1
=	1	2				0		=	1		0				≡ Z ,
	2
		0				−2 0				−1

еще один способ проверки (по входу и выходу)

′	| B	′	| C′
| A

	?
| ψ H X H | ψ1′	≡ | ψ	Z	| ψ′2

пусть | ψ = a| 0+b|1 , тогда (см. табл. 5.1)

′

a +b

a −b

| A

=

| 0 +

2 |1 = A| 0 + B|1 ,

2

′

a −b

a +b

| B

= B| 0 + A|1 = 2

| 0 + 2 |1 = E | 0 +W |1 ,

| C

′

=

E +W

| 0 +

E −W

|1 =

2

2

a −b

+

a +b

a −b

+

a +b

=

2

2

| 0 +

2

2

|1 = a| 0 −b|1 ,

2

2

| ψ1′ ≡| C′ = a| 0−b|1 , | ψ′2 = a| 0−b|1 ,

и сравнивая | ψ1′ и | ψ′2 , получаем, что | ψ1′ =| ψ′2 ,

416

тождество HYH ≡–Y

0

−i

1

1

1

YH =

0

×

=

2

i

1

−1

=

1

0 −i

0 +i

=

1

−i

i

= M,

2

2

i +0 i −0

i

i

HYH = HM =

=1 −0

2 2i

1

1 1

×

1

−i i

=

1

−i +i

2i

=

2

2

2

1

−1

i

i

−i −i

i −i

2i

0 i

= −

0 −i

=

0

≡ −Y ,

0

−i

0

i

тождество HZH ≡X
1		0				1					1	1
ZH =				×											=
						2
0		−1									1	−1
	1		1+0 1+0												1				1 1		M,
=												=								=
		2													2
			0		−1 0 +1													−1 1
HZH = HM =						1			1 1						1				1 1		1	1−1 1+1
												×								=	2		+1 1		=
						2									2
									1			−1						−1 1				1		−1
=	1	0			2						0	1	≡ X
	2						=											,
		2			0						1	0

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

Перейдем к рассмотрению еще одного несколько необычного примера для однокубитовых схем.

417

Пример 5.14б (эквивалентность 2-х схем на одном кубите) Известна квантовая схема из кубита и только одного провода без каких-либо последовательно соединенных однокубитовых гейтов.

Требуется определить один однокубитовый гейт, который эквивалентен этому одному проводу. Другими словами, требуется определить унитарную матрицу Mc результирующего преобразования и установить, что следующие две квантовые схемы эквивалентны:

		?
| ψ	| ψ1′	≡ | ψ	Mc	| ψ′2

Решение

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

ры | ψ1′ , | ψ′2 и необходимые матрицы преобразования гейтов соответствуют одному и тому же вычислительному базису.

2). Преобразование, которое выполняет квантовый провод, состоит в том, что не изменяется состояния кубита, что фактически равносильно (см. Правило 5.0в) тождественному преобразованию I с соответствующей унитарной матрицей

1	0
I ≡		,
0	1

а значит | ψ = I | ψ или | ψ1′ = | ψ .

3). Учтя, что для эквивалентных схем обязательно должно выпол-

няться | ψ1′	=| ψ′2 при одинаковом входном векторе | ψ , а
значит | ψ′2	= | ψ , получаем окончательно, что Mc = I или
	Mc =	1	0
			.
		0	1

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

На этом закончим рассмотрение однокубитовых схем и прейдем к алгоритму Дойча и к двухкубитовым квантовым схемам.

418

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

Рассмотрим пример одного из вариантов [7, с.53] первого квантового алгоритма, предложенного в 1985 г. Д. Дойчем (см. раздел 3.1). Можно полагать [7, с.54], что с этого алгоритма и началась фактически область исследования квантовых вычислений.

Алгоритм решает следующую задачу для булевой функции f, отображающей {0, 1} в себя.

Существуют только 4 функции [7, с.53]:

постоянные

f1(0)= f1(1)=0;

f2(0)= f2(1)=1;

биекции (или другое название — сбалансированные) f3(0)=0, f3(1)=1;

f4(0)=1, f4(1)=0.

Имеется возможность вычислить значение функции только один раз. Случайно выбирается одна из 4 функций, но не известно, какая именно.

Ставится задача определить, что это за отобранная функция, т.е. является ли она биекций (само значение этой функции интереса не представляет, и это значение определять не требуется).

Заметим, что в классическом случае для определения такого глобального свойства функции f требуется вычислить как значение f(1), так и значение f(0), что, как очевидно, потребует дважды вычислять значение этой функции.

С помощью квантовых вычислений при решении этой задачи уже потребуется только однократное вычисление значения этой функции(т.е. используется только 1 гейт Uf, вычисляющий f).

Квантовая схема, решающая эту задачу (см. [7]), представлена на рис. 5.18а, а диаграмма переходов (см. и ср. с [7]) с амплитудами вероятностей показана на рис. 5.18б. Отметим (см. рис. 5.18б), что для Uf амплитуды вероятности переходов из 1 в 0 , а также из 0 в 1 не показаны, поскольку они равны нулю.

419

Квантовая схема и диаграмма для алгоритма Дойча

а)

		not			Uf				not
б)
		not			Uf						not
0	i	2	0	0	(-1) f(0)	0	0		i	2	0
1	2							1	2
1 1	2		1	1	(-1) f(1)	1	1	1	2		1
	i	2							i	2

Рис. 5.18

Квантовый элемент Uf — гейт, вычисляющий, значение функции f(x) только один раз, а точнее (см. [7]) амплитуда вероятности на пути x (на траектории, соответствующей x) умножается на спе-

циально подобранный фазовый множитель exp (i π f (x)), где

i= −1= exp (iπ2), exp(iπ)= cos(π)+i sin (π)= cos(π)= −1, т.е.

на (–1) f(0) (на траектории для 0 в Uf); на (–1) f(1) (на траектории для 1 в Uf).

Перейдем к вычислениям.

1). Вычислим вероятность P00 — выхода 0 на входе 0. Согласно диаграмме (см. рис. 5.18б) из 0 в 0 можно прийти только по следующим 2-м траекториям:

траектория 1: { 0 в 0,	0 в 0,	0 в 0 };
траектория 2: { 0 в 1,	1 в 1,	1 в 0 }.
420