Файл: sem7.pdf

|

1

,

1

,

0

i

,

|

1

,

1

,

1

i

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

8

×

8

CCN OT

≡















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















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

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

"цепи", например

(7.22)

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

|

a, b

i → |

a, a

⊕

b

i

→ |

a

⊕

(

a

⊕

b

)

, a

⊕

b

i

=

|

b, a

⊕

b

i

→ |

b,

(

a

⊕

b

)

⊕

b

i

=

|

b, a

i

(7.23)

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

символом:

(7.24)

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

|

ψ

i

=

a

|

0

i

+

b

|

1

i

в вероятностный

классический бит

M

(изображаемый на выходе двойной линией), который может быть

0

с

вероятностью

|

a

|

2

или

1

с вероятностью

|

b

|

2

.

7.4

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

CNOT-гейт позволяет продемонстрировать одно фундаментальное свойство квантовой

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

65

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

(7.25)

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

|

ψ

i

=

a

|

0

i

+

b

|

1

i

имеем

вход

≡ |

ψ

i |

0

i

:

выход

:

a

|

00

i

+

b

|

11

i

(7.26)

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

|

ψ

i |

0

i

=

{

a

|

0

i

+

b

|

1

i} |

0

i

=

a

|

0

i |

0

i

+

b

|

1

i |

0

i

=

a

|

00

i

+

b

|

10

i

.

(7.27)

Так как гейт CNOT не преобразует состояние контролируемого кубита

|

0

i

, если состояние

контролирующего

|

0

i

, и переворачивает состояние контролируемого кубита, при значении

контролирующего

|

1

i

, то очевидно:

CN OT

:

a

|

00

i →

a

|

00

i

CN OT

:

b

|

10

i →

b

|

11

i

.

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

CN OT

:

|

ψ

i |

0

i

=

|

ψ,

0

i →

a

|

00

i

+

b

|

11

i

.

(7.28)

Как видно, выход не является произведением состояний

|

ϕ

i |

ψ

i

, за исключением тривиальных

случаев

|

ϕ

i

=

|

0

i

и

|

ψ

i

=

|

1

i

, так как в общем случае

|

ϕ

i |

ψ

i

=

a

2

|

00

i

+

ab

|

01

i

+

ab

|

10

i

+

b

2

|

11

i

.

(7.29)

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

не копирует кубит. Общее свойство невозможности копирования кубита известно в квантовой
теории информации как

теорема о неклонируемости кубита

(no-cloning theorem).

7.5

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

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

⇒ |

C

xy

i

(7.30)

66

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

|

x, y

i

вида:

|

00

i

,

|

01

i

,

|

10

i

,

|

11

i

.

Например, при действии гейта Адамара на

|

00

i

на выходе будем иметь

(

|

0

i

+

|

1

i

)

|

0

i

/

√

2

,

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

(

|

00

i

+

|

11

i

)

/

√

2

. Для

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

вход

выход

|

00

i

(

|

00

i

+

|

11

i

)

/

√

2

≡ |

C

00

i

|

01

i

(

|

01

i

+

|

10

i

)

/

√

2

≡ |

C

01

i

|

10

i

(

|

00

i − |

11

i

)

/

√

2

≡ |

C

10

i

|

11

i

(

|

01

i

+

|

10

i

)

/

√

2

≡ |

C

11

i

(7.31)

Двухкубитовые состояния

|

C

ij

i

,

i, j

∈

0

,

1

называются

состояниями Белла

или

EPR-парами

(EPR

≡

Einstein-Podolsky-Rosen), которые обнаружили странные (необычные)

свойства этих состояний. Сокращенно эти состояния можно записать в виде:

|

C

xy

i ≡

|

0

y

i

+ (

−

1)

x

|

1

y

i

√

2

,

(7.32)

где

y

≡ ¬

y

.

7.6

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

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

–

это фундаментальное свойство квантовых вычислений. Данное

свойство позволяет квантовым компьютерам вычислять функцию

f

(

x

)

для различных

значений

x

одновременно.

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

переменной

x

, результатом которой также является битовое значение

f

(

x

) :

{

0

,

1

} → {

0

,

1

}

.

(7.33)

Приемлемый способ вычисления этой функции на квантовом компьютере

–

это рассмотрение

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

|

xy

i

. Используя

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

|

xy

i

в состояние

|

x, y

⊕

f

(

x

)

i

. Здесь можно сказать, что

x

,

y

–

регистры квантового

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

регистром данных

, а второй

–

регистром мишени

. Положим, что преобразование

|

x, y

i → |

x, y

⊕

f

(

x

)

i

осуществляется

некоторым унитарным преобразованием

U

. В нашем случае мы можем рассматривать

U

как

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

y

= 0

, то:

|

x,

0

i → |

x, f

(

x

)

i

.

(7.34)

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

f

(

x

)

.

|

x

i

|

y

i

|

x

i

|

y

⊕

f

(

x

)

i

(7.35)

67

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

0

i

+

|

1

i

√

2

|

0

i

|

ψ

i

?

(7.36)

т.е. на регистр данных

(

|

ψ

i

)

попадает суперпозиция

(

|

0

i

+

|

1

i

)

/

√

2

, которая может быть

создана действием гейта Адамара на кубит

|

0

i

. В результате действия "черного ящика"

U

результирующее состояние будет иметь вид:

|

0

i

+

|

1

i

√

2

|

0

i

|

ψ

i

=

|

0

, f

(0)

i

√

2

+

|

1

, f

(1)

i

√

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

i

, получим

|

0

i

H

|

0

i

H

|

ψ

i ≡

|

0

i

+

|

1

i

√

2

·

|

0

i

+

|

1

i

√

2

=

|

00

i

+

|

01

i

+

|

10

i

+

|

11

i

2

.

(7.39)

В общем случае, результат действия гейта Адамара-Уолша на

n

-штук кубит, первоначально

находящихся в состоянии

|

0

i

приводит к результату:

ˆ

W

|

0

i

=

1

2

n

X

x

|

x

i

,

(7.40)

где суммирование осуществляется по всем возможным состояниям

x

(см. пример при

n

=

2

Такое преобразование Адамара-Уолша производит суперпозицию всех базисных

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

2

n

состояний, используя при этом только

n

-гейтов.

68

Квантовые параллельные вычисления функции с

n

-битовым входом

x

и однобитовым

выходом

f

(

x

)

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

n

+ 1

-кубитовое

состояние

|

0

i

на выходе. Применим преобразование Уолша-Адамара к первым

n

-кубитам,

с последующим применением цепи

U

. В результате получим состояние

U

ˆ

W

(

n

)

|

0

i →

1

√

2

n

X

x

|

x

i |

f

(

x

)

i

.

(7.41)

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

значения функции

f

одновременно для всех значений, хотя

f

вычисляется только один раз!

Однако такой параллелизм оказывается не очень-то полезным.

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

|

0

, f

(0)

i

или

|

1

, f

(1)

i

. Аналогично в общем случае, измерение состояния

P

x

|

x, f

(

x

)

i

может

дать только

f

(

x

)

для одного значения

x

. Конечно и классический компьютер все это делает

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

f

(

x

)

из суперпозиции состояний подобно

P

x

|

x, f

(

x

)

i

. Такая задача

решается при построении специальных квантовых алгоритмов.

Ниже приводится пример действия гейта Уолша-Адамара на начальное

n

-кубитовое

состояние

|

0

i

. Если имеется произвольное

n

-кубитовое состояние

|

x

i

(например,

|

x

i ≡

|

01011

. . .

i

|

{z

}

n

), то

ˆ

W

|

x

i

=

1

√

2

n

2

n

−

1

X

y

=0

(

−

1)

x

·

y

|

y

i

,

где

x, y

–

цепочки из

2

n

состояний

n

-кубитов, а

x

·

y

обозначает их побитовое скалярное

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

x

·

y

≡

2

n

−

1

X

n

=0

(

x

n

∧

y

n

)

.

69