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

который написал Боб, т.е.
(M (T ))m (mod c)=T .	(3.59)

В этой криптографической системе числа c и t являются открытым ключом и известны всем. Секретный ключ m можно найти, только зная простые делители числа c.

Квантовое преобразование Фурье

Пусть f (x) есть функция битов, т.е. функция дискретной пере-

менной x, которая принимает значение от 0 до N −1, где N = 2n . Дискретное преобразование Фурье φ(x) функции f (x) определяется выражением

	1	N −1			xy
φ(x) =		∑exp		2πi	f ( y) .	(3.60)
	N y=0				N

Рассмотрим сначала классическую процедуру вычисления сум-

мы	(3.60).	Если	совокупность	дискретных	значений
{f (0), f (1),…, f (N −1)}			функции f	и аналогичную совокуп-
ность значений		{φ(0),φ(1),…,φ(N −1)}		функции φ	рассматри-

вать как два вектор-столбца, то преобразование (3.60) означает, что

искомая функция φ получается из f				в результате действия уни-
тарной1 N × N матрицы F с матричными элементами
Fxy =	1	exp		2πi	xy
						.	(3.61)
	N
					N

Из определения (3.60) видно, что «бесхитростное» вычисление N

1 Унитарность матрицы (3.61) доказывается в задаче 2 в конце этого раздела.

251

значений функции φ(x) для каждой совокупности значений f ( y) потребует порядка N 2 операций.

В рассматриваемом нами случае, когда N = 2n , существует классическая оптимизация процесса вычисления, которая сокраща-

ет трудоемкость до числа операций порядка N log2 N = n2n . Такая

процедура вычисления называется быстрым преобразованием Фурье.

Для этого вспомним, что x и y можно представить в виде n-разрядных разложений по степеням двойки:

x = x

2n−1

+ x

2n−2 + + x 2 + x

n−1

n−2

1

0

(3.62)

y

= y

2n−1

+ y

2n−2

+ + y

2 + y ,

n−1

n−2

что xi , yi

1

0

так

= 0,1,

а состоящие

из

нулей

и единиц стро-

ки

(xn−1xn−2

xk x1x0 )

и

(yn−1 yn−2

yk y1 y0 ) являются

n-разрядными двоичными записями чисел x и y соответственно. При вычислении матричных элементов (3.61) в разложении про-

изведения	x y по степеням двойки достаточно удержать только
слагаемые,	содержащие 2k	с k ≤ n −1,	поскольку члены с более
высокими	степенями уже,	очевидно,	не влияют на величину
exp(2πixy	2n ), так как дают множители, равные единице. Тогда

существенную

для вычисления

часть

величины

xy 2n можно

представить в форме

xy

x

x

x

x

x

x

n → yn−1

0

+ yn−2

1

+

0

+ yn−3

2

+

1

+

0

+ +

2

2

2

2

2

3

2

2 2 2

+ + y

xn−2

+

xn−3

+

x1

+

x0

+

1

2

2

2

2

n−2

2

n−1

x			x			x
+ y0	n−1	+		1	+	0		≡
	2		2	n−1		n
						2

≡ yn−1 (ix0 )+ yn−2 (ix1x0 )+ yn−3 (ix2 x1x0 )+ + y1 (ixn−2 xn−3 x1x0 )+ y0 (ixn−1xn−2

(3.63)

+

x0 ).

252

Здесь на последнем шаге введено обозначение для двоичных дробей в виде множителей, написанных в скобках. Например,

(ix x x			)≡	x2	+	x1	+	x0	.	(3.64)
2	1	0	2		22		23

Подставляя разложение (3.63) в (3.61), получаем

F = 1		n−1	exp	2πiy		(ix − −	x	) . (3.65)
xy		∏			k	n k 1	0
	N
		k =0

Для вычисления функции φ(x) надо, согласно (3.60), умножить f (y) на Fxy и просуммировать по всем y. С помощью представления (3.65) для матрицы Fxy суммирование по y сводится к суммированию по двум возможным значениям yk = 0,1 каждого двоич-

ного разряда числа y. Поэтому число операций, которое требуется для вычисления φ(x) для одного из N значений переменной x, оп-

ределяется количеством сомножителей в произведении (3.65), т.е. порядка n = log2 N . Полное же вычисление функции φ(x) потре-

бует порядка N log2 N = n2n операций.

Перейдем теперь к квантовому преобразованию Фурье (КПФ). Этому преобразованию отвечает унитарный оператор, который

действует на базисные векторы x состояний n-кубитового регистра по закону:

КПФ			1	N −1			xy
x →		Ψ =		∑exp		2πi			y . (3.66)
			N y=0				N

Эта формула является квантовым аналогом выражения (3.60) в том смысле, что вместо вектор-столбцов φ(x) и f (y) стоят кэт-

векторы Ψ и y . Унитарность преобразования (3.66) совпадает с условием унитарности матрицы коэффициентов в разложении

253

(3.66), а она имеет тот же самый вид, что и матрица Fxy (3.61). Зная

результат (3.66) преобразования для базисных векторов и используя свойство линейности оператора, не представляет труда написать КПФ для произвольного состояния.

Займемся преобразованием выражения (3.66) к виду, из которого легко понять, как построить квантовую схему, реализующую КПФ. В выражении (3.66) числа x и y считаем записанными в виде n-разрядных двоичных строк. Стоящая в показателе экспоненты

величина xy

2n описывается формулой (3.63). Поскольку каждый

базисный

кэт-вектор

y

имеет

вид

yn−1 …y1 y0

=

yn−1

yn−2

y1

y0

, суммирование по y сводится

к суммированию по двум значениям

yk

= 0,1 для каждого одноку-

битового состояния

yk

вместе

с фазовым множителем

exp 2πiyk (ixn−k −1 …x1x0 ) . Тогда цепочка преобразований выгля-

дит следующим образом:

n−1

Ψ = 2−n 2 ∑exp 2πi∑yk (ixn−k −1

x0 )

yn−1 yn−2 …y0 =

y

k =0

∑

exp

2πiy − (ix

)

y

= 2−n 2

−

×

n 1

0

n

1

yn−1 =0,1

(3.67)

∑

exp

2πiy

(ix x

)

y

×

−

−

n

2

1 0

n

2

yn−2 =0,1

∑

exp 2πiy

(ix −

x

)

y

=

0

n 1

0

0

y0 =0,1

= 2−n 2 (

0 + e2πi(ix0 )

1 )(

0 + e2πi(ix1x0 )

1 )

(

0 + e2πi(ixn−1

x0 )

1 ).

Получившееся состояние (3.67) имеет факторизованный вид.

254

Состояние каждого кубита является суперпозицией базисных состояний 0 и 1 , а коэффициент при 1 представляет собой

некоторый фазовый множитель. Можно сказать, что каждый кубит подвергается преобразованию сдвига фазы. При этом фазовые сдвиги зависят от значений двоичных дробей, которые определяются двоичными знаками числа x. Каждая такая дробь представляет сумму типа (3.64), так что результирующая фаза определяется не только значением данного кубита, но аддитивно зависит от других кубитов. Поэтому такие фазовые преобразования можно осуществить с помощью однокубитовых гейтов, а также двухкубитовых гейтов, которые описывают управляемые фазовые преобразования.

Напомним, что расположение однокубитовых кэт-векторов в тензорном произведении (3.67) соответствует убыванию двоичных разрядов слева направо. Количество же разрядов двоичных дробей, стоящих в фазах, напротив, возрастает слева направо. Поменяем местами кубиты – первый и последний, второй и предпоследний и т.д. Если число кубитов четное, то все обмены будут парными. При нечетном числе кубитов положение среднего кубита остается неизменным. Каждая перестановка представляет собой унитарное преобразование, которое реализуется с помощью трех гейтов CNOT (см. задачу 3 в конце раздела 2.5). Сделав такое преобразование состояния (3.67), получим

2−n 2(				0 + e2πi(ixn −1 x0 )				1 )(		0 + e2πi(ixn−2 x0 )		1 )
(		0 +e2πi(ix0 )				1 ).							(3.68)

Теперь двоичные разряды кубитов и число разрядов в двоичных дробях, стоящих в фазах, упорядочены одинаковым образом – они убывают слева направо, что существенно упрощает понимание структуры квантовой схемы.

Каждая круглая скобка в (3.68) отвечает определенному двоичному разряду. Этот же разряд имеет первый знак в двоичной дроби, которая входит в фазовый множитель. Поэтому вклад в фазу первого слагаемого двоичной дроби зависит от значения данного бита

255

и определяется однокубитовым оператором Адамара. Действительно, если подействовать этим оператором на кубит xk , соответствующий k-му разряду, то получим

H		xk	=	1	(		0	+(−1)xk		1 )=	1	(		0	+e2 π i(ixk )		1 ), (3.69)
				2							2

так как

(−1)xk = exp(iπxk )= exp 2πi xk ≡ exp 2πi (ixk ) .

2

Вклады в фазу других слагаемых двоичной дроби зависят от значений битов в предшествующих разрядах. Они описываются двухкубитовыми операциями управляемых фазовых сдвигов:

Controlled Pd =		0 j j 0		I k +		1 j j 1		Pd .	(3.70)

Управляющий кубит имеет индекс j, а управляемый кубит – индекс k, отвечающий более высокому разряду, чем j.

Однокубитовый унитарный оператор

Pd ≡ P (π 2d )=		0 k k 0		+ exp(iπ 2d )		1 k k 1		(3.71)

фазового сдвига π2d действует на k-й кубит. Величина фазового сдвига зависит от «расстояния» d = k − j между кубитами.

Чтобы получить, например, кэт-вектор, стоящий в первой круглой скобке выражения (3.68), надо на исходное состояние

xn−1

xn−2

x0

подействовать сначала оператором H на первый кубит, а потом применить последовательно операторы управляемых фазовых сдвигов на двухкубитовые состояния

xn−1 xn−2 , xn−1 xn−3,…, xn−1 x0 .

256

Тогда цепочка преобразований выглядит следующим образом:

												Hn−1		1			(										2πi(ixn−1 )					1 )
xn−1	xn−2								x0 →						2				0 + e																	xn−2	x0 →
CP1		1	(							+ e		2πi(ixn−1xn−2 )				1 )					xn−2							xn−3						x0
→		2				0																														→
				(															1 )
CP2		1								+ e		2πi(ixn−1xn −2 xn−3 )												xn−2						x0 →
→		2					0
			1							(			2πi(ixn−1				x0 )						)
CPn/ −1												+ e														xn−2							x0 .
→											0											1
			2

После завершения этой процедуры с первым кубитом аналогичные преобразования производятся со вторым кубитом, третьим и т.д. В результате получается состояние (3.68). Заключительным преобразованием надо вернуть переставленные кубиты на исходные места. Это делается с помощью того же самого преобразования обмена. На рис. 3.9 представлена квантовая схема, реализующая КПФ на трех кубитах.

x2 H P1	P2
x1	H	P1	Ψ
x
		H
0

Рис. 3.9

Последний элемент справа представляет преобразование обмена первого и третьего кубитов.

Оценим число операций, реализующих КПФ. Число однокубитовых операций H равно числу кубитов n. Число двухкубитовых

257

операций Controlled Pd определяется числом пар среди n кубитов,

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

кубитовых операций есть Cn2 = n (n −1)2 . Эта величина определяет характер роста требуемого ресурса, который ведет себя полиномиальным образом как n2 = (log2 N )2 .

Таким образом, КПФ дает очень сильное – экспоненциальное – ускорение вычислительной процедуры по сравнению с классическим быстрым преобразованием Фурье, которое, напомним, требу-

ет порядка N log2 N операций. Отметим, что число операций для КПФ можно уменьшить до линейной зависимости от n = log2 N ,

если есть возможность снизить точность. Дело в том, что двухкубитовые гейты Controlled Pd начинают давать экспоненциально

малый вклад в фазовый сдвиг π2d , если «расстояние» d между

управляющим и управляемым кубитами велико. Если опустить гейты, которые действуют на кубиты, разнесенные друг от друга более чем на m позиций, то каждое длинное слагаемое в (3.63) за-

меняется m-битовым приближением. Полная погрешность в xy2n заведомо не больше чем n2m . Поэтому, если выбрать m ≥ log nε, то погрешность в величине xy2n будет меньше ε.

Итак, если сохранить только гейты, которые действуют на кубиты, разнесенные на m и менее позиций, то их число nm будет порядка n log nε, а не n2 .

Квантовая схема, реализующая КПФ, была разработана Д. Копперсмитом в 1994 г. Заметим также, что преобразование Адамара принадлежит к некоторому классу квантовых преобразований Фурье.

Квантовый алгоритм поиска периода последовательности и задача факторизации

Задача факторизации может быть сведена к другой трудной проблеме – отысканию периода длинной последовательности. Пре-

258

имущества собственно квантовой составляющей алгоритма Шора как раз и проявляются при решении этой последней задачи.

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

f (a) = xa (mod M ), a = 0,1,2,…

(3.72)

Можно убедиться, что эта последовательность

f (a) =1, x,…, xr−1,1, x,…

(3.73)

является периодической функцией a с периодом r, где r ≠ 0 есть минимальная степень, для которой

xr =1(mod M ).

(3.74)

Такое число r называется порядком числа x по модулю M. Предположим, что с помощью какого-то алгоритма будет най-

ден период r. Пусть этот период четный. Если r оказалось нечетным, то надо изменить x и повторить вычисления. Запишем соотношение (3.74) в виде

xr −1 =	(	)(	)	= 0(mod M ). (3.75)
		xr 2 +1	xr 2 −1

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

259

Проиллюстрируем указанное свойство задачи факторизации на простом примере разложения на сомножители числа 21. В качестве x выберем число 5, взаимно простое с 21. Подсчитав вручную последовательность (3.72), получаем следующую таблицу:

A	0	1	2	3	4	5	6	7	8	9	10	…
5a (mod21)	1	5	4	20	16	17	1	5	4	20	16	…

Из этой таблицы видно, что 56 ≡1(mod 21), т.е. период r в данном случае равен 6. Записывая далее соотношение (3.75), получаем

(53 )2 −1 = (53 −1)(53 +1)=124.126 = 0(mod 21).

Осталось установить, что у числа 124 или 126 есть общий множитель с числом 21. Воспользовавшись алгоритмом Евклида, находим, что число 124 является взаимно простым с 21, а число 126 вместе с 21 делится на 3 и 7. Таким образом, разложение на множители имеет вид 21 = 3×7 .

Теперь рассмотрим квантовый алгоритм поиска периода длинной последовательности f (a), a = 0,1,…,2n −1. Систему кубитов, каждый из которых первоначально находится в состоянии 0 , образуют два квантовых регистра 0;0 ≡ 00…0;00…0 . О них

можно говорить как о двух наборах квантовых переменных. В первом регистре n кубитов, с помощью которых записываются числа a. Второй регистр должен содержать число кубитов, достаточное для последующих вычислений. Применяя преобразование Адамара к каждому из кубитов первого регистра, получаем состояние

s−1
s−1 2 ∑ a;0 , s = 2n ,	(3.76)

a=0

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

Далее используется некоторая последовательность элементар-

260