Файл: sem8.pdf

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

8.1

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

Алгоритм

Дойча

сочетает

квантовый

параллелизм

с

квантовомеханической

интерференцией. Рассмотрим цепь приведенную на рис. 8.1.

Пусть гейт Адамара приводит первый кубит в суперпозицию вида

(

|

0

i

+

|

1

i

)

/

√

2

, а второй

кубит в состояние суперпозиции вида

(

|

0

i−|

1

i

)

/

√

2

. Это означает, что гейт Адамара действует

на первый кубит в состоянии

|

1

i

, а на второй кубит в состоянии

|

1

i

.

рис. 8.1.

Входное состояние такой цепи, есть двухкубитовое состояние вида:

|

ψ

0

i

=

|

01

i

.

(8.1)

После действий оператора Адамара данное двухкубитовое состояние будет иметь вид:

|

ψ

1

i

=

|

0

i

+

|

1

i

√

2

·

|

0

i − |

1

i

√

2

.

(8.2)

Рассмотрим действие оператора

ˆ

U

на

|

x

i

(

|

0

i − |

1

i

)

/

√

2

, где

|

x

i

может принимать одно из двух

значений:

|

x

i

=

|

0

i

или

|

x

i

=

|

1

i

ˆ

U

h

|

x

i

(

|

0

i − |

1

i

)

i

=

(

|

0

,

0

⊕

f

(0)

i − |

0

,

1

⊕

f

(0)

i

,

для

|

x

i

= 0

|

1

,

0

⊕

f

(1)

i − |

1

,

1

⊕

f

(1)

i

,

для

|

x

i

= 1

.

(8.3)

Функция

f

(

x

)

принимает значения

0

или

1

, при

x

= 0

,

1

. Рассмотрим последовательно

случай

|

x

i

=

|

0

i

ˆ

U

h

|

0

i

(

|

0

i − |

1

i

)

i

=

|

0

,

0

i − |

0

,

1

i

,

f

(0) = 0

|

0

,

1

i − |

0

,

0

i

,

f

(0) = 1

= (

−

1)

f

(0)

|

0

i

(

|

0

i − |

1

i

)

.

(8.4)

Аналогично для случая

|

x

i

=

|

1

i

ˆ

U

h

|

1

i

(

|

0

i − |

1

i

)

i

=

|

1

,

0

i − |

1

,

1

i

,

f

(1) = 0

|

1

,

1

i − |

1

,

0

i

,

f

(1) = 1

= (

−

1)

f

(1)

|

1

i

(

|

0

i − |

1

i

)

.

(8.5)

70

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

ˆ

U

h

|

x

i

(

|

0

i − |

1

i

)

i

= (

−

1)

f

(

x

)

|

x

i

(

|

0

i − |

1

i

)

/

√

2

.

(8.6)

Таким образом после действия цепи

U

на двухкубитовое состояние

|

ψ

1

i

получим

U

:

|

ψ

1

i → |

ψ

2

i

=

(

±

|

0

i

+

|

1

i

√

2

·

|

0

i

+

|

1

i

√

2

,

если

f

(0) =

f

(1)

±

|

0

i−|

1

i

√

2

·

|

0

i−|

1

i

√

2

,

если

f

(0)

6

=

f

(1)

.

(8.7)

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

H

1

:

|

ψ

2

i ⇒ |

ψ

2

i

=

(

± |

0

i

|

0

i−|

1

i

√

2

если

f

(0) =

f

(1)

± |

1

i

|

0

i−|

1

i

√

2

если

f

(0)

6

=

f

(1)

.

(8.8)

Учитывая, что

f

(0)

⊕

f

(1) = 0

если

f

(0) =

f

(1)

, и

f

(0)

⊕

f

(1) = 1

, если

f

(0)

6

=

f

(1)

можно

переписать выражение (8.8) в виде

|

ψ

3

i

=

± |

f

(0)

⊕

f

(1)

i

|

0

i − |

1

i

√

2

.

(8.9)

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

f

(0)

⊕

f

(1)

,

т.е. квантовая цепь дает возможность определить

глобальное свойство

функции

f

(

x

)

,

используя только одно вычисление

f

(

x

)

. Это быстрее, чем с использованием классического

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

В простейшем варианте задача Дойча состоит в следующем

1

Пусть имеются четыре

бинарные функции

f

i

(

x

)

от двоичной переменной

x

= 0

,

1

при этом функции

f

1

и

f

2

–

постоянны и принимают значения

f

1

(

x

) = 0

,

f

2

(

x

) = 1

, а функции

f

3

и

f

4

–

принимают

следующие значения:

f

3

(

x

) =

x

,

f

4

(

x

) =

¬

x

. При этом говорят, что функции

f

3

и

f

4

–

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

f

i

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

–

вычисление

f

i

(0)

и

f

i

(1)

. Квантовый алгоритм позволяет решить задачу за одну операцию.

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

ˆ

U

n

|

x

i ⊗ |

y

i

o

⇒ |

x

i ⊗ |

y

⊕

f

(

x

)

i

.

(8.10)

Оператор

ˆ

U

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

4

×

4

, определяющими четыре

1

Deutsch D. Quantum Theory the Church-Turing Principle and the Universal Quantum Computer. Proc. Roy.

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

71

возможные функции

f

i

(

x

)

ˆ

U

f

1

≡







1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1







≡

ˆ

I

;

ˆ

U

f

2

≡







0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0







≡

ˆ

I

⊗

N OT

;

ˆ

U

f

3

≡







1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0







≡

CN OT

;

ˆ

U

f

4

≡







0 1 0 0
1 0 0 0
0 0 1 0
0 0 0 1







≡

CN OT

( ˆ

I

⊗

N OT

)

.

(8.11)

Как следует из изложенного выше алгоритма для решения задачи Дойча достаточно

только одной операции (квантовая цепь 8.1). Если состояние первого кубита на выходе
цепи (8.9)

|

0

i

, то

f

1

,

2

(

x

)

–

постоянные функции. Если состояние первого кубита на выходе

цепи

|

1

i

, то

f

3

,

4

(

x

)

–

сбалансированные функции. Существенно, что при этом не вычисляются

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

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

–

квантовых

компьютерах

2

8.2

Алгоритм Дойча

–

Джозса (Deutsch-Jozsa).

Данный алгоритм был сформулирован для общего случая, когда

|

x

i

и

|

y

i

являются

векторами в

2

n

-мерном гильбертовом пространстве

|

x

i

=

|

x

0

, x

1

, . . . x

n

−

1

i

,

|

y

i

=

|

y

0

, y

1

, . . . y

n

−

1

i

, а квантовый Оракул

ˆ

U

действует на многомерный вектор состояния

3

.

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

x

и другое

–

для второй. Квантовый алгоритм

позволяет решить эту задачу за

n

-операций, тогда как классический алгоритм имеет решение

за

2

n

-операций.

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

в Амстердаме, выбирает число

x

из

0

÷

2

n

−

1

и посылает его по почте Бобу в Бостоне.

Боб вычисляет некоторую функцию

f

(

x

)

и сообщает результат, который может быть или

0, или 1. При этом Боб обещал использовать функцию

f

, одну из двух типов: Либо

f

(

x

)

–

постоянна для всех значений

x

, либо

f

(

x

)

–

сбалансирована, при этом она равна 1 точно

для половины всех возможных значений

x

и равна 0 для другой половины. Задача Алисы

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

В классическом случае Алиса может послать Бобу только одно значение

x

в каждом

письме. Поэтому Алиса будет вынуждена запросить Боба по меньшей мере

2

n

/

2 + 1

раз,

так как она может получить

2

n

/

2

нулей для окончательного получения 1, объясняющего ей,

2

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

3

Deutsch D., Jozsa R. Rapid Solution of Problems by Quantum Computation. Proc. Roy. Soc., London, 1992,

V A439, № 1907, p.553. Перевод с английского под ред. В.А. Садовничего: Сборн. "Квантовый компьютер и
квантовые вычисления". Ижевск: Ред. журн. "Регулярная и хаотическая динамика", 1999, с.191.

72

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

2

n

/

2 + 1

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

n

-бит

информации.

Если Алиса и Боб могут обмениваться кубитами и если Боб согласен вычислить

f

(

x

)

используя унитарное преобразование

U

f

, тогда Алиса может достичь своей цели одной

корреспонденцией используя следующий алгоритм.

Алиса имеет

n

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

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

f

(

x

)

с использованием квантового параллелизма и поместит результат в регистр ответа. Затем

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

f

постоянной функцией или сбалансированной.

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

рис. 8.2.

Исходное состояние есть

|

ψ

0

i

=

|

0

i

⊗

n

|

1

i

,

(8.12)

где регистр запроса определяется

n

-кубитовым состоянием, каждый из которых находится в

состоянии

|

0

i

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

регистра ответа возникнет состояние

|

ψ

1

i

вида:

|

ψ

1

i

=

X

x

∈{

0

,

1

}

n

|

x

i

√

2

n

|

0

i − |

1

i

√

2

.

(8.13)

Регистр запроса теперь является суперпозицией всех значений

x

, а регистр ответа

находится в суперпозиции состояний

|

0

i

и

|

1

i

.

Затем Боб вычисляет функцию

f

, используя квантовый оракул:

ˆ

U

:

|

x, y

i → |

x, y

⊕

f

(

x

)

i

.

(8.14)

В результате образуется состояние

|

ψ

2

i

вида:

|

ψ

2

i

=

X

x

(

−

1)

f

(

x

)

|

x

i

√

2

n

|

0

i − |

1

i

√

2

.

(8.15)

73

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

|

x

i

. Рассматривая случаи

x

= 0

и

x

= 1

раздельно,

мы видим, что для одиночного кубита

H

|

x

i

=

X

z

(

−

1)

xz

|

z

i

/

√

2

.

(8.16)

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

H

⊗

n

|

x

1

. . . x

n

i

=

1

√

2

n

X

z

1

...z

n

(

−

1)

x

1

z

1

+

···

+

x

n

z

n

|

z

1

. . . z

n

i

,

(8.17)

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

H

⊗

n

|

x

i

=

1

√

2

n

X

z

(

−

1)

x

·

z

|

z

i

,

(8.18)

где

x

·

z

–

побитовое внутреннее произведение

x

и

z

по модулю 2. Используя (8.18) можно

записать результат вычисления состояния

|

ψ

3

i

|

ψ

3

i

=

X

x

X

z

1

2

n

(

−

1)

x

·

z

+

f

(

x

)

|

z

i

|

0

i − |

1

i

√

2

.

(8.19)

Теперь Алиса может наблюдать регистр запроса. Отметим, что амплитуда для состояния

|

0

i

⊗

n

есть

P

x

(

−

1)

f

(

x

)

/

2

n

.

В случае, если

f

–

константа, амплитуда для

|

0

i

⊗

n

равна

+1

или

−

1

, в зависимости от

значения константы

f

(

x

)

. Так как состояние

|

ψ

3

i

имеет единичную длину отсюда следует,

что все другие амплитуды должны быть равны 0 и измерение даст нулевые значения для всех
кубитов в регистре запроса. Если

f

сбалансирована тогда положительный и отрицательный

вклад в амплитуду для

|

0

i

⊗

n

сокращается, приводя к нулевому значению амплитуды, а

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

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

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

:

1. Оракул

U

, который осуществляет преобразование

|

x

i |

y

i → |

x

i |

y

⊕

f

(

x

)

i

для

x

∈

{

0

, . . .

2

n

−

1

}

и

f

(

x

)

∈ {

0

,

1

}

.

2.

f

(

x

)

–

либо константа для всех

x

, либо

–

сбалансирована, так что

f

(

x

) = 1

для

половины значений

x

и

f

(

x

) = 0

для другой половины значений

x

.

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

: 0 если

f

–

константа.

Время вычислений

: одно вычисление

U

f

.

Алгоритм

:

74