Файл: sem7.doc

Семинар 7. Квантовые вычисления

7.1 Введение

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

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

Вторая причина, которая стимулирует исследования в области квантовых компьютеров

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

Для задачи факторизации входными данными является число N, которое необходимо разложить на множители. Поэтому "длина" входных данных на классическом "двоичном" компьютере есть log₂ N. Основание 2 логарифма связано с использованием двоичной системы исчисления. Известно, что лучшие алгоритмы факторизации выполняются за число шагов, k, которое имеет следующий порядок ¹

k=Constexp(64/9)^1/3(lnN)^1/3(lnlnN)^2/3. (7.1)

·

То есть алгоритм вычислений приводит к экспоненциальному росту числа шагов по мере роста числа входных данных. Так в 1994 году 129-значное число было факторизовано на 1600 рабочих станциях, распределенных по всему миру ².Времяфакторизациисоставило8месяцев.ИспользуярезультатыэтогоэкспериментаможнокачественнооценитьпорядоквеличиныConstв (7.1). Оценка числа времени, которое потребуется для факторизации 250-значного числа на тех же 1600 рабочих станциях дает _∼ 10⁶ лет (миллион лет!). Соответственно для факторизации 1000-значного числа потребуется 10²⁵ лет, что на 11 ₋ 12 порядков больше (триллион лет) возраста вселенной, который оценивается в 10¹² ₋ 10¹³ лет.

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

¹A.M.Odiyzko.AT&TBellLaboratories,preprint1995.²S.L.Branstein.EncyclopediaofAppliedPhysics,Update,WILEY-VCH,1999.

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

7.2 Логические однокубитовые гейты

Классическиекомпьютерныецеписостоятизпроводовинаборалогическихгейтов(совокупноститранзисторов).Проводаслужатдляпередачистандартныхнапряженийпоэлектрическимцепям,алогическиегейтыосуществляютпреобразование"проходящей"черезнихинформации.Приэтомединственнымнетривиальнымлогическимгейтом,которыйпреобразует1битклассическойинформацииявляетсяNOT-гейт,действиекоторогосводитсякпреобразованиямбитоввида:01и10.

→→

Одиночный кубит, по определению, является суперпозицией двух квантовых состояний _|0_� и _|1_�, каждое из которых может рассматриваться как носитель одного бита классической информации

_|ψ_� = a _|0_� + b _|1_� . (7.2)

										В соответствии с определением классического NOT-гейта, квантовый NOT-гейт (т.е. гейт преобразующий информацию внутри кубита) может быть определен по аналогии:

NOT :

|ψ�→NOT:(a|0�+b|1�)→a|1�+b|0�.

(7.3)

На основании теории соответствует столбец

представлений,

квантовому

состоянию

кубита

|ψ�

(7.2)

� �

|ψ�→

a b

.

(7.4)

Поэтому квантовым аналогом классического NOT-гейта является матрица вида:

01 ab

x _{≡ 10} , x_b = _a, (7.5)

котораясовпадаетсматрицейПаулиσxвsz-представлении.

В соответствии с (7.4) квантовые гейты, преобразующие однокубитовое состояние являются унитарными матрицами размерности 2 _× 2. В отличие от классических систем, для кубита можно построить неограниченное число гейтов. Однако, в силу полноты системы матриц Паули и единичной матрицы I, любая 2 _× 2 матрица может быть разложена по этой полной системе матриц. Поэтому для практического использования представляют интерес сами матрицы Паули X _≡ σx,Y_≡ σy,Z_≡ σz и некоторые их специальные комбинации, среди которых выделим следующие три:

111 10 10

H _{≡√21 −1}; S _{≡ 0 i} ; T _{≡ 0 eiπ/4} . (7.6)

Матрицы (7.6) определяютсоответственноH–гейтАдамара,S–фазовыйгейт,аTназываетсяπ/8-гейт.Изопределенияперечисленныхгейтовследует,что:

11

H = _√2(σx+σz)_≡√2(X+Z);S=T² . (7.7)

					НазваниеT-гейта(π/8-гейт)определяетсяисторическимипричинамиивозможностьюпредставленияматрицыэтогогейтасточностьюдообщегофазовогомножителяexp(iπ/8)

в виде:

�

�

T≡exp(iπ/8)

exp(−iπ/8)0

0exp(iπ/8)

(7.8)

Гейт Адамара является одним из наиболее полезных квантовых гейтов. Этот гейт иногда определяют как "квадратный корень от NOTгейт. Это связано с тем, что данный гейт преобразует a _|0_�-часть кубита в (_|0_�+_|1_�)/√2–"половинапути"между_|0_� и _|1_� состояниями в геометрической интерпретации кубита на сфере Блоха. Соответственно в _|1_�-части кубита преобразуется гейтом Адамара в комбинацию (_|0_{�− |}1_�)/√2,чтотакже"половинапути"между_|0_� и _|1_�. Однако H²-гейт не приводит к NOT-гейту, так как алгебраические вычисления дают H² _≡ I. То есть двухкратное применение гейта H возвращает систему в исходное положение.

Графическое обозначение однокубитовых гейтов представляют в виде:

a _|0_� + b _|1_�

X

b _|0_� + a _|1_�

a

Y

|⁰� ^{+ b} |¹�

− ⁱ{^b |⁰�− ^a |¹�} a _|0_� + b _|1_� Z

^a |⁰�− ^b |¹� a _|0_� + b _|1_� H

a |⁰� ⁺ |¹� + b |⁰�− |¹� (7.9)

√2 √2

a

S

a _|0_� + ib _|1_�

|⁰� ^{+ b} |¹� a _|0_� + b _|1_�

T

a _|0_� + e^iπ/4b _|1_� =iπ/8_{e−iπ/8iπ/8_b

= ea

|⁰� ^{+ e}|¹�}

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

U=exp(iα)R�n(θ),(7.10)

гдеR�n(θ)–операторповоротанауголθвокругоси,определеннойединичнымвектором�n,αиθ–действительныечисла.

Используя вид оператора поворота можно установить, что T _≡ Rz(π/4),агейтАдамарасточностьюдоглобальногофазовогомножителя,являетсяпроизведениемоператоровповоротаRxиRz.СучетомусловияантикоммутацииматрицПаулиσxσy=₋σyσxможноустановить,что

XRy(θ)X=Ry(₋θ).(7.11)

62

В алгебре матриц Паули доказывается теорема, которая называется теоремой X ₋ Y разложения для однокубитового гейта (или оператора). Содержание теоремы утверждает, что существуют действительные числа α, β, γ, δ такие, что унитарный оператор U может быть представлен в виде:

U = e ^iαRz(β)Ry(γ)Rz(δ).(7.12)

Обобщение этой теоремы может быть выполнено для двух произвольных направлений, определенных векторами �n. В этом случае однокубитовая унитарная матрица может быть

mи�записанаввиде

U = e ^iαRn(β1)Rm(γ1)Rn(β2)Rm(γ1)...(7.13)

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

HXH = Z; HY H = ₋Y;HZH=X;HTH=e^iαRx(π/4)(7.14)

7.3 Контролируемые квантовые гейты

Простейшим двухкубитовым контролируемым гейтом в классическом компьютере является CNOT-гейт. В квантовых вычислениях водится, по сути подобный, гейт, который имеет два входных кубита и два кубита на выходе. Как и в классическом случае один из пары кубитов называется контролирующим, а второй контролируемым или кубитом-мишенью. Буквенное обозначение CNOT-квантового гейта не отличается от классического. Логика выполнения операции при этом определяется следующим образом: если контролирующий кубит находится в состоянии _|1_�, тогда контролируемый кубит подвергается квантовой операции NOT, в противном случае контролируемый кубит остается без изменения. Графически "цепь" квантового CNOT-гейта изображается в виде:

(7.15)

Для пары кубитов _|a_� и _|b_� в качестве базисных можно выбрать вектора, являющиеся прямым произведением базисных векторов отдельных кубитов:

⎞
⎛

1

.

11

|^0a0b� ⁼ |^0a�⊗ |^0b� ⁼0 ⊗ 0 ≡

0

0

(7.16)

0

Аналогично оставшиеся 3 базисных состояния имеют вид:

⎞⎛

⎞⎛

⎞⎛

000

|

^0a1b�≡

1

0

;

|

^1a0b�≡

0

1

;

|

^1a1b�≡

0

0

.

(7.17)

001

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

⎞
⎛

|^ψab� ^{= α} |^0a0b� ^{+ β} |^0a1b� ^{+ γ} |^1a0b� ^{+ δ} |^1a1b�≡

α β γ δ

.

(7.18)

Таким образом матрица квантового CNOT-гейт имеет следующий вид в базисе кубитов

|⁰� ^и

|¹�

⎞

⎛

CNOT =

10000100

00010010

(7.19)

Если выбирать в качестве оператора некоторый произвольный унитарный оператор, действующий на одиночный кубит, то контролируемая U-операция или CONTROLLED Uгейт можно графически определить следующим образом

(7.20)

И в более общем случае

контролирующие кубиты

(7.21)

контролируемые кубиты,

наиболее важным из которых является Тоффоли гейт или CCNOT-гейт

ВэтомгейтеуправляющимиявляютсякубитыAиB,аC–являетсяуправляемым.Впространствебазисныхсостояний3-хкубитов_|0, 0, 0_�, _|0, 0, 1_�, _|0, 1, 0_�, _|1, 0, 0_�, _|1, 0, 1_�,

|

1, 1, 0_�, _|1, 1, 1_� он описывается следующей матрицей размерности 8 _× 8

⎞

⎛

10000000 0 0 0 0 0

1 00000010

⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠

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

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

0100000

0010000

0001000

CCNOT

≡

0000100

0000010

0000000

Последовательность преобразования кубитов в основном базисе выглядит здесь следующим образом:

|^{a, b}� → |^{a, a} ⊕ ^b�

_|a _⊕ (a _⊕ b),a_⊕ b_� = _|b, a _⊕ b_� (7.23)

_|b, (a _⊕ b) _⊕ b_� = _|b, a_�

Важной операцией для кубитов является его измерение, которая отображается на рисунке символом:

(7.24)

Операция измерение преобразует состояние одного кубита _|ψ_� = a _|0_� + b _|1_� в вероятностный классический бит M (изображаемый на выходе двойной линией), который может быть 0 с вероятностью _|a_|² или 1 с вероятностью _|b_|² .

7.4 Невозможность клонирования кубита

CNOT-гейт позволяет продемонстрировать одно фундаментальное свойство квантовой информации. Как известно, задача копирования классического бита информации может быть

выполнена с использованием классического CNOT-гейта

В квантовом случае для произвольного кубита _|ψ_� = a _|0_� + b _|1_� имеем

выход : a _|00_� + b _|11_� (7.26)

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

_|ψ_�|0_� = _{a _|0_� + b _|1_�}|0_� = a _|0_�|0_� + b _|1_�|0_� = a _|00_� + b _|10_� . (7.27)

Так как гейт CNOT не преобразует состояние контролируемого кубита _|0_�, если состояние контролирующего _|0_�, и переворачивает состояние контролируемого кубита, при значении контролирующего _|1_�, то очевидно:

CNOT : a _|00_�→ a _|00_�
CNOT : b _|10_�→ b _|11_� .

Таким образом

CNOT : _|ψ_�|0_� = _|ψ, 0_�→ a _|00_� + b _|11_� . (7.28) Как видно, выход не является произведением состояний _|ϕ_�|ψ_�, за исключением тривиальных случаев _|ϕ_� = _|0_� и _|ψ_� = _|1_�, так как в общем случае

_|ϕ_�|ψ_� = a ² _|00_� + ab _|01_� + ab _|10_� + b² _|11_� . (7.29)

Другими словами такая цепь является цепью, создающей копию классического бита, но некопируеткубит.Общеесвойствоневозможностикопированиякубитаизвестновквантовой теории информации как теорема о неклонируемости кубита (no-cloning theorem).

7.5 Состояния Белла

Рассмотрим более сложную квантовую цепь

_⇒|Cxy_� (7.30)

состоящую из однокубитового гейта Адамара и CNOT-гейта, и рассмотрим результат действия такой цепи на набор двухкубитовых состояний _|x,y_� вида: _|00_�, _|01_�, _|10_�, _|11_�.

Например, при действии гейта Адамара на _|00_� на выходе будем иметь (_|0_� + _|1_�) _|0_� /√2,апоследействиягейтаCNOTполучимдвухкубитовоесостояниевида(_|00_� + _|11_�)/√2.Длявсехчетырехначальныхсостоянийможнозаписатьквантовыйаналогтаблицыистинности:

вход

|⁰⁰� |⁰¹� |¹⁰� |¹¹�

выход (_|00_� + _|11_�)/√2_≡|C00_� (_|01_� + _|10_�)/√2_≡|C01_�

(7.31)

⁽|⁰⁰�− |¹¹�^)/√2 ≡|^C10�

(_|01_� + _|10_�)/√2_≡|C11_�

			Двухкубитовые состояния |Cij�, i,j ∈ 0, 1 называются состояниями Белла или EPR-парами (EPR≡Einstein-Podolsky-Rosen), которые обнаружили странные (необычные) свойства этих состояний. Сокращенно эти состояния можно записать в виде:

|Cxy�≡

|0y�+(−1)x√2

|1y�,

(7.32)

гдеy≡¬y.

7.6 Квантовый параллелизм

Квантовыйпараллелизм–этофундаментальноесвойствоквантовыхвычислений.Данноесвойствопозволяетквантовымкомпьютерамвычислятьфункциюf(x)дляразличныхзначенийxодновременно.

Для иллюстрации квантового параллелизма рассмотрим вычисление функции от битовой переменной x, результатом которой также является битовое значение

f(x):_{0, 1_}→{0, 1_}. (7.33)

Приемлемый способ вычисления этой функции на квантовом компьютере – эторассмотрение двухкубитового квантового компьютера, который оперирует с состоянием _|xy_�. Используя соответствующую последовательность логических гейтов можно преобразовать исходное состояние _|xy_� всостояние _|x, y _⊕ f(x)_�.Здесьможносказать,чтоx,y–регистрыквантовогокомпьютера.Приэтомпервыйрегистрбудемназыватьрегистромданных,авторой–регистроммишени.Положим,чтопреобразование_|x,y_{�→ |}x, y _⊕ f(x)_� осуществляется некоторым унитарным преобразованием U. В нашем случае мы можем рассматривать U как некий "черный ящик". Как следует из преобразования, если y =0, то:

_|x, 0_{�→ |}x,f(x)_� . (7.34)

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

|^x� (7.35)

|^x�

|^y�

|^y ⊕ ^f(x)�

Рассмотрим квантовую цепь (7.35) которая действует на входные состояния вида

_|ψ_�? (7.36)

т.е. на регистр данных (_|ψ_�) попадает суперпозиция (_||1_�)/√2,котораяможетбыть

⁰_� ⁺ создана действием гейта Адамара на кубит _|0_�.Врезультатедействия"черногоящика"Uрезультирующеесостояниебудетиметьвид:

0,f(0)_� 1,f(1)_�

_|ψ_� = |_√2+ |_√2 . (7.37)

Вданномудивительномрезультирующемсостоянииразличныечленысодержатинформациюкакозначенииf(0),такиозначенииf(1)!Фактическиэтосоответствуетвычислениюфункцииf(x)длядвухзначенийxодновременно.Этосвойствоиобозначаетсявквантовыхвычисленияхкак"квантовыйпараллелизм".Вотличиеоторганизациипараллельныхвычисленийвклассическихкомпьютерах,когдатехническисоздаетсянесколькопараллельныхцепей,производящихвычисленияодновременновквантовомкомпьютереэтоосуществляетсяводнойцепинасуперпозициисостояний.

ДаннаяпроцедураможетбытьлегкообобщенадляфункцииспроизвольнымчисломбитовпутемвведенияпреобразованияУолша-Адамара(Walsh-Hadamard),представляющеесобойпрямоепроизведениеоднокубитовыхоператоровАдамара:

^Wˆ≡ ^Hˆ1 ⊗ ^Hˆ2 ⊗ ^Hˆ3 ⊗···⊗ ^{Hˆn. (7.38)} Данныйоператор–естьn-штукгейтовАдамара,действующихпараллельнонаn-кубитов.Например,вслучаеn=2придействиинакубитывначальномсостоянии_|0_�, получим

H

_|ψ_�≡ |⁰�_√⁺₂|¹�_·|⁰�_√⁺₂|¹� = |⁰⁰� ⁺ |⁰¹� ⁺₂ |¹⁰� ⁺ |¹¹�. (7.39)

|⁰�

H

|⁰�

Вобщемслучае,результатдействиягейтаАдамара-Уолшанаn-штуккубит,первоначальнонаходящихсявсостоянии_|0_� приводит к результату:

1 ^�

W^ˆ_|0_� =_{2n |}(7.40)

^x_� ^,

x

где суммирование осуществляется по всем возможным состояниям x (см. пример при n = 2 (7.39)).

ТакоепреобразованиеАдамара-Уолшапроизводитсуперпозициювсехбазисныхсостоянийсравнойамплитудой.Болеетогооночерезвычайноэффективнодляпостроениясуперпозиции2ⁿ состояний,используяприэтомтолькоn-гейтов.

Квантовыепараллельныевычисленияфункциисn-битовымвходомxиоднобитовымвыходомf(x)могутбытьпостроеныследующимобразом.Приготовимn+1-кубитовоесостояние_|0_� навыходе.ПрименимпреобразованиеУолша-Адамаракпервымn-кубитам,споследующимприменениемцепиU.Врезультатеполучимсостояние

1 ^�

UW^ˆ(n)_|0_{�→ √2n |}x_�|f(x)_� . (7.41)

x

В определенном смысле квантовый параллелизм способен вычислить возможные значения функции f одновременно для всех значений, хотя f вычисляется только один раз! Однако такой параллелизм оказывается не очень-то полезным.

Действительно, в нашем двухкубитовом примере измерение состояния даст только

_|0,f(0)_� или _|1,f(1)_�. Аналогично в общем случае, измерение состояния _|x,f(x)_� может

x

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

значениифункцииf(x)изсуперпозициисостоянийподобно_{x |}x,f(x)_�.Такаязадачарешаетсяприпостроенииспециальныхквантовыхалгоритмов.НижеприводитсяпримердействиягейтаУолша-Адамарананачальноеn-кубитовоесостояние_|0_�.Еслиимеетсяпроизвольноеn-кубитовоесостояние_|x_� (например, _|x_�≡ 01011..._�), то

n

1 ²ⁿ−¹

y

W^ˆ_|x_� = _√2n (₋1)^x·_|y_� ,

y=0

где x,y– цепочки из 2ⁿ состоянийn-кубитов,аxyобозначаетихпобитовоескалярное

·

произведение по модулю 2, определяемое как

2n₋1

xy _≡ (xn_∧ yn).

·

n=

0