Файл: sem8.doc

Семинар 8. Квантовые алгоритмы.

8.1 Алгоритм Дойча (Deutsch).

Алгоритм Дойча сочетает квантовый параллелизм с квантовомеханической интерференцией. Рассмотрим цепь приведенную на рис. 8.1.

Пусть гейт Адамара приводит первый кубит в суперпозицию вида (|0_� + |1�)/√2,авторойкубитвсостояниесуперпозициивида(|0_�−|1�)/√2.Этоозначает,чтогейтАдамарадействуетнапервыйкубитвсостоянии|1�, а на второй кубит в состоянии |1�.

рис. 8.1. Входное состояние такой цепи, есть двухкубитовое состояние вида: |ψ0_� = |01_� . (8.1) После действий оператора Адамара данное двухкубитовое состояние будет иметь вид:

|⁰� ⁺ |¹�|⁰�− |¹�. (8.2)

|ψ¹� ⁼ √2 ·√2

Рассмотрим действие оператора Uˆна |x_� (|0_{�− |}1�)/√2,где|x_� может принимать одно из двух значений: |x_� = |0_� или |x_� = |1_�

U_ˆ^�� ₌ |0, 0 _⊕ f(0)_{�− |}0, 1 _⊕ f(0)_� , для |x_� =0 _(8.3)|x� ⁽|⁰�− |¹�⁾ |1, 0 _⊕ f(1)_{�− |}1, 1 _⊕ f(1)_� , для |x_� =1.

Функцияf(x)принимаетзначения0или1,приx=0,1.Рассмотримпоследовательнослучай|x_� = |0_�

Uˆ=^{0, 1}� ,f⁽⁰⁾⁼⁰=(−1)f⁽⁰⁾(8.4)

|⁰� ⁽|⁰�− |¹�⁾ |^{0, 0�− |}0, 0_� ,f(0)=1|⁰� ⁽|⁰�− |¹�^).

|^{0, 1}�−|Аналогичнодляслучая|x_� = |1_�

Uˆ1_� (1�)= |^{1, 0}�− |^{1, 1}� ,f⁽¹⁾⁼⁰=(−1)f⁽¹⁾1_� (1�). (8.5)

||⁰�− ||1, 1_{�− |}1, 0_� ,f(1)=1||⁰�− |

Объединяя равенства (8.4) и (8.5) получим

ˆ

U ^� |x_� (|0_{�− |}1�) ^� =(−1)f⁽x⁾|x_� (|0_{�− |}1�)/√2. (8.6)

Таким образом после действия цепи U на двухкубитовое состояние |ψ1_� получим

_{U :} |ψ_{1�→ |}ψ_{2� =} ±|⁰�√+₂|¹�|⁰�√+₂|¹�,еслиf(0)=f(1)_{. (8.7)}

·

±|⁰�−|¹�|⁰�−|¹�,еслиf(0)=f(1)

√² · √² �

Действуя в соответствии с цепью приведенной на рис. 8.1. на первый кубит гейтом Адамара, находим:

0_� |⁰�−|¹�еслиf(0)=f(1)

√2

H^{1 :} |ψ²�⇒ |ψ²� ⁼ ±|1_� |⁰�−|¹�еслиf(0)=f(1)^{. (8.8)}

±|√² �

Учитывая,чтоf(0)_⊕ f(1)=0еслиf(0)=f(1),иf(0)_⊕ f(1)=1,еслиf(0)=�f(1)можнопереписать выражение (8.8) в виде

|ψ3_� = ±|f(0)_⊕ f(1)�|⁰�− |¹�. (8.9)

√2

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

В простейшем варианте задача Дойча состоит в следующем ¹ Пустьимеютсячетыребинарныефункцииfi(x)отдвоичнойпеременнойx=0,1приэтомфункцииf1иf2–постоянныипринимаютзначенияf1(x)=0,f2(x)=1,афункцииf3иf4–принимаютследующиезначения:f3(x)=x,f4(x)=x.Приэтомговорят,чтофункцииf3иf4–

¬

сбалансированы. В задаче Дойча требуется определить к какой группе (постоянные или сбалансированные) относится функция fi

Классическоерешениетакойзадачипредполагаетпроведениекакминимумдвухопераций

– вычислениеfi(0)иfi(1).Квантовыйалгоритмпозволяетрешитьзадачузаоднуоперацию.Квантовыйкомпьютерработаеткакчерныйящик(вквантовыхвычисленияхегопринятоназыватьОракул),выполняяунитарнуюоперацию

Uˆ|x_{�⊗ |}y_{� ⇒|}x_{�⊗ |}y _⊕ f(x)_� . (8.10)

Оператор Uˆпредставляется четырьмя матрицами размерности 4 _× 4, определяющими четыре

¹ DeutschD.QuantumTheorytheChurch-TuringPrincipleandtheUniversalQuantumComputer.Proc.Roy.Soc.London,1985,VA400,№1818,p.57.Переводсанглийскогоподред.В.А.Садовничего:Сборн"Квантовыйкомпьютериквантовыевычисления".Ижевск.Ред.журн."Регулярнаяихаотическаядинамика",1999,с.157.

возможныефункцииfi(x)U_ˆf_{1 ≡} 0₀

⎟⎟⎠

⎜⎜⎝ ⎞

⎛

⎞

⎛

10000100

010

001

_≡ ˆUˆf₂

I;

≡

1000

0001

_≡ Iˆ_⊗ NOT ;

00010010

⎞

⎛

⎞

⎛

10000100

U_ˆf_{3 ≡} 0₁

00100001

Как следует из изложенного выше алгоритма для решения задачи Дойча достаточно только одной операции (квантовая цепь 8.1). Если состояние первого кубита на выходе цепи (8.9) |0�,тоf1,2(x)–постоянныефункции.Еслисостояниепервогокубитанавыходецепи|1�,тоf3,4(x)–сбалансированныефункции.Существенно,чтоприэтомневычисляютсязначениясамихфункций.Квантовыйкомпьютервыделяет"глобальную"информациюиз

Экспериментально данный алгоритм был реализован на простейших ЯМР– квантовых компьютерах ²

8.2 Алгоритм Дойча – Джозса (Deutsch-Jozsa).

Данный алгоритм был сформулирован для общего случая, когда |x_� и |y_� являются векторами в 2n-мерном гильбертовом пространстве x_� =x0,x1,...xn−1�, y_� =

_ˆ|||3

⎟⎟⎠_{суперпозициисостояний. аквантовыйОракул} ^{действуетнамногомерныйвекторсостояния} U|�y,y_,...y,.₀₁₁−n

Задача,вданномалгоритмеформулируетсяподобнопредыдущемуалгоритмуиимеетцельюопределитьявляетсялидвузначнаяфункцияпостояннойилисбалансированной,имеющейоднозначениедляоднойполовиныданныхxидругое–длявторой.Квантовыйалгоритмпозволяетрешитьэтузадачузаn-операций,тогдакакклассическийалгоритмимеетрешение

⎜⎜⎝

за 2n-операций.

Алгоритм может быть продемонстрирован на примере следующей игры. Алиса, находясь в Амстердаме, выбирает число x из 0 _÷ 2ⁿ ₋ 1ипосылаетегопопочтеБобувБостоне.Бобвычисляетнекоторуюфункциюf(x)исообщаетрезультат,которыйможетбытьили0,или1.ПриэтомБобобещалиспользоватьфункциюf,однуиздвухтипов:Либоf(x)–постояннадлявсехзначенийx,либоf(x)–сбалансирована,приэтомонаравна1точнодляполовинывсехвозможныхзначенийxиравна0длядругойполовины.ЗадачаАлисыопределитьдостовернокакойтипфункциивыбранБобомдлявычислений,затративприэтомминимумкорреспонденции.

В классическом случае Алиса может послать Бобу только одно значение x в каждом письме. Поэтому Алиса будет вынуждена запросить Боба по меньшей мере 2n/2+1раз,таккаконаможетполучить2n/2 нулей для окончательного получения 1, объясняющего ей,

²К.А.Валиев,А.А.Кокин"Квантовыекомпьютеры:надеждыиреальность",Москва.Ижевск.R&C2001г.

³Deutsch D., Jozsa R. Rapid Solution of Problems by Quantum Computation. Proc. Roy. Soc., London, 1992, V A439, № 1907, p.553. Перевод с английского под ред. В.А. Садовничего: Сборн. "Квантовый компьютер и квантовые вычисления". Ижевск: Ред. журн. "Регулярная и хаотическая динамика", 1999, с.191.

010

1000

Uˆf₄

_≡ CNOT(Iˆ_⊗ NOT ). (8.11)

_≡ CNOT ;

≡

000

0010

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

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

Алисаимеетn-кубитовыйрегистрдлянакапливаниясвоегозапросаиоднокубитовыйрегистр,которыйонапредставляетБобудляразмещенияответа.Алисаприготавливаеткакрегистрзапроса,такирегистрответавсостояниисуперпозиции.Бобпроведетвычислениеf(x)сиспользованиемквантовогопараллелизмаипоместитрезультатврегистрответа.ЗатемАлисаосуществляетинтерференциюсостоянийиспользуягейтАдамарадлярегистразапросаизаканчиваетисследованияпутемпроведенияподходящегоизмерениясцельюопределенияявляетсялиfпостояннойфункциейилисбалансированной.

Пошаговое исполнение алгоритма представлено квантовой цепью на рис. 8.2.

|ψ1_� вида: _��

ψ1_� = ^� √|^x ₂ � _n |⁰�− |. (8.13)

|√2^1�

x∈{⁰,¹}ⁿ

Регистр запроса теперь является суперпозицией всех значений x, а регистр ответа находится в суперпозиции состояний |0_� и |1�.

Затем Боб вычисляет функцию f, используя квантовый оракул:

Uˆ: |x,y_{�→ |}x,y _⊕ f(x)_� . (8.14)

В результате образуется состояние |ψ2_� вида:

⁽−¹⁾f⁽x⁾|x�|⁰�− |¹� . (8.15)

|ψ²� ⁼ √2n√2

x

ТеперьАлисаимеетнаборкубитов,вкоторыхрезультатвычисленияфункциисобранвамплитудесуперпозициикубитовогосостояния.АлисадалееиспользуетинтерференциюслагаемыхвсуперпозициипутемдействияГейтаАдамаранарегистрзапроса.ЧтобыопределитьрезультатдействияпреобразованийАдамараполезно,вычислитьдействиепреобразованияАдамаранасостояние|x�. Рассматривая случаи x =0 и x =1 раздельно, мы видим, что для одиночного кубита

H |x_� = ^� (−1)^xz |z_� /√2. (8.16)

z

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

1 ^�

H⊗ⁿ |x1...xn_� = √_2n (−1)x¹z¹+···+xnzⁿ |z1...zn_� ,(8.17)z1...zn

что может быть записано компактно в форме:

1 ^�

H⊗ⁿ |x_� = √_2n (−1)x·^z |z_� , (8.18)

z

где xz– побитовое внутреннее произведение x и z по модулю 2. Используя (8.18) можно

·

записатьрезультатвычислениясостоянияψ3_� ψ3_� = ^{�� 1}(−1)x·z+f⁽x⁾z�|⁰�− |¹� . (8.19)

| 2ⁿ |√2

xz

ТеперьАлисаможетнаблюдатьрегистрзапроса.Отметим,чтоамплитудадлясостояния 0�⊗ⁿ есть ^� (−1)f⁽x⁾/2ⁿ . |

x

Вслучае,еслиf–константа,амплитудадля|0�⊗ⁿ равна +1 или −1,взависимостиотзначенияконстантыf(x).Таккаксостояние|ψ3_� имеет единичную длину отсюда следует, что все другие амплитуды должны быть равны 0 и измерение даст нулевые значения для всех кубитов в регистре запроса. Если f сбалансирована тогда положительный и отрицательный вклад в амплитуду для |0�⊗ⁿ сокращается,приводякнулевомузначениюамплитуды,аизмерениедолжнодатьрезультат0хотябыодногокубитаврегистрезапроса.Такимобразом,еслиАлисаизмеряетвсе0,тогдафункцияконстанта,впротивномслучаефункциясбалансирована.

Суммарно алгоритм Дойча-Джозса выглядит следующим образом.

Входные данные:

Оракул U, который осуществляет преобразование |x�|y_{�→ |}x�|y _⊕ f(x)_� для x _{∈ {}0,...2n−¹_} иf(x)∈{0, 1}.

f(x)–либоконстантадлявсехx,либо–сбалансирована,такчтоf(x)=1дляполовинызначенийxиf(x)=0длядругойполовинызначенийx.

Выходные данные: 0 если f – константа.

Время вычислений: одно вычисление Uf .

Алгоритм:

1. |0�⊗ⁿ |1_� – инициализация состояний.

�₂n��

2. _→ ¹−¹ ||⁰�−|¹� – создание суперпозиции с использованием гейта Адамара.

√2nx=0x_� √2

3. _→ (−1)f⁽x⁾||⁰�−|¹� – вычисление f с использованием оракула U.

xx_� √2

→ _{xz 2}1 _n z+f(x)|z_� √₂

(−1)x·|⁰�−|¹� – преобразование Адамара.

z – измерение для получения ответа задачи.

→

8.3 Классы квантовых алгоритмов.

Имеется 3 класса квантовых алгоритмов

– алгоритмы основанные на квантовых версиях Фурье преобразований (Дойча, ДойчаДжозса, алгоритм Шора факторизации целых чисел, дискретный логарифм);

– алгоритмы квантового поиска;

– алгоритмы моделирования квантовых систем.

8.3.1 Квантовые алгоритмы, основанные на квантовых Фурье-преобразованиях.

ДискретноеФурье-преобразованиеобычноопределяетсякакпреобразованиенабораx0,x1,...,xn−1N-комплексныхчиселвнаборкомплексныхчиселy0,y1,...,yn−1, определенных соотношением

1 N−¹

yk ≡√Ne ^2πijk/Nxj.(8.20)

j=0

Такоепреобразованиеимеетмногочисленныеприложениявразличныхотрасляхнауки.РассмотренноевышепреобразованиеАдамара,используемоевалгоритмеДойча-ДжозсаявляетсяпримеромэтогоклассаФурье-преобразований.Имеяввиду,чтомыопределяемлинейноепреобразованиеUнадn-кубитамипутемдействиянавычислительныйбазиссостояний|j�, где 0 � j � 2ⁿ ₋ 1 можно написать

1 ²n−¹

|j_�→ √_2n e ^2πijk/2n |k_� . (8.21)

k=0

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

2n−12n−12n−12n−1

� ₁ �� �

xj |j_�→ √_2n e ^2πijk/2n xj |k_� = yk |k_� (8.22)

j=0k=0j=0k=0

то видно, что преобразование соответствует векторным обозначениям для Фурьепреобразования (8.20) для случая N =2ⁿ .

8.3.2 Алгоритмы квантового поиска.

Алгоритм квантового поиска решает следующую задачу:

Задано пространство поиска содержащее N элементов и нет предварительной информации о структуре расположения элементов в пространстве поиска. Необходимо в данном пространстве элементов найти такой, который удовлетворяет заданному свойству.

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

8.3.3 Алгоритмы квантового моделирования.

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

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

ДискретноеФурье-преобразованиенаборакомплексныхчиселx0,x1,...,xN−1внаборкомплексныхчиселy0,y1,...,yN−1 определяется равенством (8.20)

Квантовое Фурье-преобразование есть аналогичное преобразование, хотя общепринятые обозначения для квантовых Фурье-преобразований несколько отличаются. Квантовое Фурье преобразование ортонормированного базиса |0_� ... |N ₋ 1_� определено как линейный оператор со следующим действием на базисные состояния:

1 N−^1� 1 ^�

|j_�→ √_N exp2πijk_{· N |}k_� . (8.23)

k=0

Эквивалентное, действие на произвольное состояние может быть записано в виде

N−1N−1

xj |j_�→ yk |k_� , (8.24)

j=0k=0

гдеамплитудыykявляютсядискретнымиФурьепреобразованиямиамплитудxj.Этопреобразованиеявляетсяунитарными,поэтому,можетопределятьдинамикуквантовыхвычислений.

В последующем N =2n, где n – произвольное целое число, а базис |0_� ... |2ⁿ ₋ 1_�

– вычислительныйбазисдляn-кубитовогоквантовогокомпьютера.Полезнозаписатьсостояние|j�,используябинарноепредставлениеj=j1j2...jn:

j=j12n−¹ +j22n−² ++jn2⁰ . (8.25)

···

ВведемтакжеследующееобозначениеO.j�j�+1...jmдляпредставлениябинарнойфункции

j�/2+j�+1/4++jm/2m−�⁺¹.

···

76

В результате квантовое Фурье-преобразование может быть задано в следующей полезной форме представления в виде произведения

|j1...jn_�→ √¹_2n ^� |0_� + e ^2πiO.j^m |1_� ^�� |0_� + e ^2πiO.jn−¹jⁿ |1_� ^� ...

... |0_� + e ^2πiO.j¹j^2...jn |1_� . (8.26)

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

2n−1

1 ^�

|j_{� →} √_2n exp(2πijk/2n) |k_� =

k=011n

₁ �� � =√_{2n ···} exp(2πij(k�_· 2−�)) |k1...kn_� =

k1=0kn=0�=1

11n

₁ � �� =√_{2n ···} exp(2πijk�_· 2−�) |k�_� =

k1=0kn=0�=1

^�� (8.27)

n1

₁ ��
=√_2n exp(2πijk�_· 2−�) |k�_� =

�=1k�=0n

1 �� �

=√_2n |0_� +exp(2πij2−�) |1_� =

�=1

1

=√_2n (|0_� +exp(2πiO.jm)|1�)(|0_� +exp(2πiO.jn−1jn)|1�) ...

... (|0_� +exp(2πiO.j1j2...jn)|1�) .

ПредставлениеФурье-преобразованиявформепроизведения(8.26)позволяетлегковывести эффективные квантовые цепи для квантовых Фурье-преобразований. Такие квантовые цепи изображены на рис. (8.5), на которой гейт Rk обозначает унитарное преобразование вида

10

Rk _{≡ 0 e2πi/2}k . (8.28)

Чтобы показать, что нарисованные цепи действительно вычисляют квантовые Фурьепреобразования, рассмотрим изменения состояний, если начальное состояние имеет вид |j1,...,jn�. Применяя гейт Адамара к первому биту получим

1 ��

√₂ |0_� + e ^2πiO.j¹ |1�|j2...jn_� (8.29)

таккакexp(2πiO.j1)=−1когдаj1=1иравна+1впротивномслучае.ИспользуяконтролируемыйR2-гейтпроизводимсостояние:

√¹₂ ^� |0_� + e ^2πiO.j¹j² |1_� ^� |j2...jn_� . (8.30)

ПродолжаявычислениедействийконтролируемыхR3,R4доRn-гейтов,каждыйизкоторыхдобавляетэкстра-биткфазекоэффициентапри|1_� первого кубита. В конце этой процедуры получим состояние:

1 ��

√₂ |0_� + e ^2πiO.j¹j^2...jn |1�|j2j3...jn_� . (8.31)

Преобразуем аналогичной процедурой следующий кубит. В результате получим:

1 � �� �

√₂ |0_� + e ^2πiO.j¹j^2...jn |1�|0_� + e ^2πiO.j^2...jn |1�|j3j4...jn_� . (8.32)

Продолжая последовательно для каждого кубита, находим конечное состояние

1 � �� ���

√_2n |_{0� + e} 2πiO.j1j2...jn|₁�|_{0� + e} 2πiO.j2...jn|_{1� ...} |_{0� + e} 2πiO.jn|_{1� (8.33)}

Используя далее SWAP – операторы, состояние кубитов приводится к формуле (8.26), т. е. выполненное Фурье преобразование.