Юрий Кругляк_Квантовое моделирование в квантовой химии на квантовых компьютерах_399_стр

откуда | u00 | =| u11 | и | u01 | =| u10 |. Таким			образом, коэффициенты uij			можно
выразить через sine и cosine некоторого угла β :
Q =	eiθ00	cosβ	eiθ01 sin β
	−eiθ10	sin β	eiθ11 cosβ .
Более того, фазы не независимы: u00u10 +u01u11 = 0				означает,	что θ10 −θ00	=θ11 −θ01 .
Поскольку
K(δ)T (α)R(β)T		ei(δ+α+γ ) cosβ		ei(δ+α−γ ) sin β
	(γ) =				,
		−ei(δ−α+γ ) sin β		ei(δ−α−γ )	cosβ

мы можем для данного Q найти δ,α,γ , решив уравнения

δ +α +γ	=	θ00,
δ +α −γ	=	θ01,
δ −α +γ	=	θ10.

Воспользовавшись равенством θ11 =θ10 −θ00 +θ01 , убеждаемся также, что имеет место равенство δ −α −γ =θ11 .

5.5.2. Одиночно контролирующие преобразования одиночных кубитов

Пусть Q = K(δ)T (α)R(β)T (γ) будет произвольным однокубитным унитарным преобразованием. Контролирующий вентиль ΛQ (§ 5.3.3) может быть реализован посредством ΛK(δ) с последующим ΛQ′ для Q′=T (α)R(β)T (γ) , а именно: ΛQ = (ΛK(δ))(ΛQ′). Сейчас покажем, как реализовать эти два

преобразования посредством базисных вентилей.

Обусловленный фазовый сдвиг может быть реализован посредством простых однокубитных операций:

ΛK(δ) =|0 0 | I +|1 1| K(δ) =|0 0 | I +eiδ |1 1| I =(K(δ/2)T (−δ/2)) I

или в виде квантовой схемы

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

190

отсутствии прямых преобразований над вторым кубитом. Причиной достаточности преобразований над первым кубитом является то обстоятельство, что фазовый сдвиг влияет на квантовое состояние в целом, а не только на одиночный кубит. В частности, | x a | y = a | x | y .

Реализация ΛQ′ несколько более сложная. Определим для Q′=T (α)R(β)T (γ) следующие преобразования:

Q0	=	T (α)R(β/2),
Q	=	R(−β/2)T −γ −α			,
1				2
Q	=	T γ −α .
2			2

Квантовая схема ΛQ′ может быть определена как

ΛQ′=(I Q0)Cnot (I Q1)Cnot (I Q2 )

или графически

Эта схема выполняет следующее преобразование:

|0 | x →|0 Q0Q1 | x ,

|1 | x →|1 Q0 X Q1X Q2 | x .

Если учесть, что R(β)R(−β) = I и T (α)T (γ) =T (α +γ ) , равенство Q0 Q1 Q2 = I немедленно следует из определения Qi . С целью показать, что Q0 X Q1 X Q2 =Q′,

воспользуемся тем, что X R(β)X = R(−β) и X T (α)X =T (−α) . Тогда

Q0 X Q1X Q2	=T (α)R(β/2)(X R(−β/2)X )	X T (−	γ +α)X T		γ −α		=Q′.
			2		2

Мы можем таким образом реализовать произвольное однокубитное преобразование, контролируемое одиночным кубитом.

5.5.3. Множественно контролирующие преобразования одиночных кубитов

Графические образы контролирующих операций (§§ 5.3.3, 5.5.2) обобщаются на более чем один контролирующий кубит. Пусть ΛkQ будет

191

преобразование (k+1)-кубита, в результате которого Q применяется к кубиту 0,

когда кубиты от 1 до	k все имеют значение 1. Примером может служить
трехкубитный вентиль	Λ2 X Тоффоли CCnot (Controlled-Controlled-NOT),

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

Двойка в Λ2 X указывает, что есть два контролирующих кубита. В этом смысле вентиль Cnot иногда обозначают как Λ1 X или просто Λ X .

Конструкцию, описанную в предыдущем параграфе 5.5.2, можно обобщить на управление одиночным кубитом со стороны остальных k кубитов. Для реализации Λ2Q , трехкубитного вентиля, контролирующего третий кубит

первыми двумя, заменяют каждый из Q0 ,Q1,Q2 в предыдущей схеме, а именно:

Дальнейшее расширение можно продолжить вплоть до ΛkQ .

5.6. Стандартная модель квантовых схем

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

всеми однокубитными преобразованиями с последующими однокубитными измерениями в стандартном базисе. Известны иные модели квантовых схем

[2, 15].

192

Глава 6. Квантовый алгоритм вычисления фазы

6.1. Введение

Начнем с квантового преобразования Фурье/КПФ (Quantum Fourier Transformation /QFT), уникальной наиболее часто используемой квантовой процедуры. Именно КПФ используется во многих квантовых алгоритмах для достижения большей скорости выполнения вычислений по сравнению с классическими алгоритмами. КПФ берет свое начало еще в классическом дискретном преобразовании Фурье/ДПФ (Discrete Fourier Transformation/DFT) [16] и в его эффективной реализации, получившей название быстрого преобразования Фурье/БПФ (Fast Fourier Transformation/FFT) [17]. Мы сначала кратко обсудим классическое преобразование Фурье, а затем подробнее рассмотрим его квантовую реализацию [18, 19] и перейдем к обсуждению алгоритма вычисления фазы (АВФ), квантового алгоритма для нахождения собственного значения унитарного оператора U = eiH , где H – эрмитов оператор. АВФ есть квантовый аналог процедуры классической диагонализации в классической квантовой химии. В части III книги, посвященной квантовой химии на квантовых компьютерах, мы будем пользоваться АВФ и его различными вариантами.

6.2. Классическое преобразование Фурье

Сначала обратимся к стандартному ДПФ, которое в качестве входа требует дискретную комплексную функцию a : [0,1,..., N −1] , а на выходе дает функцию

A : [0,1,..., N −1],

1

N −1

A(x) =

∑a(k)exp 2πi kx

,

N k=0

N

и может

рассматриваться

как

линейное преобразование

вектора-столбца

(a(0),a(1),...,a(N −1))T в другой вектор-столбец (A(0), A(1),..., A(N −1))T

посредством

матрицы

с

элементами

F =

1

exp

2πi

kx .

Значения

A(0), A(1),..., A(N −1)

xk

N

N

называют коэффициентами Фурье функции a .

Пример

6.2.1.

Пусть

a : [0,1,..., N −1]

будет

периодической

функцией

−2πi

ux

некоторой частоты 0 < u < N . Фурье-коэффициентами этой

a(x) = exp

N

193

функции будут:

N −1

A(x) = 1 ∑a(k)

N k =0

kx

1

N −1

uk

kx

exp

2πi

=

∑

exp

−2πi

exp

2πi

=

N

N

N

N

k =0

1		N −1			k(x −u)
		∑	exp	2πi	N	.
	N
		k =0

Поскольку u < N , A(x) = 0 , если только не x −u = 0 : только A(u) будут ненулевые.

Любая периодическая комплексная функция a с периодом r и частотой u = N/ r аппроксимируется фурье-рядами в виде суммы экспоненциальных функций с частотами, кратными u . Поскольку преобразование Фурье линейное, коэффициенты Фурье A(x) любой периодической функции будут суммой коэффициентов Фурье ее компонентов. Если r делит N равномерно, фурье-коэффициенты A(x) будут ненулевые только для тех x , которые кратны

u = N / r .

Быстрое преобразование Фурье является эффективной реализацией ДПФ с

N = 2n . Ключевым моментом				успешной		реализации		БПФ	является то
обстоятельство,		что F(n) может быть			рекурсивно декомпозирована через
фурье-преобразования более низких степеней двойки.
Пусть ω(n)		будет	N -ым	корнем	единицы,		ω(n) = exp(2πi /N ) . Элементы
N × N матрицы F(n) для N = 2n -размерного преобразования Фурье
				F(n) =ωij		,
				ij	(n)
где индексы матрицы F(n) принимают значения i {0,1,..., N −1} и									j {0,1,..., N −1}.
Пусть F(k )	будет матрицей 2k ×2k			2k -размерного преобразования Фурье.
Пусть	I (k )	будет	единичной матрицей 2k				×2k , а	D(k ) –	диагональной

матрицей той же размерности с элементами ω(0k +1) ,ω(1k +1) ,...,ω(2kk+−1)1 . Пусть R(k ) будет перестановкой (рис. 13) вектора с номером 2i в положение i , а с номером 2i +1 в положение i +2k −1 .

Рис. 13. Пример тасующего преобразования R .

194

Элементами 2k ×2k матрицы R(k ) будут

	1,		если2i = j,
R(k ) = 1,			если2(i – k 2 )+1j
ij		0	впротивномслучае.

Можно убедиться, что

F(k ) =	1		I
	2		I

(k−1)	D(k−1) F(k−1)					0
(k−1)		(k−1)				(k−1)	R(k ) ,
	−D			0	F

а также в том, что реализация этой рекурсивной декомпозиции требует только O (n N ) шагов.

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

Квантовое преобразование Фурье, как и БПФ, предполагает, что N = 2n . Амплитуды ax квантового состояния ∑x ax | x рассматриваются как функции x

и обозначим их как a(x) . КПФ реализует следующее преобразование квантового состояния:

∑x a(x) | x →∑x A(x) | x ,

где A(x) – коэффициенты Фурье дискретного преобразования Фурье a(x) с x {0,1,..., N −1}. Если сразу после преобразования Фурье состояние измеряется в стандартном базисе, то вероятность, что результирующим окажется состояние | x , будет равна |A(x)|2 . КПФ реализуется экспоненциально быстрее по сравнению с БПФ, требуя только O (n2 ) шагов, а не O (n N ) .

6.4. Квантовая схема для быстрого преобразования Фурье

Мы ниже покажем как эффективно реализовать КПФ UF(n) для N = 2n :

	1			N −1		2πi kx
UF(n) :|k →				∑exp			| x .
		N
				x=0		N

Для N = 2 это известное преобразование Адамара:

UF(1) : |0 →		1			1			e0	| x =		1					(|0 +|1 ),
											2
				2 ∑x=0
		1			1			πix			1
|1 →						∑x=0 e				| x =						(|0 −|1 ).
			2										2
								195

Используя рекурсивную декомпозицию из § 6.2

	UF(k+1) =	1			I
		2
					I

(k )	D(k ) U (k )			0		,
			F	UF(k )	R(k+1)
(k )	−D(k )		0

вычисляем UF(n) . Все, входящие в рекурсию матрицы, унитарны; численный

коэффициент идет с первой матрицей. Остается показать, каким образом эту процедуру можно эффективно реализовать на квантовом компьютере.

Поступаем следующим образом.

1. Вращение R(k +1) записываем как

R(k+1) =∑i2=k0−1(|i 2i | +|i +2k 2i +1|) ,

что достигается простой перестановкой k +1 кубитов: кубит 0 становится кубитом k, а кубиты от 1 вплоть до k становятся кубитами от 0 до k –1. Эти перестановки могут быть реализованы с помощью обменных операций (§ 5.3.3).

2. Трансформация

U (k )		0		= I UF(k )
	F	UF(k )
	0

может быть реализована путем рекурсивного применения КПФ к кубитам от 0 до k.

3. Для k ≥1 диагональная 2k ×2k матрица фазовых сдвигов D(k ) может быть рекурсивно декомпозирована следующим образом:

D(k ) = D(k−1)		1	0
		0		.
			ω(k+1)

Рекурсивно декомпозируя D(k ) таким образом, преобразование D(k ) может быть

реализовано путем применения		1	0		к кубиту i (1 ≤ i ≤ k) . Таким образом,
		0	ω
			(k +1)
в конечном итоге D(k −1) может			быть		реализовано с использованием k
однокубитных вентилей.

	1			(k )	D	(k )
4. Теперь			I
					−D(k )
	2		I (k )

вентилей:

	можно реализовать с использованием лишь k

1 I 2 I

(k )	D(k )		=	1		(|0 +|1 ) 0| I (k ) +	1		(|0 −|1 ) 1| D(k ) =
(k )	−D(k )			2			2

=(H |0 0|) I (k ) +(H |1 1|) D(k ) =(H I (k ) )(|0 0| I (k ) +|1 1|) D(k ) ).

196

Преобразование (| 0 0 | I (k ) + |1 1|) D(k ) ) применяет D(k ) к кубитам низкого порядка, контролируемым кубитом высокого порядка.

Поскольку оба преобразования D(k ) и R(k ) могут быть реализованы посредством O (k) операций, k -шаг в рекурсии добавляет O (k) шагов в имплементации UF(n) . Всего UF(n) для реализации требует O (n2 ) вентилей, что экспоненциально быстрее по сравнению с O (n2n ) шагами в случае классического БПФ. Схема такой реализации КПФ показана на рис. 14.

Рис. 14. Рекурсивная квантовая схема квантового преобразования Фурье.

Итак, при действии оператора КПФ на кубит имеем:

			1		N −1		kj
	UQFT|k =				∑exp 2πi			| j , N =2n,
							N
			N
					j=0
	| j =| jn jn−1... j1 ,					ji {0,1},		j =∑in=1 ji 2i−1.
	Можно показать, что оператор UQFT					унитарный [15].

В дополнение к описанным выше четырем шагам, ведущим к квантовой схеме на рис. 14, приведем также квантовую схему (рис. 15), реализующую КПФ посредством вентилей Адамара H (§ 5.3.2) и

R			1		0		,
	j	=			2πi/2	j
			0	e

доказательство которой можно найти в [15]. Эта схема нашла применение в квантово-химических расчетах [20].

Рис. 15. Схема квантового преобразования Фурье на вентилях H и Rj ; обратите внимание на обратный порядок результирующих кубитов qi после выполнения этой схемы.

197

Несмотря на то, что КПФ экспоненциально быстрее чем БПФ, им все же нельзя напрямую заменить собственно преобразование Фурье. Требуется подготовить n кубитов, а также в конце концов измерить их амплитуды, что эффективно выполнить непросто. Тем не менее, КПФ является ключевым блоком рассматриваемого ниже алгоритма вычисления фазы (АВФ/PEA, Phase Estimation Algorithm) [15, 19, 21].

6.5. Квазиклассический подход к квантовому преобразованию Фурье

Квантовую схему КПФ на рис. 15 можно существенно упростить [22]. Обратим внимание, что вентили, действующие на каждый кубит, кроме первого и последнего, однотипны. Сначала действуют вентили Rj , контролируемые

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

соответствующие однокубитные вентили в зависимости от результатов индивидуальных измерений. Более того, все вентили Rj , действующие на k-ый

кубит, можно объединить в единственный вращательный вентиль

R			1		0		,
	(ω ) =
z	k		0	e	2πiωk

угол ωk которого зависит от результатов до этого измеренных кубитов qi в соответствии с формулой

n−k+1 q

ωk = ∑ k+ii−1. k : n →1 i=2 2

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

Рис. 16. Упрощенная, основанная на измерении, схема для k-го кубита КПФ.

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

198

алгоритму вычисления фазы и он позволяет сформулировать итерационную версию АВФ (ИАВФ/Iterative Phase Esmation Algorithm, IPEA).

6.6. Квантовый алгоритм вычисления фазы

Алгоритм вычисления фазы (АВФ) – это квантовый алгоритм для нахождения собственного значения унитарного оператора U , предполагающий задание пробного собственного вектора [15]. Поскольку унитарный оператор U = eiH , где H – эрмитов оператор, АВФ есть квантовый аналог процедуры классической диагонализации.

Пусть | u есть собственный вектор оператора U ,

U |u =e2πiφ |u , φ 0,1)

где φ – значение фазы, определяемое в результате выполнения алгоритма. Квантовый регистр состоит из двух частей. Первая часть – результативная, состоит из m кубитов, измеренных в конце и порождающих состояние | 0 m . Вторая часть содержит соответствующий собственный вектор | u .

Квантовая схема АВФ показана на рис. 17.

Рис. 17. Квантовая схема алгоритма вычисления фазы с выделенным блоком обратного КПФ QFT† .

Применение вентилей Адамара ко всем кубитам первой части регистра

дает

				m
|reg =		1		2∑−1| j |u .
		m
		2		j=0

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

		1		2m −1		1		2m −1
|reg =				∑U j| j |u =				∑e2πijφ | j |u .
		m				m
		2		j=0		2		j=0
			199