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

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

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

вычисление, превращает каждое состояние a;0 в состояние a; f (a) . Примененная к суперпозиционному состоянию (3.76), эта операция дает состояние

s−1

s−12 ∑ a; f (a) . (3.77)

a=0

Мы вновь видим, как работает квантовый параллелизм, позволяющий за один шаг вычислить функцию f (a) для экспоненци-

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

Следующая ключевая операция состоит в применении квантового преобразования Фурье (КПФ) (3.66) к переменным первого набора. Для каждого члена суммы (3.77) это преобразование имеет вид

	−1 2	s−1		2πa
a; f (a) → s		∑exp i			c		c; f (a)	. (3.78)
				s
		c=0

Тогда для суперпозиционного состояния (3.77) КПФ приводит к следующему состоянию системы на выходе:

	−1	s−1	s−1		2πa
s		∑∑exp i				c	c; f (a) .	(3.79)
					s
		c=0	a=0

На этом процесс квантового вычисления заканчивается.

261

Измерим состояние всех n кубитов первого регистра в вычислительном базисе 0 и 1 . Такое измерение дает случайным обра-

зом какую-то строку c;… , представленную в состоянии (3.79). Пусть вероятность этого результата есть W (c) . Ключевым моментом является именно квантовое распределение вероятности получения того или иного результата. Если функция f (a) имеет пери-

од r, то сумма по a в формуле (3.79) приводит к конструктивной интерференции большого числа коэффициентов в том случае, ко-

гда входящая в фазу величина cs кратна обратному периоду 1r , т.е. cs = pr , где p – целое число. Действительно, в этом случае

	2πac			p			a = r, 2r,3r,…. Для всех
exp i			= exp i2πa			=1 для
	s			r

других значений числа cs , т.е. не кратных 1r , будет иметь место, в большей или меньшей степени, деструктивная интерференция. Это означает, что распределение вероятности W (c) найти

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

	c = p	s	= 0, s r , 2s r ,…,	(3.80)
		r

как это изображено на рис. 3.10.

Один описанный выше цикл работы с одним актом измерения дает случайное число c = psr , кратное обратному периоду 1r . Если p и r взаимно простые, то период r получается, если привести cs к несократимой дроби. Для реализации такой благоприятной ситуации процедуру вычисления надо повторить несколько раз,

порядка log2 log2 r < log2 log2 M log2 n . Как уже	отмечалось,
квантовое преобразование Фурье требует порядка n2	операций, а с

учетом вычисления функции f (a) , полная сеть гейтов, необходи-

мых для реализации алгоритма Шора, содержит порядка 300n3 логических элементов.

262

Рис. 3.10

Таким образом, успешное решение задачи факторизации боль-

шого числа M 2n может быть реализовано за полиномиальное число шагов с вероятностью, сколь угодно близкой к единице.

Задачи

1. Пусть c=pq, где p и q – простые числа, φ(c) = ( p −1)(q −1) , а число t взаимно простое с φ(c) . Пусть далее Tt=M(mod c). Доказать, что имеет месторавенство Mm(modc)=T, если mt =1(mod φ(c) ).

Доказательство

Сначала покажем, что φ(c) есть функция Эйлера, которая оп-

ределяется как число положительных целых чисел, меньших с и взаимно простых с с. Действительно, с = pq, где p и q – простые числа. Поэтому делителями с являются все числа, кратные р, т.е. р, 2р, …, p(q–1), а также все числа, кратные q, т.е. q, 2q, …, q(p–1).

Таким образом, число делителей с есть q–1+p–1=q+p–2. Остальные числа, которых pq–1– (q+p–2) = (p–1)(q–1) ≡ φ(c) штук, будут

263

взаимно простые с с. Итак, ϕ(c) есть функция Эйлера. Так как Tt=M(mod c), то интересующая нас величина имеет вид

Mm(mod c)= Tmt(mod c).

Из соотношений mt =1(modϕ(c) ) следует, что mt =1+kϕ(c) , где k — целое число. Тогда

Tmt(mod c) = T1+kϕ(c) (mod c) = T(Tϕ(c) )k (mod c) .

Рассмотрим случай, когда T и с взаимно простые, т.е. Т не де-

лится на с. Поэтому надо вычислить величину Tϕ(c) (mod c). Для этого применим теорему Эйлера, которая гласит, что если Т и с

взаимно простые, то Tϕ(c) =1(mod c), где ϕ(c) – функция Эйлера.

Очевидно, что (Tϕ(c) )k=1(mod c). Таким образом, окончательно соотношение имеет вид Mm(mod c)=Т, что требовалось доказать.

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

2. Доказать, что матрица дискретного преобразования Фурье

F	=	1	exp(2πi xy ) ,
xy		N	N

где x, y – целые неотрицательные числа, пробегающие значения от 0 до N–1, является унитарной.

Доказательство

Эрмитово сопряженная матрица имеет вид

	ˆ +	*	*		1		xy
	(F	)xy = Fyx	= Fxy	=		exp(−2πi	N	) .
					N

Тогда для матричных элементов произведения матриц ˆ ˆ +

F F

264

получаем

1

x − y

ˆ

ˆ +

N −1

ˆ

ˆ *

N −1

(F

F

)xy = ∑

Fxz

Fzy = ∑

exp(2πi

z) =

N

N

z=0

z=0

=

1

1−exp(2πi(x − y))

=δxy .

N 1−exp(2πi

(x − y)

)

N

Действительно,

если x ≠ y,

то 1 ≤

x − y

≤ N −1 . Поэтому числи-

тель равен нулю, а знаменатель отличен от нуля. Следовательно, матричные элементы при x ≠ y обращаются в нуль. Если х = у, то

такие матричные элементы равны единице. Итак, имеем ˆ ˆ + =1,

F F

т.е. матрица ˆ является унитарной.

F

3.4.Корреляции ЭПР–Белла

вквантовых коммуникационных схемах

Корреляции ЭПР – Белла

Рассмотрим корреляционные свойства перепутанных состояний двух квантовых систем. В историческом плане побудительной мотивацией тщательного анализа этих свойств послужил парадоксальный мысленный эксперимент, предложенный в 1935 г. Эйнштейном – Подольским – Розеном (ЭПР). В нем шла речь о системе двух частиц, которые находятся в состоянии, перепутанном по пространственным степеням свободы. При этом ни координата, ни импульс каждой частицы не определены, но координата центра инерции и разность импульсов, которым отвечают коммутирующие операторы, имеют определенные значения. Поэтому, измерив координату, например, второй частицы, мы достоверно можем предсказать координату первой. То же самое относится и к импульсам – измерение импульса одной частицы позволяет однозначно предсказать импульс другой частицы. Эти утверждения находятся в полном соответствии с квантово-механическим описанием перепутанных состояний. Свой вывод о том, что квантовые состояния в общем случае не могут быть полным описанием физи-

265

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

В оригинальной работе ЭПР речь шла о перепутывании состояний поступательного движения, достаточно трудных для тонких корреляционных измерений. В 1951 г. Дэвид Бом предложил рассматривать системы, перепутанные по спиновым состояниям двух частиц со спином 1/2. Эти системы существенно проще, а аргументация ЭПР легко переносится на спиновые состояния. Измеряя проекцию спина одной из частиц, можно с достоверностью предсказать значение проекции спина другой частицы, которая находится от нее достаточно далеко, так что взаимодействие отсутствует. Тогда указанная проекция является элементом реальности. Такое же утверждение справедливо и в отношении проекций на другие оси, что противоречит квантовой механике, так как состояний

266

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

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

иисходя из классических представлений, опирающихся на “локальный реализм”. Существует много различных модификаций неравенств Белла. Мы рассмотрим одну из них, которая была предложена в 1969 г. Д. Клаузером, М. Хорном, А. Шимони и Р.

Хольтом и лежит в основе многочисленных экспериментальных проверок.

Пусть имеется некоторый источник, генерирующий пары частиц, находящихся в том или ином состоянии. Одна из частиц попадет к Алисе, а другая – к Бобу. Каждый из них производит над своей частицей измерения некоторых физических характеристик, например, проекций спина на какие-то оси. Алиса случайным образом производит измерения, которые мы назовем F и G. Результа-

том измерения каждой из этих величин пусть будут числа ±1. Подчеркнем, что в рамках классических представлений каждый из этих результатов есть элемент реальности, характеризующий данную частицу. Аналогично, Боб случайным образом производит какие-то другие измерения, J и K, результатом которых тоже могут быть числа ±1. Считаем, что события измерения являются абсолютно удаленными и не могут влиять друг на друга.

Результаты измерений, которые мы будем обозначать теми же буквами – F и G у Алисы, J и K у Боба, зависят от исходного состояния пары частиц, но не зависят от процесса измерения. При многократном повторении процедуры можно говорить о вероятности W(F, G, J, K) того, что перед измерением система находилась в состоянии с указанными значениями величин F, G, J и K, которые потом были обнаружены в результате измерений. Рассмотрим теперь величину

FJ + GJ + GK − FK = (F + G)J + (G − F)K , (3.81)

267

которая характеризует корреляционные свойства результатов измерений. Так как F, G, J и K принимают значения, равные ±1, то

|FJ +GJ +GK − FK |= 2 .

(3.82)

Поэтому для среднего значения величины (3.81) получаем

< FJ + GJ + GK − FK > = < FJ > + < GJ > + < GK > − < FK > =

= ∑ W (F,G, J, K )(FJ + GJ + GK − FK) ≤

F ,G,J ,K

≤ ∑ W (F,G, J, K) FJ + GJ + GK − FK = 2∑W = 2.

F ,G,J ,K

Таким образом, имеем следующее обобщенное неравенство Белла (его называют неравенством КХШХ):

< FJ > + < GJ > + < GK > − < FK > ≤ 2 , (3.83)

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

В качестве квантового объекта будем рассматривать ЭПР-пару, т.е. двухкубитовую систему, находящуюся в максимально перепутанном состоянии, полный набор которых записывается в виде четырех состояний Белла (2.162)–(2.163):

	Φ(±)	=	1		(			00 ±						11 ),
			2
					(3.84)
	Ψ(±)	=		1		(				01 ±			10 ).
				2

Пусть квантовая система находится в состоянии Ψ(−) , а Алиса и Боб получают по одному кубиту этой ЭПР-пары.

268

Измерениям F и G, которые выполняет Алиса, отвечают эрмитовые операторы

ˆ	(1)	,	ˆ	(1)	,	(3.85)
F =σ	3		G =σ1

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

	ˆ		1	(2)		(2)		ˆ	1		(2)	(2)
	J	= −		(σ1	+σ	3	),	K =		(σ	3	−σ1	),	(3.86)
			2						2

действующие на второй кубит. Поскольку квадраты всех операторов, указанных в (3.85) и (3.86), равны единице, то собственные значения этих операторов равны ±1. Вычисляя квантово-

механические средние значения в состоянии Ψ(−) тех же величин, что стоят слева в (3.83), получаем:

ˆ ˆ

(−)

(1)

σ1(2)

+σ3(2)

(−)

1

FJ

= Ψ

−

σ3

Ψ

=

,

2

2

ˆ ˆ

(−)

(1)

σ1(2)

+σ3(2)

(−)

1

GJ

= Ψ

−

σ1

Ψ

=

,

2

2

ˆ ˆ

(−)

(1)

σ3(2)

−σ1(2)

(−)

1

GK

= Ψ

σ1

Ψ

=

,

2

2

ˆ ˆ

(−)

(1)

σ3(2)

−σ1(2)

(−)

1

FK

= Ψ

σ

3

Ψ

= −

.

2

2

Тогда комбинация квантово-механических средних

ˆ ˆ	ˆ ˆ	ˆ ˆ	ˆ ˆ	2 ,	(3.87)
FJ	+ GJ	+ GK	– FK = 2

характеризующая корреляционные свойства результатов измерений, заметно выходит за рамки классического неравенства (3.83).

269

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

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

Протокол квантовой плотной кодировки

Как уже неоднократно подчеркивалось, состояния Белла (3.84) являются максимально перепутанными состояниями двух кубитов.

Измерение состояния любого кубита в базисе 0 , 1 в каждом из

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

Поскольку проекция спина каждой из двух максимально перепутанных частиц на любую ось является совершенно случайной величиной, то квантовая информация, которую хранят два спиновых кубита, оказывается как бы спрятанной, если она закодирована

с помощью состояний вычислительного базиса 0 , 1 . Эту си-

туацию нельзя изменить путем перехода к любому другому базису однокубитовых состояний. Как было показано в разделе 2.4, перепутанное состояние нельзя факторизовать с помощью однокубитовых унитарных операций. Оно остается максимально перепутанным. Напомним, что в случае факторизованного двухкубитового состояния каждый кубит описывается некоторым кэт-вектором, т.е. спин частицы ориентирован вдоль какой-то оси. Измерение проекции спина на эту ось с достоверностью дает определенный резуль-

270